Schéma général

Conseil

Trois décisions à prendre pour avoir un algorithme diviser-pour-régner efficace :[1]

  • Quand est x « petit ou simple ? » Détermination d'un seuil adéquat. Bien décider quand utiliser l'algorithme simple sur de petites instances plutôt que les appels récursifs.

  • Comment décomposer x ? Nombre de morceaux, de taille équilibrée. Les sous-instances doivent être, autant que possible, environ de la même taille. La décomposition d'une instance en sous-instances doit être efficace.

  • Comment recombiner les solutions des sous-exemplaires ? une façon efficace de profiter du travail accompli. La recombinaison des sous-solutions doit être efficace.

L'algorithme générique de diviser pour régner peut être résumé comme suit :

1
Fonction Diviser_Régner (P : Problème) : Solution
2
Variables S : Solution ;
3
Début
4
 Si (‖𝑃‖ est petite) Alors S  CasBase(P)
5
 Sinon
6
 (P1, P2, ..., Pk )  Diviser (P) ;
7
 Pour i  1 à k Faire Si  Regner (Pi) ; FinPour
8
 S  Combiner (S1, S2, ..., Sk ) ;
9
 FinSi
10
 Retourner S ;
11
Fin