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