Exploration systématique de graphes
[Link]
[Link] en profondeur (Backtracking )
Exemples :
. Placer 8 reines dans un échiquier
. Problème des cruches d'eau
. Sortie d'un labyrinthe
Exploration systématique de graphes
Introduction
• Méthode de recherche (fouille) systématique pour la recherche
d'une solution dans un graphe orienté implicite, le plus souvent
sans circuit ou même arborescent. (Ex trouver son chemin dans un
labyrinthe)
• Le parcours se fait généralement en profondeur.
• Si le graphe est très grand(ou infini) ou si l'on veut plutôt chercher
une solution avec peu de manipulations, on utilise un parcours en
largeur.
Backtracking
Application 1 : Problèmes des 8 reines :
• "Il faut placer 8 reines dans un échiquier ( matrice 8X8) sans
qu'aucune d'entres elles ne soit en prise par une autre." Deux
reines sont en prise, si elles se trouvent sur une même ligne, une
même colonne ou une même diagonale).
Backtracking
Application 1 : Problèmes des 8 reines :
• On démarre d'un échiquier vide.
• premier niveau : Il y a 64 cas possibles de placer la premier reine.
• Deuxième niveau : Pour chaque cas du niveau 1, il y a 63
possibilités de placer une reine.( Chaque cas qui ne répond pas à la
condition est écarté).
• Et ainsi de suite....
Backtracking
Application 1 : Problèmes des 8 reines :
• On peut améliorer l'algorithme en considérant uniquement les
positions où deux reines ne sont ni sur la même ligne ni sur la
même colonne.
• On peut ainsi représenter tout l'échiquier par un vecteur V [1, 8]
où les indices désignent les lignes et les contenus les colonnes.
Par exemple si V est 1, 3, 7,....
Première ligne, première colonne: on a une reine
Deuxième ligne, troisième colonne : on a une reine
Troisième ligne, septième colonne : on a une reine
Backtracking
Application 1 : Problèmes des 8 reines :
• Afin de montrer le principe, restreingnons l'espace de recherche
en imaginant un échiquier 4 X 4.
Backtracking
Backtracking
Backtracking
Application 1 : Problèmes des 8 reines :
• Un arbre implicite se construit avec une recherche en profondeur.
• Niveau 1 : placer la reine sur la première colonne de la ligne une.
• Niveau 2 : essayer de placer la seconde reine de sorte qu'il n'y ait
pas de prises.
• Niveau 3 : Dans les mêmes conditions, placer la troisième.
• Et ainsi de suite ....
• Si échec, remonter dans l'arbre pour essayer d'autres éventualités.
Backtracking
Application 1 : Problèmes des 8 reines :
• Remarquer que
— pour une diagonale positive, la différence des indices est constante.
— pour une diagonale négative, la somme des indices constante
— Les valeurs possibles pour les diagonales positives sont : 0, 1, 2,
...7, -1, -2, ..., -7
— Les valeurs possibles pour les diagonales négatives sont : 2, 3, 4, 5,
6, 7, 8.
Backtracking
Backtracking
Application 1 : Problèmes des 8 reines :
Procedure Placer (K) { On a déjà réussi à placer K reines et on
place la reine suivante}
Si K = 8 Ecrire (V)
Sinon Pour j=1, 8
Si (j n'appartient pas à Col ET
k+1 - j n'appartient pas à DiagP ET
k+1 + j n'appartient pas à DiagN) :
V[k+1] := j ; Col := Col U {j}
DiagP := Diagp U {k+1 - j}
DiagN := DiagN U {k+1 + j}
Placer( k+1 )
Fsi Finpour Fsi
Backtracking
Application 1 : Problèmes des 8 reines
• Appel initial : Placer(0)
• Col, DiagP et DiagN initialisés à {}.
• L'algorithme ressemble à l'algorithme dfs défini sur les graphes.
Backtracking
Application 2 : Problèmes des cruches d'eau.
• Deux cruches A(4litres) et B(3litres).
• On part de A = 0 et B = 0 et on veut arriver à (2, n).
Backtracking
Application 2 : Problèmes des cruches d'eau.
• Ensemble des règles applicables:
1. Si A non pleine : Remplir A
2. Si B non pleine : Remplir B
3. Si A non vide alors vider A
4. Si B non vide alors vider B
5. Si A non vide et A>(3-B) alors verser le contenu de A dans B
jusqu'à ce que B soit plein.
6. Si B non vide et B>(4-A) alors verser le contenu de B dans A
jusqu'à ce que A soit plein.
7. Si A non vide et A <= (3-B) alors verser tout le contenu de A
dans B.
8. Si B non vide et B <= (4-A) alors verser tout le contenu de B
dans A.
Backtracking
Application 2 : Problèmes des cruches d'eau.
• La technique de backtracking consiste à appliquer les règles de 1 à
8, dans cet ordre, pour chaque nouvel état visité.
• La flèche verticale descendante désigne les nouveaux états, les
flèches montantes désignent les retours arrières vers les états déjà
visités.
Backtracking
Backtracking
Application 3 :Sortie d'un labyrinthe
• Le problème consiste, une fois rentré dans le labyrinthe, de sortir
de celui-ci. On suppose, ici, qu'il y a une seule entrée et une seule
sortie.
Backtracking
Backtracking
Application 3 :Sortie d'un labyrinthe
• Déplacements possibles :
1. vers le droite
2. vers le bas
3. vers le haut
4. vers la gauche
• Trouver l'algorithme.