Exploration systématique
de graphes
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.
Exploration en largeur
• Exploration en largeur
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.
Exemple : Passage de 15 à 4 en appliquant un nombre
minimal de fonctions f et g définies par f(x) = 3x et g(x) = x
div 2.
4 = gfg2(15)
Exploration en largeur