4 - Le Backtracking
Définition :
Le backtracking permet de trouver une solution à un problème en essayant plusieurs possibilités. Si un chemin emprunté semble erronée ou mener à une solution incorrecte, l'algorithme revient en arrière, repart à l'endroit il a fait le mauvais choix et teste une autre voie.
Génération exhaustive :
On distingue également la
génération exhaustive, c'est-à-dire que dans ce procédé, on énumère toutes les structures d'un ensemble donné. Par exemple, si on veut générer tout les mots de 5 lettres donné par notre alphabet, sans backtracking on s'y prendrait ainsi :
Code : Tout sélectionner
$text = ""
For $char = 97 to 122
$text &= Chr($char)
For $char = 97 to 122
$text &= Chr($char)
For $char = 97 to 122
$text &= Chr($char)
....
msgbox(0,"",$text) ;afficher le premier mot
$text = "" ;réinitialiser texte
Next
Next
Next
Imaginez si l'ont devait afficher tous les mots de 100 lettres !
Mais avec le backtracking, regardez bien :
Code : Tout sélectionner
const $N = 2 ;longueur du mot, prenons 2 pour pas trop faire ramer le pc ^^
Dim $array[$N]
Global $mots
GenerationMot(0)
msgbox (0,'',$mots)
Func GenerationMot($i)
If $i=$N Then ;FIN -> AFFICHAGE AVEC LE BACKTRACKING
For $j=0 to $N-1 step 1
$mots &= $array[$j]
Next
$mots &= " "
Else
For $char = 97 to 122
$array[$i] = Chr($char)
GenerationMot($i+1)
Next
Endif
Endfunc
En clair, au début on met dans array[0] "a" -> i+1 array[1] "a" -> i+1 ... -> i = n
backtracking -> array[n-1] = "b" -> i = n
backtracking -> array[n-1] = "c" etc
D'ou l'exemple avec deux lettres donne bien :
aa ab ac ad .... az ba bb bc.....
Démolition d'une solution
Contrairement à la définition donnée en début de post, la génération exhaustive ne cherche pas spécialement une bonne solution, elle génère toutes les possibilités d'un ensemble donné. Si dans un problème, seulement quelques solutions nous conviennent, il faut tester toutes les possibilités, certes, mais éliminer celle qui ne répondent pas au problème et non les énumérer comme la génération exhaustive. Nous devons donc
démolir des solutions partielles.
Prenons l'exemple d'un sac dont on définit le volume au préalable. Nous avons plusieurs briques de volume différent à disposition. Le but est de rechercher toutes les combinaisons telles que le volume des briques dans le sac = le volume total du sac. Par exemple si le sac a un volume de 10 et qu'on a mis des briques dont le total vaut 9. Si il nous reste une brique de volume 2, 4 et 7, on va dépasser 10 donc la combinaison essayée est fausse.
Regardez plutôt ce script :
Code : Tout sélectionner
;le nombre d'objets, disons des briques, à notre disposition
Global $n = InputBox("Question", "Nombre d'objets ?", "10")
Dim $volume[$n]
Dim $bool[$n]
Global $volumesac
Global $volumetotal
;définition du volume des objets, prenons ici objet1 à un volume 1, objet 2 volume de 2 etc.
For $j=0 To $n-1 Step 1
$volume[$j]=$j+1
Next
;Le sac peut contenir au maximum des briques dont le volume total vaut 10
$volumetotal = InputBox("Question", "Volume du sac ?", "10")
Combinaisons(0)
Func Combinaisons($i)
If $i = $n Then ;si on est à la fin d'une possibilité
If $volumesac = $volumetotal Then ;si elle est juste
local $texte
For $j=0 to $N-1 step 1 ;on affiche
If $bool[$j] = true Then
$texte &= $volume[$j]&"+"
Endif
Next
$texte &= "="&$volumetotal
msgbox(0,"",$texte)
Endif
Else
;premier essai, on prend l'objet $i
$bool[$i] = true
$volumesac += $volume[$i]
Combinaisons($i+1)
;démolition de la solution partielle
$volumesac -= $volume[$i]
;deuxieme essai, on ne prend pas l'objet $i
$bool[$i] = false
Combinaisons($i+1)
;Fin du script donc pas nécessaire de détruire la solution partielle
Endif
Endfunc
Il correspond parfaitement à notre attente. En clair toutes les combinaisons seront testées grace aux booléens. Un peu à l'instar des mots (script précédent), on teste toutes les possibilités :
true, true ,true, true
true, true ,true, false
true, true, false, true
true, true, false, false
...
A la fin de chaque combinaison, si le volume des briques choisies est égal au volume du sac : c'est gagné on affiche la solution. Si on dépasse, on détruit la solution grâce à $volumesac -= $volume[$i].
Cet exemple est bien entendu plutôt facile, mais si vous aimez il y a bien plus dur ! Orientez vous par exemple vers le
problème des huit dames ou le
voyageur de commerce résolu grâce à l'algorithme branch & bound.
Ceci clôt ce tutorial. N'hésitez pas si vous avez des questions.