Les algorithmes de recherche avec retour arrière

2 Les algorithmes de recherche avec retour arrière

Exercice 6: recherche de chemins dans un graphe avec circuits

Rechercher tous les chemins dans un graphe avec circuits.

Exemple de graphe:

Un graphe est un ensemble de noeuds(ou sommets) et de relations (ou arcs) entre ces noeuds. Le graphe donné en exemple a pour noeuds: a, b, c, d, e, f, g, h et i. Le noeud début du graphe est a et le noeud fin f. Un chemin commence en a, se termine en f et ne passe jamais 2 fois par le même noeud. Les chemins du graphe donné en exemple sont les suivants:
a b c d e f, a b c i d e f, a c d e f, a c i d e f.

Méthode de résolution:
On construit les chemins un à un, noeud par noeud. Si, à un instant donné, on se trouve au noeud extrémité qui est l'extrémité d'un début de chemin, on le complète en choisissant un des noeuds successeurs de extrémité. Le noeud choisi ne doit pas déjà appartenir au chemin. Si c'est le cas et qu'il n'y a pas d'autre choix possible, on remet en question le choix de extrémité(à retour arrière).

Algorithme informel

fonction rechercherChemin(début_chemin, extrémité, arrivée, graphe)
début
     si extrémité = arrivée alors
         écrire(début_chemin)
     sinon
         pour chaque noeud Î {successeur(extrémité)} et noeud Ï début_chemin
         faire
             rechercherChemin(début_chemin + noeud, noeud, arrivée, graphe)
         fpour
     fsi
fin
Lexique:
     débutchemin: début d'un chemin
     extrémité: noeud extrémité de débutchemin
     graphe: le graphe dans lequel on cherche les chemins
     arrivée: noeud terminal du graphe(f dans l'exemple)
Pour trouver tous les chemins du graphe donné en exemple, on fait l'appel suivant:

rechercherChemin(a, a, f, graphe)

Choix d'une représentation logique du graphe
Première possibilité : Le graphe est représenté par une table dont les indicatifs sont les couples de noeuds et les valeurs vrai ou faux:

I = {(i, j) i,j sont des noeuds } et V = {vrai, faux}

A un couple de noeud (i,j), graphe associe vrai si on peut aller du noeud i au noeud j directement(c'est-à-dire s'il y a un arc de i vers j) et faux sinon.
Le graphe exemple peut être schématisé de la manière suivante:

	a	b	c	d	e	f	g	h	i
a	faux	vrai	vrai	faux	faux	faux	faux	faux	faux
b	faux	faux	vrai	faux	faux	faux	faux	faux	faux
c	faux	faux	faux	vrai	faux	faux	faux	faux	vrai
d	faux	faux	faux	faux	vrai	faux	faux	faux	faux
e	faux	faux	faux	faux	faux	vrai	vrai	faux	faux
f	faux	faux	faux	faux	faux	faux	faux	faux	faux
g	faux	faux	faux	faux	faux	faux	faux	vrai	faux
h	faux	vrai	faux	faux	faux	faux	faux	faux	faux
i	faux	faux	faux	vrai	faux	faux	faux	faux	faux

Un chemin est représenté par une liste de noeuds.
Deuxième possibilité: Le graphe est représenté par une table dont les indicatifs sont les noeuds et les valeurs des listes de noeuds:

I = { Noeud } et V = {liste(Noeud)}

A chaque noeud, graphe associe la liste de ses successeurs.
Ecrire l'algorithme formel en choisissant la première représentation possible.

Corrigé
...

Exercice 7: problème des 8 reines

Placer 8 reines sur un échiquier de façon à ce qu'aucune ne soit en prise avec une autre(même ligne, même colonne, même diagonale).
Supposons que l'on place les reines colonne par colonne. La i^ème reine sera placée dans la i^ème colonne. Soit placerReine(i) la fonction chargée de placer la i^ème reine(pour i de 1 à 8). Si cette fonction tombe en échec, on remet en question les choix précédents. On s'arrête quand toutes les reines sont bien placées.
Algorithme informel

fonction placerReine(i, échiquier): booléen
/* i= numéro de la reine et numéro de la colonne */
début
     si i > 8 alors
         échec   ¬   faux
     sinon
         échec   ¬   vrai
         j   ¬   1 /* numéro de la ligne */
         tant que échec et j < 9 faire
             si la position(j, i) est sûre alors
                 y mettre la reine i
                 échec   ¬  placerReine(i+1, échiquier)
                 si échec alors
                     enlever reine i
                 fsi
             fsi
             j   ¬   j+1
         ftant
     fsi
     retourne échec
fin
Choix des structures de données

pour les lignes: un tableau ligne de 8 booléens tel que:
ligne[j] est vrai s'il y a une reine dans la ligne j
pour les colonnes: un tableau position de 8 entiers tel que:
position[i] est la position(c'est-à-dire le numéro de la ligne) de la reine i dans la colonne i
pour les diagonales:
- un tableau de booléens pour les diagonales gauches, diagauche[2..16]:
  - diagauche[k] est tel que tous les éléments sur la k^ième diagonale gauche ont le même i+j(=k)
  - diagauche[k] est vrai s'il y a une reine sur la k^ième diagonale gauche
- un tableau de booléens pour les diagonales droites, diadroite[-7..7]:
  - diadroite[k] est tel que tous les éléments sur la k^ième diagonale droite ont le même i-j(=k)
  - diadroite[k] est vrai s'il y a une reine sur la k^ième diagonale droite

Corrigé
...