Séance 3 — L’IA qui cherche
Formuler un problème, explorer un espace d’états, guider la recherche
Amont. L’agent fondé sur des buts (Séance 1) choisit ses actions selon ce qu’elles lui permettent d’atteindre ; la logique (Séance 2) lui permet de déduire ce qu’il ne perçoit pas. Il lui reste à trouver une suite d’actions qui mène au but.
Aval. Le monde est supposé ici connu avec certitude ; la Séance 5 lève cette hypothèse (probabilités, Bayes), la Séance 6 combine recherche et incertitude. La recherche locale annonce la descente de gradient (Séance 6, puis cours de Machine Learning).
- Formuler un problème de recherche : états, état initial, actions, modèle de transition, coûts, test du but.
- Dérouler à la main BFS, DFS, UCS, la recherche gloutonne et A*, avec la frontière et les états atteints à chaque tour.
- Juger un algorithme de recherche : complétude, optimalité, temps, espace.
- Vérifier qu’une heuristique est admissible et consistante, et dire ce que chaque propriété garantit.
- Concevoir une heuristique par relaxation, et comparer deux heuristiques par dominance (taquin).
- Résoudre le problème des 8 reines par le hill climbing et par le recuit simulé, et mesurer leur taux de succès.
La résolution par la recherche
Le trajet du Magal
Fatou et sa famille partent de Dakar pour le Magal de Touba. Aucune route ne relie directement les deux villes : il faut choisir une suite de routes, et plusieurs suites conviennent, de longueurs très différentes. Un GPS ne « voit » pas le meilleur itinéraire. Il dispose d’une carte, c’est-à-dire d’un modèle du réseau, et l’explore méthodiquement avant que la voiture ne démarre : il essaie des routes sur le papier, compare les longueurs, revient en arrière, et ne propose un itinéraire qu’à la fin de cette exploration.
Quand le monde est observable (l’agent connaît l’état courant), déterministe (chaque action a un effet unique et connu) et connu (l’agent dispose d’un modèle des actions et de leurs coûts), un agent fondé sur des buts peut chercher une solution : il simule les actions sur son modèle jusqu’à trouver une suite d’actions qui mène au but, puis il l’exécute.
Les algorithmes de recherche occupent une place centrale en intelligence artificielle pour trois raisons. D’abord, beaucoup de problèmes se formulent ainsi : le calcul d’un itinéraire, un jeu, la planification d’une suite d’opérations, l’ordonnancement de tâches, la démonstration d’un théorème. Ensuite, ils sont les briques de systèmes plus récents : AlphaGo, qui a battu un champion du monde de go en 2016, combine des réseaux de neurones avec une recherche arborescente. Enfin, ils montrent sur un exemple concret le compromis qui traverse tout le domaine, entre l’optimalité (trouver la meilleure solution), la complétude (trouver une solution dès qu’il en existe une) et l’efficacité (le faire vite et avec peu de mémoire).
Le réseau de la séance
Tous les algorithmes de ce document sont comparés sur un même réseau routier simplifié de dix villes du Sénégal, reliées par douze routes à double sens. Les villes sont placées selon leurs coordonnées GPS ; les longueurs sont des distances routières arrondies au kilomètre. Le départ est Dakar, le but Touba.
| Route | km |
|---|---|
| Dakar – Rufisque | 26 |
| Rufisque – Thiès | 45 |
| Dakar – Mbour | 83 |
| Mbour – Thiès | 64 |
| Thiès – Tivaouane | 24 |
| Tivaouane – Kébémer | 70 |
| Kébémer – Louga | 40 |
| Louga – Saint-Louis | 73 |
| Thiès – Diourbel | 80 |
| Diourbel – Touba | 48 |
| Touba – Louga | 100 |
| Mbour – Diourbel | 120 |
Un même exemple, déroulé par tous les algorithmes, permet de comparer directement ce qu’ils rendent et ce qu’ils coûtent : certains trouveront 199 km, d’autres 251 km, un autre 517 km, et ils ne développeront pas le même nombre de villes pour y parvenir.
La formulation d’un problème de recherche
Les composants d’un problème
Avant de chercher, il faut dire précisément ce qui est cherché. Un GPS a besoin de savoir où il se trouve, quels lieux existent, quelles routes partent de chaque lieu et où elles mènent, ce que coûte chaque route, et à quoi il reconnaît l’arrivée. Ces questions, posées pour n’importe quel problème, donnent les composants d’un problème de recherche.
Un problème de recherche est un sextuplet \(\mathcal P=\big(\mathcal S,\ s_0,\ \mathrm{Actions},\ \mathrm{Résultat},\ c,\ \mathrm{EstBut}\big)\) :
- \(\mathcal S\), l’ensemble des états ; \(s_0\in\mathcal S\), l’état initial ;
- \(\mathrm{Actions}(s)\), l’ensemble des actions applicables dans l’état \(s\) ;
- \(\mathrm{Résultat}(s,a)\), le modèle de transition : l’état obtenu en appliquant l’action \(a\) dans l’état \(s\) ;
- \(c(s,a,s')>0\), le coût d’action ;
- \(\mathrm{EstBut}(s)\), le test du but : vrai si \(s\) est un état but.
États, actions et transitions forment l’espace d’états : un graphe orienté dont les sommets sont les états et les arcs les actions.
Sur le réseau, \(\mathcal S\) est l’ensemble des dix villes et \(s_0=\) Dakar. Les actions applicables à Thiès sont les quatre routes qui en partent ; \(\mathrm{Résultat}(\text{Thiès},\text{vers Diourbel})=\) Diourbel ; le coût d’une action est la longueur de la route en kilomètres ; \(\mathrm{EstBut}(s)\) est vrai si et seulement si \(s=\) Touba.
Formuler, c’est abstraire. L’état « à Thiès » oublie le niveau du carburant, la météo, le péage, le passager qui dort à l’arrière : il ne garde que ce qui sert à décider de la suite. Une formulation trop riche multiplie les états sans rien apporter ; une formulation trop pauvre oublie une contrainte réelle, et la solution trouvée n’est plus exécutable.
Solution et solution optimale
Une solution est une suite d’actions qui mène de \(s_0\) à un état but. Son coût de chemin est la somme des coûts de ses actions. Une solution optimale est une solution de plus petit coût ; ce coût est noté \(C^*\).
Le réseau compte sept chemins sans cycle de Dakar à Touba :
| Chemin sans cycle de Dakar à Touba | Routes | km |
|---|---|---|
| Dakar, Rufisque, Thiès, Diourbel, Touba | 4 | 199 |
| Dakar, Mbour, Diourbel, Touba | 3 | 251 |
| Dakar, Mbour, Thiès, Diourbel, Touba | 4 | 275 |
| Dakar, Rufisque, Thiès, Mbour, Diourbel, Touba | 5 | 303 |
| Dakar, Rufisque, Thiès, Tivaouane, Kébémer, Louga, Touba | 6 | 305 |
| Dakar, Mbour, Thiès, Tivaouane, Kébémer, Louga, Touba | 6 | 381 |
| Dakar, Mbour, Diourbel, Thiès, Tivaouane, Kébémer, Louga, Touba | 7 | 517 |
Le plus court fait \(C^*=199\) km, en 4 routes, par Rufisque, Thiès et Diourbel. Le chemin par Mbour n’a que 3 routes, mais il fait 251 km. Le chemin qui a le moins de routes n’est donc pas celui qui a le moins de kilomètres : cette tension entre nombre d’actions et coût sépare les algorithmes de la suite, selon qu’ils regardent l’un ou l’autre.
Tous les algorithmes de cette séance supposent \(c(s,a,s')>0\). Avec un coût négatif, un cycle de coût total négatif pourrait faire baisser indéfiniment le coût d’un chemin, et la notion de solution optimale n’aurait plus de sens. Les distances, les durées et les consommations vérifient naturellement cette hypothèse.
Espace d’états et arbre de recherche
L’espace d’états est le graphe du problème : dix sommets, douze routes. Un algorithme de recherche ne le parcourt pas directement ; il construit un arbre de recherche, dont la racine est l’état initial et dont chaque nœud représente un chemin depuis la racine. La figure montre les deux premiers niveaux de l’arbre issu de Dakar.
Au niveau 2, Dakar réapparaît deux fois, par un aller-retour vers Mbour ou vers Rufisque : c’est un cycle. Thiès apparaît aussi deux fois, par Mbour et par Rufisque : deux chemins différents mènent au même état, et l’un des deux est redondant. Les cases encadrées en orange sont ces états déjà rencontrés. Un même état peut donc correspondre à plusieurs nœuds de l’arbre, un par chemin qui y mène.
Avec les cycles, l’arbre de recherche est infini, alors que l’espace d’états n’a que dix sommets : Dakar, Rufisque, Dakar, Rufisque… est un chemin valide de longueur arbitraire. Un algorithme doit donc écarter des chemins : soit ceux qui repassent par un état du chemin courant (recherche arborescente, tree search), soit ceux qui mènent à un état déjà atteint (recherche en graphe, graph search).
Le réseau en Python
Le réseau se range dans un dictionnaire de dictionnaires : G[ville][voisine] donne la longueur de la route. Chaque route est rangée une fois dans chaque sens.
ROUTES = [("Dakar", "Rufisque", 26), ("Rufisque", "Thies", 45),
("Dakar", "Mbour", 83), ("Mbour", "Thies", 64),
("Thies", "Tivaouane", 24), ("Tivaouane", "Kebemer", 70),
("Kebemer", "Louga", 40), ("Louga", "Saint-Louis", 73),
("Thies", "Diourbel", 80), ("Diourbel", "Touba", 48),
("Touba", "Louga", 100), ("Mbour", "Diourbel", 120)]
G = {} # G[ville][voisine] = km
for a, b, km in ROUTES: # une route se parcourt dans les deux sens
G.setdefault(a, {})[b] = km
G.setdefault(b, {})[a] = km
def voisins(e): # successeurs dans l'ordre alphabetique
return sorted(G[e].items())
print(len(G), sum(len(v) for v in G.values()) // 2)
print(voisins("Thies"))La sortie est :
10 12
[('Diourbel', 80), ('Mbour', 64), ('Rufisque', 45), ('Tivaouane', 24)]Le dictionnaire compte 10 villes et 12 routes : la somme des tailles des dictionnaires intérieurs vaut 24, et chaque route y figure deux fois. La fonction voisins rend les successeurs d’une ville dans l’ordre alphabétique ; pour Thiès, Diourbel, Mbour, Rufisque et Tivaouane. Cet ordre est une convention de tous les algorithmes de la séance : il fixe l’ordre dans lequel les successeurs entrent dans la frontière, et donc le résultat de DFS et le départage des égalités.
La stratégie générale de recherche
La frontière
Un éclaireur qui avance dans le brouillard ne connaît que la lisière de ce qu’il a déjà découvert ; à chaque pas, il choisit un point de cette lisière, s’y rend et découvre ce qui l’entoure. Les algorithmes de recherche procèdent de même, avec une structure appelée la frontière.
La frontière est l’ensemble des nœuds générés mais pas encore développés. Développer un nœud, c’est générer ses successeurs, c’est-à-dire les nœuds des états qu’une action permet d’atteindre depuis le sien.
Au cours de la recherche, un état passe par trois situations. Il est d’abord inconnu : aucun chemin vers lui n’a encore été généré. Il est ensuite dans la frontière : un nœud qui le contient a été généré comme successeur d’un nœud développé, et attend son tour. Il est enfin développé : son nœud est sorti de la frontière et ses successeurs ont été générés. Un état déjà rencontré, dans la frontière ou développé, est dit atteint.
La recette générique
Tous les algorithmes de ce document suivent la même recette ; ils ne diffèrent que par la règle qui choisit le nœud à retirer de la frontière.
- Frontière \(\leftarrow\{\)racine \(s_0\}\) ; atteints \(\leftarrow\{s_0\}\).
- Tant que la frontière n’est pas vide : en retirer un nœud \(n\), selon la stratégie.
- Si l’état de \(n\) est un but : rendre \(n\) ; le chemin se lit en remontant les parents.
- Sinon, développer \(n\) : chaque successeur non atteint, ou atteint par un chemin plus cher, entre dans la frontière.
- Si la frontière est vide : échec, aucune solution n’existe.
La règle de retrait est tout l’algorithme. Une file (premier entré, premier sorti) donne la recherche en largeur ; une pile (dernier entré, premier sorti) donne la recherche en profondeur ; une file de priorité (le plus petit d’abord) donne, selon la priorité choisie, la recherche à coût uniforme, la recherche gloutonne ou A*.
Le nœud et la reconstruction du chemin
Un nœud porte trois informations : un état, son parent (le nœud dont il est le successeur) et le coût \(g\) du chemin depuis la racine. Le parent permet de retrouver le chemin à la fin de la recherche, en le remontant jusqu’à la racine.
class Noeud:
def __init__(self, etat, parent=None, g=0):
self.etat, self.parent, self.g = etat, parent, g
def __lt__(self, autre): # a priorite egale : ordre alphabetique
return self.etat < autre.etat
def chemin(n): # remonter les parents jusqu'a la racine
etats = []
while n is not None:
etats.append(n.etat); n = n.parent
return etats[::-1]
a = Noeud("Dakar"); b = Noeud("Rufisque", a, 26); c = Noeud("Thies", b, b.g + 45)
print(chemin(c), c.g)La sortie est :
['Dakar', 'Rufisque', 'Thies'] 71Le nœud de Thiès a pour parent celui de Rufisque, dont le parent est celui de Dakar ; son coût vaut \(g=26+45=71\). La fonction chemin remonte la chaîne des parents de Thiès jusqu’à la racine, puis la retourne. La méthode __lt__ compare deux nœuds par l’ordre alphabétique de leurs états : elle départage les égalités de priorité dans les files de priorité de la section 4.
- Les successeurs sont générés dans l’ordre alphabétique ; à priorité égale, l’ordre alphabétique départage.
- Le but est testé à la sortie de la frontière, et non à la génération (section 4.10 pour la raison).
- Les nœuds développés comptés dans la suite sont les nœuds sortis de la frontière, le but compris.
Les paramètres \(b\), \(d\), \(m\) et l’explosion combinatoire
Le coût d’une recherche s’exprime, dans presque tous les cas, avec trois paramètres du problème.
Le facteur de branchement \(b\) (branching factor) est le nombre maximal de successeurs d’un nœud ; \(d\) est le nombre d’actions de la solution la moins profonde ; \(m\) est la longueur maximale d’un chemin dans l’espace d’états.
Sur le réseau, Thiès a quatre voisines et donne \(b=4\) ; le facteur de branchement moyen vaut \(2{,}4\). La solution la moins profonde passe par Mbour, en 3 routes : \(d=3\). Le plus long chemin sans cycle depuis Dakar compte 8 routes : \(m=8\) ; avec les cycles, \(m\) est infini.
Ces paramètres révèlent la difficulté centrale de la recherche : l’explosion combinatoire. Le niveau 0 de l’arbre compte un nœud, le niveau 1 au plus \(b\), le niveau 2 au plus \(b^2\) puisque chacun des \(b\) nœuds du niveau 1 a au plus \(b\) successeurs, et le niveau \(d\) au plus \(b^d\). Le nombre de nœuds croît exponentiellement avec la profondeur.
L’axe vertical est logarithmique : les droites traduisent la croissance exponentielle. Avec \(b=10\), le niveau 6 compte un million de nœuds, le niveau 12 mille milliards. Aucun ordinateur ne parcourt un tel arbre en entier ; tout l’enjeu des algorithmes qui suivent est d’en parcourir le moins possible.
Les quatre critères
Un algorithme est complet s’il trouve une solution dès qu’il en existe une ; il est optimal s’il trouve une solution de coût \(C^*\). Sa complexité en temps compte les nœuds générés ou développés ; sa complexité en espace compte les nœuds gardés en mémoire en même temps (frontière et états atteints). Les deux s’expriment avec \(b\), \(d\), \(m\) et, pour les coûts, avec \(C^*\) et le plus petit coût d’action \(\varepsilon\).
Les deux premiers critères disent si le résultat est correct ; les deux derniers, ce qu’il coûte. Le temps et l’espace portent sur le même objet, la frontière, mais sous deux angles : le temps compte tous les nœuds qui y sont passés, l’espace la taille qu’elle atteint à un instant donné. Un restaurant de thiéboudienne de la Médina peut servir 200 clients dans la journée avec 20 places assises : les clients mangent, partent, et libèrent leur place pour les suivants.
Un algorithme peut visiter beaucoup de nœuds en n’en gardant que peu en mémoire : c’est toute la différence entre la recherche en profondeur et la recherche en largeur (section 4). En pratique, c’est souvent l’espace qui limite : un calcul long finit par aboutir, un programme qui manque de mémoire s’arrête.
La recherche non informée
Une recherche est dite non informée (uninformed) quand elle ne dispose d’aucune information sur la position du but, en dehors du test \(\mathrm{EstBut}\) : elle sait reconnaître Touba, mais ignore dans quelle direction se trouve Touba. Trois stratégies de cette famille sont étudiées : la recherche en largeur, la recherche en profondeur et la recherche à coût uniforme.
La recherche en largeur
Au guichet de la gare routière des Baux maraîchers, le premier voyageur arrivé est le premier servi. La recherche en largeur applique cette règle à la frontière.
La recherche en largeur (breadth-first search, BFS) range la frontière dans une file FIFO (first in, first out) : le nœud sorti est toujours le plus ancien. Elle développe donc tous les nœuds à une action de la racine, puis tous ceux à deux actions, et ainsi de suite, niveau par niveau.
Comme les niveaux sortent dans l’ordre, le premier but qui sort est à la plus petite profondeur possible : BFS minimise le nombre d’actions. Elle n’est optimale en coût que si toutes les actions coûtent autant. Elle est complète dès que \(b\) est fini : chaque niveau est fini, et le niveau \(d\) finit par être atteint.
Exemple pas à pas : BFS de Dakar à Touba
La version suivante est une recherche en graphe : l’ensemble atteint mémorise les états déjà rencontrés, et un successeur n’entre dans la file que s’il n’y est pas encore. Un état est marqué atteint dès sa génération (ligne 10), ce qui évite de mettre deux fois le même état dans la file.
def bfs(depart, but):
frontiere = deque([Noeud(depart)])
atteint = {depart}
while frontiere:
n = frontiere.popleft()
if n.etat == but:
return n
for v, c in voisins(n.etat):
if v not in atteint:
atteint.add(v)
fils = Noeud(v, n, n.g + c)
frontiere.append(fils)
n = bfs("Dakar", "Touba")
print(chemin(n), n.g)La ligne 2 crée la file avec le nœud racine, la ligne 3 marque Dakar comme atteint. Chaque tour de la boucle de la ligne 4 retire la tête de la file (ligne 5), teste le but (lignes 6–7), puis parcourt les voisines dans l’ordre alphabétique (ligne 8) : chaque voisine non atteinte est marquée (ligne 10) et entre en bout de file avec son parent et son coût (lignes 11–12). La table suivante donne l’état de la file et des états atteints à la fin de chaque tour ; en gras, ce qui vient d’y entrer.
| Tour | Sort de la file | File après le tour (tête à gauche) | Atteints |
|---|---|---|---|
| 0 | – | Dakar | Dakar |
| 1 | Dakar | Mbour, Rufisque | Dakar, Mbour, Rufisque |
| 2 | Mbour | Rufisque, Diourbel, Thiès | Dakar, Mbour, Rufisque, Diourbel, Thiès |
| 3 | Rufisque | Diourbel, Thiès | Dakar, Mbour, Rufisque, Diourbel, Thiès |
| 4 | Diourbel | Thiès, Touba | Dakar, Mbour, Rufisque, Diourbel, Thiès, Touba |
| 5 | Thiès | Touba, Tivaouane | Dakar, Mbour, Rufisque, Diourbel, Thiès, Touba, Tivaouane |
| 6 | Touba (but) | Tivaouane | Dakar, Mbour, Rufisque, Diourbel, Thiès, Touba, Tivaouane |
Au tour 1, Dakar sort et ses deux voisines entrent, Mbour avant Rufisque dans l’ordre alphabétique. Au tour 2, Mbour sort, parce qu’il est le plus ancien de la file ; ses voisines sont Dakar, déjà atteint, Diourbel et Thiès, qui entrent en bout de file derrière Rufisque. Au tour 3, Rufisque sort sans rien ajouter : Dakar et Thiès sont déjà atteints. Au tour 4, Diourbel sort et génère Touba, avec Mbour pour parent ; Touba est dans la file, mais il n’est pas encore testé. Au tour 5, Thiès, qui le précède dans la file, sort et ajoute Tivaouane. Au tour 6 enfin, Touba sort de la file : c’est le but, et la fonction rend ce nœud. BFS a développé 6 nœuds.
La figure suivante montre deux états de l’exécution. À gauche, le code, avec en jaune les lignes exécutées pendant le tour ; à droite, la carte : en bleu pâle les états développés, numérotés dans l’ordre de sortie, en orange pâle les états de la frontière, en gris les états non atteints, et cerclé d’orange le nœud qui vient de sortir. La première ligne montre le tour 2 : Mbour sort, Diourbel et Thiès passent à l’orange.
La seconde montre la fin : la ligne 14 écrit le chemin, tracé en trait épais, lu par les parents de Touba : Touba, Diourbel, Mbour, Dakar. Tivaouane est encore dans la frontière ; Tivaouane, Kébémer, Louga et Saint-Louis n’ont jamais été développés.
La sortie est :
['Dakar', 'Mbour', 'Diourbel', 'Touba'] 251BFS rend 251 km, en 3 routes : le chemin qui a le moins de routes, et non le plus court en kilomètres, puisque \(C^*=199\). Si le but était testé à la génération, la recherche s’arrêterait au tour 4, dès que Diourbel génère Touba, après 4 nœuds développés au lieu de 6 ; pour BFS, ce raccourci ne change pas le chemin rendu, car tous les nœuds d’un même niveau ont la même profondeur.
La complexité de BFS
Le coût de BFS se compte niveau par niveau. Dans le pire cas, chaque nœud a \(b\) successeurs et BFS développe tous les niveaux jusqu’à celui du but. Le total est une somme géométrique : \[1+b+b^2+\dots+b^d=\frac{b^{d+1}-1}{b-1}\leq2\,b^d\qquad(b\geq2).\] Le dernier niveau domine : avec \(b=10\) et \(d=5\), l’arbre compte \(111\,111\) nœuds, dont \(100\,000\) au niveau 5. Si le but est testé à la génération, temps et espace sont en \(O(b^d)\) ; s’il l’est à la sortie, comme ici, BFS génère encore les successeurs des nœuds du niveau \(d\) sortis avant le but, et l’on obtient \(O(b^{d+1})\).
L’espace est le vrai problème. BFS est une recherche en graphe : tout nœud généré reste en mémoire, dans la frontière ou dans l’ensemble des atteints. Juste avant d’atteindre le niveau \(d\), la frontière contient tout le « front d’onde » de ce niveau. La table suivante donne, pour \(b=10\), un million de nœuds générés par seconde et un kilo-octet par nœud, le temps et la mémoire d’une recherche complète jusqu’au niveau \(d\).
| \(d\) | Nœuds | Temps | Mémoire |
|---|---|---|---|
| 4 | 11 111 | \(11{,}1\) ms | \(11{,}1\) Mo |
| 6 | \(1{,}11\times10^{6}\) | \(1{,}11\) s | \(1{,}11\) Go |
| 8 | \(1{,}11\times10^{8}\) | \(1{,}85\) min | \(111\) Go |
| 10 | \(1{,}11\times10^{10}\) | \(3{,}09\) h | \(11{,}1\) To |
| 12 | \(1{,}11\times10^{12}\) | \(12{,}9\) jours | \(1{,}11\) Po |
| 14 | \(1{,}11\times10^{14}\) | \(3{,}52\) ans | \(111\) Po |
À \(d=8\), le calcul dure moins de deux minutes, mais il demande 111 Go de mémoire : la mémoire sature bien avant la patience. À \(d=14\), le calcul durerait plus de trois ans. BFS est donc réservée aux problèmes de faible profondeur.
La recherche en profondeur
Dans une pile d’assiettes, la dernière posée est la première reprise. La recherche en profondeur applique cette règle à la frontière.
La recherche en profondeur (depth-first search, DFS) range la frontière dans une pile LIFO (last in, first out) : le nœud sorti est toujours le plus récent. Elle descend le plus loin possible le long d’un chemin, et ne revient en arrière qu’au bout d’une impasse.
La version étudiée est une recherche arborescente : elle n’écarte que les états déjà présents sur le chemin courant, ce qui interdit les cycles sans mémoriser tous les états rencontrés. Les successeurs sont empilés en ordre inverse, de sorte que le premier dans l’ordre alphabétique se retrouve au sommet et sort le premier. DFS ne regarde ni les coûts ni la profondeur : son résultat dépend entièrement de l’ordre des successeurs.
Exemple pas à pas : DFS de Dakar à Touba
def sur_chemin(n, v):
while n is not None:
if n.etat == v:
return True
n = n.parent
return False
def dfs(depart, but):
pile = [Noeud(depart)]
while pile:
n = pile.pop()
if n.etat == but:
return n
fils = [Noeud(v, n, n.g + c)
for v, c in voisins(n.etat)
if not sur_chemin(n, v)]
pile.extend(reversed(fils))
n = dfs("Dakar", "Touba")
print(chemin(n), n.g)La fonction sur_chemin (lignes 1–6) remonte les parents de n et dit si l’état v y figure. La pile part de la racine (ligne 8). Chaque tour retire le sommet (ligne 10), teste le but (lignes 11–12), construit la liste des fils dont l’état n’est pas sur le chemin courant (lignes 13–15), et les empile en ordre inverse (ligne 16). La table donne, à la fin de chaque tour, la pile, du fond au sommet, avec le coût \(g\) de chaque nœud, et le chemin du nœud qui vient de sortir.
| Tour | Sort (\(g\)) | Pile après le tour (sommet à droite), avec \(g\) | Chemin du nœud sorti |
|---|---|---|---|
| 0 | – | Dakar (0) | – |
| 1 | Dakar (0) | Rufisque (26), Mbour (83) | Dakar |
| 2 | Mbour (83) | Rufisque (26), Thiès (147), Diourbel (203) | Dakar, Mbour |
| 3 | Diourbel (203) | Rufisque (26), Thiès (147), Touba (251), Thiès (283) | Dakar, Mbour, Diourbel |
| 4 | Thiès (283) | Rufisque (26), Thiès (147), Touba (251), Tivaouane (307), Rufisque (328) | Dakar, Mbour, Diourbel, Thiès |
| 5 | Rufisque (328) | Rufisque (26), Thiès (147), Touba (251), Tivaouane (307) | Dakar, Mbour, Diourbel, Thiès, Rufisque |
| 6 | Tivaouane (307) | Rufisque (26), Thiès (147), Touba (251), Kébémer (377) | Dakar, Mbour, Diourbel, Thiès, Tivaouane |
| 7 | Kébémer (377) | Rufisque (26), Thiès (147), Touba (251), Louga (417) | Dakar, Mbour, Diourbel, Thiès, Tivaouane, Kébémer |
| 8 | Louga (417) | Rufisque (26), Thiès (147), Touba (251), Touba (517), Saint-Louis (490) | Dakar, Mbour, Diourbel, Thiès, Tivaouane, Kébémer, Louga |
| 9 | Saint-Louis (490) | Rufisque (26), Thiès (147), Touba (251), Touba (517) | Dakar, Mbour, Diourbel, Thiès, Tivaouane, Kébémer, Louga, Saint-Louis |
| 10 | Touba (517) but | Rufisque (26), Thiès (147), Touba (251) | Dakar, Mbour, Diourbel, Thiès, Tivaouane, Kébémer, Louga, Touba |
Au tour 1, Dakar sort ; Rufisque puis Mbour sont empilés, et Mbour, premier dans l’ordre alphabétique, est au sommet. Au tour 2, Mbour sort ; Dakar est sur le chemin et ne revient pas, Diourbel et Thiès sont empilés, Diourbel au sommet. Au tour 3, Diourbel sort ; Thiès et Touba sont empilés, Thiès au sommet : Touba est déjà dans la pile, avec \(g=251\), mais il n’est pas testé tant qu’il n’en sort pas, et DFS s’éloigne vers Thiès. Au tour 4, Thiès sort avec \(g=283\) ; Rufisque et Tivaouane sont empilés, Rufisque au sommet. Après le tour 3, la pile contenait deux nœuds de Thiès (\(g=147\) et \(g=283\)) ; après le tour 4, elle contient deux nœuds de Rufisque (\(g=26\) et \(g=328\)) : en recherche arborescente, un même état peut figurer plusieurs fois, une fois par chemin.
Au tour 5, Rufisque sort, mais ses deux voisines, Dakar et Thiès, sont sur son chemin : c’est une impasse, rien n’est empilé, et le tour suivant reprend au nœud placé dessous, Tivaouane. DFS descend alors par Kébémer et Louga. Au tour 8, Louga empile Touba et Saint-Louis ; Saint-Louis sort au tour 9, deuxième impasse, puisque sa seule voisine, Louga, est sur son chemin. Au tour 10, Touba sort avec \(g=517\) : c’est le but. DFS a développé 10 nœuds, et sa pile n’a jamais contenu plus de 5 nœuds.
La figure montre le tour 4, où Thiès sort, atteint par Mbour et Diourbel avec \(g=283\), puis la fin de l’exécution.
La sortie est :
['Dakar', 'Mbour', 'Diourbel', 'Thies', 'Tivaouane', 'Kebemer', 'Louga', 'Touba'] 517Le chemin rendu traverse sept routes et fait 517 km : DFS rend le premier chemin trouvé, pas le meilleur. Avec l’ordre alphabétique inverse, elle part vers Rufisque, Thiès, Tivaouane, Kébémer et Louga, et rend 305 km en 6 routes, après 7 nœuds développés : un autre résultat, aussi éloigné de l’optimum.
La mémoire de DFS et l’approfondissement itératif
L’atout de DFS est sa mémoire. À tout instant, la pile contient le chemin courant, au plus \(m\) nœuds, et, pour chacun d’eux, les frères qui attendent leur tour, au plus \(b-1\). Sa taille est donc \(O(bm)\). Avec \(b=10\) et \(m=16\), cela représente 161 nœuds, soit 161 ko à un kilo-octet par nœud, contre \(10^{16}\) nœuds pour BFS. Cet avantage n’existe qu’en recherche arborescente : avec un ensemble global des états visités, la mémoire redevient celle de l’espace d’états.
En contrepartie, DFS n’est pas optimale (517 km ici), et elle n’est pas complète sur un espace infini, où elle peut descendre sans fin le long d’une branche qui ne contient pas le but. Sans la vérification du chemin courant, elle tournerait indéfiniment dans un cycle Dakar, Rufisque, Dakar, Rufisque… Son temps, dans le pire cas, est en \(O(b^m)\) : quand \(m\) est bien plus grand que \(d\), DFS peut explorer des branches profondes et inutiles avant de trouver un but peu profond.
L’approfondissement itératif (iterative deepening search, IDS) exécute une recherche en profondeur limitée à la profondeur \(\ell\), pour \(\ell=0,1,2,\dots\), jusqu’à trouver un but. Il est complet si \(b\) est fini, optimal en nombre d’actions, de temps \(O(b^d)\) et de mémoire \(O(bd)\).
IDS combine les deux qualités : il trouve, comme BFS, la solution la moins profonde, avec la mémoire de DFS. Sur Dakar \(\to\) Touba, les quatre itérations sont :
| Limite \(\ell\) | Nœuds | Nœuds sortis, dans l’ordre |
|---|---|---|
| 0 | 1 | Dakar |
| 1 | 3 | Dakar, Mbour, Rufisque |
| 2 | 6 | Dakar, Mbour, Diourbel, Thiès, Rufisque, Thiès |
| 3 | 5 | Dakar, Mbour, Diourbel, Thiès, Touba |
| total | 15 | chemin rendu : Dakar, Mbour, Diourbel, Touba, 251 km |
Les limites 0, 1 et 2 ne contiennent pas Touba ; la limite 3 le trouve par Mbour, et IDS rend le chemin de BFS, 251 km, après 15 nœuds développés en tout. Les niveaux supérieurs sont refaits à chaque itération, mais ce surcoût reste faible, parce que le dernier niveau domine. La table compare les nœuds développés par une recherche complète jusqu’au niveau \(d\) :
| \(b\) | \(d\) | BFS | IDS | IDS / BFS |
|---|---|---|---|---|
| 10 | 5 | 111 111 | 123 456 | \(1{,}11\) |
| 2 | 10 | 2 047 | 4 083 | \(1{,}99\) |
| 3 | 8 | 9 841 | 14 757 | \(1{,}50\) |
Avec \(b=10\), IDS développe \(11\) % de nœuds de plus que BFS ; le surcoût ne devient important que pour un facteur de branchement faible (\(b=2\) : deux fois plus).
La recherche à coût uniforme
BFS et DFS ignorent les coûts. Pour trouver le chemin de moindre coût, il faut développer en priorité les nœuds les moins chers.
La recherche à coût uniforme (uniform-cost search, UCS) range la frontière dans une file de priorité ordonnée par \(g(n)\), le coût du chemin de la racine à \(n\) : elle développe toujours le nœud le moins cher.
Une nouvelle qui partirait de Dakar et se propagerait de ville en ville par la route atteindrait les villes dans l’ordre où UCS les développe : par distance croissante. Deux différences séparent UCS de BFS. D’abord, un état déjà atteint est réinséré dans la frontière si un chemin strictement moins cher y mène : c’est une mise à jour ; l’ancienne entrée reste dans la file de priorité, mais elle est ignorée à sa sortie. Ensuite, le but est testé à la sortie de la frontière, jamais à la génération (section 4.10).
En Python, la file de priorité est un tas binaire du module heapq : heappush insère un élément, heappop retire le plus petit, chacun en \(O(\log n)\). Les éléments sont des couples (priorité, nœud) ; à priorité égale, Python compare les nœuds, donc leurs états, par la méthode __lt__. La fonction meilleur_dabord reçoit la priorité sous forme d’une fonction f(g, v) : la même fonction servira à la recherche gloutonne et à A*.
Exemple pas à pas : UCS de Dakar à Touba
def meilleur_dabord(depart, but, f):
frontiere = [(f(0, depart), Noeud(depart))]
meilleur = {depart: 0}
while frontiere:
_, n = heappop(frontiere)
if n.g > meilleur[n.etat]:
continue
if n.etat == but:
return n
for v, c in voisins(n.etat):
g = n.g + c
if v in meilleur and g >= meilleur[v]:
continue
meilleur[v] = g
fils = Noeud(v, n, g)
heappush(frontiere, (f(g, v), fils))
f = lambda g, v: g # UCS
n = meilleur_dabord("Dakar", "Touba", f)
print(chemin(n), n.g)Le tas part de la racine, de priorité \(f(0,\text{Dakar})\) (ligne 2), et le dictionnaire meilleur garde, pour chaque état atteint, le plus petit coût connu (ligne 3). Chaque tour retire le couple de plus petite priorité (ligne 5) ; si ce nœud a été battu depuis son insertion par un chemin moins cher, il est périmé et ignoré (lignes 6–7). Après le test du but (lignes 8–9), chaque voisine reçoit le coût \(g\) du chemin qui passe par \(n\) (ligne 11) ; elle est écartée si elle a déjà un coût au moins aussi bon (lignes 12–13), sinon son meilleur coût est mis à jour et un nouveau nœud entre dans le tas (lignes 14–16). Pour UCS, la priorité est \(g\) lui-même (ligne 17).
| Tour | Sort | Tas après le tour, par \(g\) croissant | Atteints, avec le meilleur \(g\) connu |
|---|---|---|---|
| 0 | – | Dakar 0 | Dakar 0 |
| 1 | Dakar (\(g=0\)) | Rufisque 26, Mbour 83 | Dakar 0, Mbour 83, Rufisque 26 |
| 2 | Rufisque (\(g=26\)) | Thiès 71, Mbour 83 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71 |
| 3 | Thiès (\(g=71\)) | Mbour 83, Tivaouane 95, Diourbel 151 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95 |
| 4 | Mbour (\(g=83\)) | Tivaouane 95, Diourbel 151 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95 |
| 5 | Tivaouane (\(g=95\)) | Diourbel 151, Kébémer 165 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95, Kébémer 165 |
| 6 | Diourbel (\(g=151\)) | Kébémer 165, Touba 199 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95, Kébémer 165, Touba 199 |
| 7 | Kébémer (\(g=165\)) | Touba 199, Louga 205 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95, Kébémer 165, Touba 199, Louga 205 |
| 8 | Touba (\(g=199\)) but | Louga 205 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95, Kébémer 165, Touba 199, Louga 205 |
Au tour 1, Dakar sort et génère Rufisque (26) et Mbour (83). Au tour 2, Rufisque, le moins cher, sort ; il génère Thiès, à \(26+45=71\), et propose Dakar à \(26+26=52\), écarté puisque Dakar est connu à 0. Au tour 3, Thiès sort et génère Tivaouane (95) et Diourbel (151) ; Mbour par Thiès coûterait \(71+64=135\), plus que 83, et Rufisque \(71+45=116\) : tous deux sont écartés. Au tour 4, Mbour sort à 83, mais aucune de ses voisines ne s’améliore : Diourbel par Mbour coûterait \(83+120=203>151\), Thiès \(83+64=147>71\). Le tas ne reçoit rien : UCS a développé Mbour, qui n’est pas sur le meilleur chemin, parce qu’il était moins cher que tout le reste.
Au tour 5, Tivaouane sort à 95 et génère Kébémer (\(95+70=165\)). Au tour 6, Diourbel sort à 151 et génère Touba, à \(151+48=199\). Touba est dans le tas, mais UCS ne s’arrête pas : au tour 7, Kébémer, à 165, est moins cher que Touba et sort d’abord ; il génère Louga (205). Au tour 8 seulement, Touba sort avec \(g=199\) : c’est le but. UCS a développé 8 nœuds. Aucune mise à jour n’a eu lieu sur ce trajet ; la section 4.10 en montre une, sur le trajet retour.
La première figure montre le tour 4 : Mbour sort, et la frontière ne change pas. La seconde montre la fin : le chemin Dakar, Rufisque, Thiès, Diourbel, Touba, et les états développés hors du chemin, Mbour, Tivaouane et Kébémer.
La sortie est :
['Dakar', 'Rufisque', 'Thies', 'Diourbel', 'Touba'] 199UCS rend \(C^*=199\) km : le chemin optimal, en 4 routes.
L’optimalité d’UCS
Quand un nœud \(n\) sort de la frontière d’UCS, \(g(n)\) est le coût minimal pour atteindre son état. En particulier, le premier but qui sort a le coût \(C^*\).
La preuve procède par l’absurde. On suppose qu’un chemin \(P\) mène au même état que \(n\) avec un coût strictement inférieur à \(g(n)\). Soit \(n'\) le premier nœud de \(P\) qui n’a pas encore été développé ; son prédécesseur sur \(P\) l’a été, donc \(n'\) a été généré et se trouve dans la frontière. Les coûts étant positifs ou nuls, le coût de \(n'\) est au plus celui de \(P\) tout entier, donc strictement inférieur à \(g(n)\). Mais alors \(n'\) aurait dû sortir de la file de priorité avant \(n\) : contradiction. Sur le trajet de la section précédente, quand Touba sort à 199, le seul nœud restant dans le tas est Louga, à 205 : tout chemin vers Touba qui passerait par lui coûterait au moins \(205\), plus que 199.
La complexité d’UCS ne s’exprime pas avec la profondeur \(d\), puisque UCS raisonne en coût. Elle développe tous les nœuds de coût inférieur à \(C^*\). Pour traduire ce budget en profondeur, il faut le plus petit coût d’action \(\varepsilon\) : un chemin de \(k\) actions coûte au moins \(k\varepsilon\), donc un chemin de coût au plus \(C^*\) a au plus \(\lfloor C^*/\varepsilon\rfloor\) actions. En comptant la racine, l’arbre exploré a une profondeur d’au plus \(1+\lfloor C^*/\varepsilon\rfloor\), et UCS est complète si les coûts sont au moins \(\varepsilon>0\), avec un temps et un espace en \[O\big(b^{1+\lfloor C^*/\varepsilon\rfloor}\big).\] Ici, \(C^*=199\), \(\varepsilon=24\) (Thiès – Tivaouane) et \(\lfloor199/24\rfloor=8\) : avec \(b=4\), la borne vaut \(4^9=262\,144\) nœuds, pour 8 nœuds réellement développés. La borne est pessimiste, parce qu’elle suppose \(b\) successeurs partout et ignore la recherche en graphe ; elle dit seulement comment le coût croît quand \(\varepsilon\) diminue. Quand toutes les actions coûtent autant, \(C^*/\varepsilon=d\) et l’on retrouve \(O(b^{d+1})\), la complexité de BFS.
UCS est l’algorithme de Dijkstra (1959), avec deux différences : elle s’arrête dès que le but sort, alors que Dijkstra calcule les distances vers tous les sommets, et elle génère le graphe à la demande, à partir de la fonction voisins, sans le connaître en entier.
Le retour du Magal : le moment du test de but
Après le Magal, la famille de Fatou rentre de Touba à Dakar. Le même appel, départ et but échangés, donne :
n = meilleur_dabord("Touba", "Dakar", lambda g, v: g) # le retour du Magal
print(chemin(n), n.g)['Touba', 'Diourbel', 'Thies', 'Rufisque', 'Dakar'] 199Au retour, Mbour, à \(g=48+120=168\), sort avant Rufisque, à \(g=48+80+45=173\). Mbour génère Dakar avec \(g=168+83=251\), et Dakar entre dans le tas. Puis Rufisque sort et propose Dakar à \(173+26=199<251\) : le meilleur coût de Dakar est mis à jour, un nouveau nœud entre dans le tas, et l’ancien, à 251, sera ignoré s’il sort. Une version qui s’arrêterait dès que Dakar est généré rendrait le chemin par Mbour, 251 km. Le premier chemin généré vers le but n’est pas forcément le moins cher.
Le test à la sortie rend 199 km : Touba, Diourbel, Thiès, Rufisque, Dakar. Pour BFS, tester à la génération est sans risque, puisque tous les chemins d’un même niveau ont le même nombre d’actions ; pour UCS et A*, ce raccourci casse l’optimalité.
UCS a ainsi trois forces : la file de priorité sur \(g\), la mise à jour des meilleurs chemins et le test du but à la sortie. Elle a une faiblesse : elle ignore où est le but. Sur Dakar \(\to\) Touba, elle développe Mbour, Tivaouane et Kébémer, hors du chemin, uniquement parce qu’ils sont proches de Dakar. Les coûts négatifs cassent sa preuve ; les coûts nuls peuvent la faire tourner sans fin sur un cycle de coût nul.
La recherche informée
L’heuristique et la distance à vol d’oiseau
Un voyageur qui sait que Touba est à l’est de Dakar ne commence pas par explorer la route de Mbour, au sud. Cette connaissance de la direction du but peut guider la recherche ; une recherche qui l’utilise est dite informée (informed).
Une heuristique \(h(n)\) estime le coût du meilleur chemin de l’état de \(n\) à un but, à partir de cet état seul, sans chercher ; \(h=0\) sur un but. On note \(h^*(n)\) le vrai coût de ce meilleur chemin.
Sur le réseau, une estimation naturelle est la distance à vol d’oiseau jusqu’à Touba. Sur la sphère terrestre, le plus court chemin entre deux points est un arc de grand cercle, dont la longueur se calcule à partir des latitudes \(\varphi\) et des longitudes \(\lambda\), en radians, par la formule de haversine, avec le rayon terrestre \(R=6\,371\) km : \[d=2R\,\arcsin\sqrt{\sin^2\!\Big(\frac{\varphi_2-\varphi_1}{2}\Big)+\cos\varphi_1\cos\varphi_2\,\sin^2\!\Big(\frac{\lambda_2-\lambda_1}{2}\Big)}.\] Pour Dakar et Touba, \(\varphi_1=0{,}25644\), \(\varphi_2=0{,}25918\), \(\varphi_2-\varphi_1=0{,}00274\) et \(\lambda_2-\lambda_1=0{,}02729\). Le premier terme vaut \(1{,}88\times10^{-6}\), le produit des cosinus \(0{,}93499\) et le second sinus carré \(1{,}861\times10^{-4}\) ; la somme vaut \(x=1{,}759\times10^{-4}\), sa racine \(0{,}013263\), et \(d=2\times6\,371\times0{,}013263=169{,}0\) km.
Les valeurs de \(h\)
GPS = {"Dakar": (14.6928, -17.4467), "Rufisque": (14.7167, -17.2667),
"Thies": (14.7910, -16.9256), "Mbour": (14.4198, -16.9640),
"Tivaouane": (14.9500, -16.8167), "Diourbel": (14.6550, -16.2314),
"Touba": (14.8500, -15.8833), "Louga": (15.6181, -16.2244),
"Kebemer": (15.3667, -16.4500), "Saint-Louis": (16.0326, -16.4818)}
def haversine(a, b, R=6371): # distance a vol d'oiseau (km)
(la1, lo1), (la2, lo2) = GPS[a], GPS[b]
p1, p2 = math.radians(la1), math.radians(la2)
dp, dl = p2 - p1, math.radians(lo2 - lo1)
x = math.sin(dp / 2)**2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2)**2
return 2 * R * math.asin(math.sqrt(x))
H = {v: round(haversine(v, "Touba")) for v in GPS}
print(round(haversine("Dakar", "Touba"), 2), H["Mbour"], H["Rufisque"])La sortie est :
169.0 126 149Le dictionnaire H donne, pour chaque ville, la distance à vol d’oiseau jusqu’à Touba, arrondie au kilomètre. La table la compare au vrai coût restant \(h^*\), la longueur du plus court chemin routier jusqu’à Touba ; la dernière ligne donne la marge \(h^*-h\).
| Ville | Dakar | Rufisque | Thiès | Mbour | Tivaouane | Diourbel | Touba | Louga | Kébémer | Saint-Louis |
|---|---|---|---|---|---|---|---|---|---|---|
| \(h\) (km) | 169 | 149 | 112 | 126 | 101 | 43 | 0 | 93 | 84 | 146 |
| \(h^*\) (km) | 199 | 173 | 128 | 168 | 152 | 48 | 0 | 100 | 140 | 173 |
| marge | 30 | 24 | 16 | 42 | 51 | 5 | 0 | 7 | 56 | 27 |
Dakar est à 169 km de Touba à vol d’oiseau, et à 199 km par la route. Mbour, à 126 km, paraît plus proche de Touba que Rufisque, à 149 km : ce détail décide du comportement de la recherche gloutonne.
L’admissibilité
Une heuristique \(h\) est admissible si elle ne surestime jamais le coût restant : \(h(n)\leq h^*(n)\) pour tout nœud \(n\).
Une heuristique admissible est optimiste : elle croit le chemin restant au moins aussi court qu’il ne l’est. La distance à vol d’oiseau est admissible pour une raison géométrique : toute route est une courbe tracée sur la sphère, et l’arc de grand cercle est la plus courte de ces courbes. La figure compare \(h\) et \(h^*\) pour les neuf villes autres que Touba.
La barre orange (\(h\)) ne dépasse jamais la barre bleue (\(h^*\)). La marge minimale, 5 km, se trouve à Diourbel, dont la route vers Touba est presque rectiligne. L’arrondi au kilomètre déplace chaque valeur d’au plus \(0{,}5\) km, moins que la plus petite marge : il ne rend aucune valeur inadmissible.
La recherche gloutonne
La recherche gloutonne (greedy best-first search) est la recette générique avec une file de priorité ordonnée par \(f(n)=h(n)\) : elle développe toujours le nœud qui paraît le plus proche du but.
Le code est celui de la section 4.8 ; seule la priorité de la ligne 17 change.
f = lambda g, v: H[v] # recherche gloutonne
n = meilleur_dabord("Dakar", "Touba", f)
print(chemin(n), n.g)| Tour | Sort | Tas après le tour, par \(h\) croissant | Atteints, avec le meilleur \(g\) connu |
|---|---|---|---|
| 0 | – | Dakar 169 | Dakar 0 |
| 1 | Dakar (\(h=169\)) | Mbour 126, Rufisque 149 | Dakar 0, Mbour 83, Rufisque 26 |
| 2 | Mbour (\(h=126\)) | Diourbel 43, Thiès 112, Rufisque 149 | Dakar 0, Mbour 83, Rufisque 26, Diourbel 203, Thiès 147 |
| 3 | Diourbel (\(h=43\)) | Touba 0, Thiès 112, Rufisque 149 | Dakar 0, Mbour 83, Rufisque 26, Diourbel 203, Thiès 147, Touba 251 |
| 4 | Touba (\(h=0\)) but | Thiès 112, Rufisque 149 | Dakar 0, Mbour 83, Rufisque 26, Diourbel 203, Thiès 147, Touba 251 |
Au tour 1, Dakar sort et génère Mbour (\(h=126\)) et Rufisque (\(h=149\)) : Mbour paraît plus proche de Touba. Au tour 2, Mbour sort et génère Diourbel (\(h=43\)) et Thiès (\(h=112\)) ; Thiès est atteint par Mbour, avec \(g=83+64=147\). Au tour 3, Diourbel sort et génère Touba (\(h=0\)), avec \(g=83+120+48=251\). Au tour 4, Touba sort : c’est le but. La recherche gloutonne n’a développé que 4 nœuds, mais Rufisque, par où passe le chemin optimal, n’a jamais été développé.
La première figure montre le tour 2, où la recherche s’engage vers Mbour ; la seconde, la fin, avec le chemin rendu.
La sortie est :
['Dakar', 'Mbour', 'Diourbel', 'Touba'] 251\(h\) dit ce qui reste à parcourir, pas ce qui a déjà été dépensé. Mbour est à 126 km de Touba à vol d’oiseau, mais l’atteindre coûte 83 km, puis il faut 120 km pour rejoindre Diourbel. La route par Rufisque paraît moins prometteuse, alors qu’elle est 52 km plus courte : 199 km contre 251.
La recherche gloutonne est rapide quand \(h\) guide bien (4 nœuds ici, contre 8 pour UCS), mais elle n’est pas optimale. Elle est complète en recherche en graphe sur un espace fini, mais pas en recherche arborescente, où elle peut osciller entre deux états qui paraissent chacun proches du but. Son temps et son espace sont en \(O(b^m)\) dans le pire cas. La recherche gloutonne oublie \(g\) ; UCS oubliait \(h\). A* additionne les deux.
A* : ce qui est fait, plus ce qui reste
A* est la recette générique avec la priorité \(f(n)=g(n)+h(n)\) : le coût déjà payé jusqu’à \(n\), plus l’estimation de ce qui reste ; \(f(n)\) estime le coût de la meilleure solution qui passe par \(n\).
Un chauffeur de taxi-brousse qui hésite entre deux routes additionne ce que marque déjà le compteur et la distance qui reste à vol d’oiseau. \(g\) empêche A* de s’engager sur un chemin déjà cher, l’erreur de la recherche gloutonne ; \(h\) l’empêche de développer des nœuds qui s’éloignent du but, la lenteur d’UCS. Avec \(h=0\), A* est UCS ; sans \(g\), c’est la recherche gloutonne. L’algorithme a été publié par Hart, Nilsson et Raphael en 1968.
Exemple pas à pas : A* de Dakar à Touba
Dans le code, seule la ligne 17 change encore : la priorité devient \(g+h\).
f = lambda g, v: g + H[v] # A*
n = meilleur_dabord("Dakar", "Touba", f)
print(chemin(n), n.g)| Tour | Sort | Tas après le tour, par \(f\) croissant | Atteints, avec le meilleur \(g\) connu |
|---|---|---|---|
| 0 | – | Dakar 169 | Dakar 0 |
| 1 | Dakar (\(f=0+169=169\)) | Rufisque 175, Mbour 209 | Dakar 0, Mbour 83, Rufisque 26 |
| 2 | Rufisque (\(f=26+149=175\)) | Thiès 183, Mbour 209 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71 |
| 3 | Thiès (\(f=71+112=183\)) | Diourbel 194, Tivaouane 196, Mbour 209 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95 |
| 4 | Diourbel (\(f=151+43=194\)) | Tivaouane 196, Touba 199, Mbour 209 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95, Touba 199 |
| 5 | Tivaouane (\(f=95+101=196\)) | Touba 199, Mbour 209, Kébémer 249 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95, Touba 199, Kébémer 165 |
| 6 | Touba (\(f=199+0=199\)) but | Mbour 209, Kébémer 249 | Dakar 0, Mbour 83, Rufisque 26, Thiès 71, Diourbel 151, Tivaouane 95, Touba 199, Kébémer 165 |
Au tour 1, Dakar sort et génère Rufisque, de priorité \(26+149=175\), et Mbour, de priorité \(83+126=209\) : avec \(g\), Mbour n’est plus le plus prometteur. Au tour 2, Rufisque sort et génère Thiès (\(71+112=183\)). Au tour 3, Thiès sort et génère Diourbel (\(151+43=194\)) et Tivaouane (\(95+101=196\)). Au tour 4, Diourbel sort et génère Touba, de priorité \(199+0=199\). Au tour 5, Tivaouane, à 196, passe devant Touba : il sort et génère Kébémer (\(165+84=249\)). Au tour 6, Touba sort à 199 : c’est le but. A* a développé 6 nœuds, contre 8 pour UCS ; Mbour (209) et Kébémer (249) sont restés dans le tas.
La première figure montre le tour 3, où Thiès sort et où le tas reçoit Diourbel et Tivaouane ; la seconde, la fin.
La sortie est :
['Dakar', 'Rufisque', 'Thies', 'Diourbel', 'Touba'] 199A* rend 199 km, comme UCS, en développant deux nœuds de moins. Le long du chemin optimal, \(f\) vaut 169 (Dakar), 175 (Rufisque), 183 (Thiès), 194 (Diourbel) et 199 (Touba) : il ne décroît jamais, et atteint \(C^*\) au but.
L’optimalité d’A*
L’optimalité d’A* repose sur l’admissibilité. Tant qu’un nœud du chemin optimal reste dans la frontière, son \(f\) est au plus \(C^*\), parce que \(h\) ne surestime pas ; A* le développe donc avant tout but plus cher.
Si \(h\) est admissible, A* en recherche arborescente est optimal.
On suppose qu’un but \(G_2\) sorte avec \(g(G_2)>C^*\). Un nœud \(n\) du chemin optimal est alors dans la frontière, et \[f(n)=g(n)+h(n)\leq g(n)+h^*(n)=C^*<g(G_2)=f(G_2),\] car \(h(G_2)=0\). A* sort toujours le nœud de plus petit \(f\) : \(n\) aurait dû sortir avant \(G_2\), ce qui contredit l’hypothèse.
En recherche en graphe, un état peut être écarté parce qu’il est déjà atteint, alors que le premier chemin trouvé vers lui n’est pas le meilleur. Une propriété plus forte que l’admissibilité garantit que ce cas ne se produit pas.
Une heuristique \(h\) est consistante (ou cohérente, monotone) si, pour tout nœud \(n\) et tout successeur \(n'\) obtenu par l’action \(a\), \[h(n)\leq c(n,a,n')+h(n').\] L’estimation ne peut pas baisser, d’un état à son successeur, de plus que le coût de l’action.
Avec une heuristique consistante, \(f\) ne décroît pas le long d’un chemin : \[f(n')=g(n)+c(n,a,n')+h(n')\geq g(n)+h(n)=f(n).\] Les nœuds sortent donc par \(f\) croissant, et un état sort la première fois avec son coût minimal : l’écarter ensuite est sans risque, et A* en recherche en graphe sans réouverture est optimal. Toute heuristique consistante est admissible : en sommant l’inégalité le long d’un chemin optimal jusqu’au but, où \(h=0\), on obtient \(h(n)\leq h^*(n)\).
Pour une route à double sens, les deux sens de l’inégalité donnent \(|h(a)-h(b)|\leq c(a,b)\). La table vérifie cette condition sur les 12 routes du réseau ; la marge est \(c-|\Delta h|\).
| Route | \(c\) | \(|\Delta h|\) | Marge | Route | \(c\) | \(|\Delta h|\) | Marge |
|---|---|---|---|---|---|---|---|
| Dakar – Rufisque | 26 | 20 | 6 | Kébémer – Louga | 40 | 9 | 31 |
| Rufisque – Thiès | 45 | 37 | 8 | Louga – Saint-Louis | 73 | 53 | 20 |
| Dakar – Mbour | 83 | 43 | 40 | Thiès – Diourbel | 80 | 69 | 11 |
| Mbour – Thiès | 64 | 14 | 50 | Diourbel – Touba | 48 | 43 | 5 |
| Thiès – Tivaouane | 24 | 11 | 13 | Touba – Louga | 100 | 93 | 7 |
| Tivaouane – Kébémer | 70 | 17 | 53 | Mbour – Diourbel | 120 | 83 | 37 |
Les 12 marges sont positives ; la plus faible, 5 km, est celle de Diourbel – Touba. Le résultat était attendu : la distance à vol d’oiseau vérifie l’inégalité triangulaire, et la longueur d’une route est au moins la distance à vol d’oiseau entre ses deux extrémités. L’arrondi au kilomètre n’a cassé aucune marge.
Les nœuds évités par A*
La table donne, pour chaque ville, son vrai coût \(g^*\) depuis Dakar, son heuristique et la valeur \(f=g^*+h\) de son meilleur nœud, rangées par \(f\) croissant, avec les villes développées par UCS et par A*.
| Ville | \(g^*\) | \(h\) | \(f=g^*+h\) | Développée par UCS | par A* |
|---|---|---|---|---|---|
| Dakar | 0 | 169 | 169 | oui | oui |
| Rufisque | 26 | 149 | 175 | oui | oui |
| Thiès | 71 | 112 | 183 | oui | oui |
| Diourbel | 151 | 43 | 194 | oui | oui |
| Tivaouane | 95 | 101 | 196 | oui | oui |
| Touba | 199 | 0 | 199 | oui | oui |
| Mbour | 83 | 126 | 209 | oui | non |
| Kébémer | 165 | 84 | 249 | oui | non |
| Louga | 205 | 93 | 298 | non | non |
| Saint-Louis | 278 | 146 | 424 | non | non |
UCS développe toutes les villes de \(g^*<C^*=199\), dans l’ordre de \(g^*\) ; A* développe les villes de \(f<199\), dans l’ordre de \(f\), puis le but. Mbour (\(f=209\)) et Kébémer (\(f=249\)) sont proches de Dakar, et UCS les développe ; leur \(f\) dépasse 199, et A* les évite. \(f(\text{Mbour})=209\) signifie que tout chemin qui passe par Mbour coûte au moins 209 km, puisque \(h\) ne surestime pas : il est éliminé sans être développé.
A* développe tout nœud de \(f<C^*\) et aucun nœud de \(f>C^*\). Parmi les algorithmes qui garantissent une solution optimale, développent les chemins depuis la racine et n’utilisent que la même heuristique consistante, aucun ne développe moins de nœuds qu’A*, aux égalités \(f=C^*\) près.
La conception d’une heuristique
La qualité d’A* dépend de celle de son heuristique : elle doit être admissible, pour garantir l’optimalité, et proche de \(h^*\), pour réduire le nombre de nœuds développés. Une méthode générale permet de construire de telles heuristiques.
La relaxation
Une relaxation d’un problème s’obtient en retirant des contraintes sur ses actions. Le coût optimal du problème relâché est une heuristique admissible du problème d’origine.
La raison tient en une phrase : toute solution du problème d’origine reste permise dans le problème relâché, qui offre en plus d’autres solutions ; son coût optimal est donc au plus celui du problème d’origine. Sur le réseau, retirer la contrainte « suivre les routes » permet de voler en ligne droite, et le coût optimal du problème relâché est la distance à vol d’oiseau.
Le taquin (8-puzzle) offre un second exemple. Huit tuiles numérotées et une case vide occupent une grille \(3\times3\) ; une action fait glisser une tuile vers la case vide voisine. Une tuile peut passer de la case \(A\) à la case \(B\) si \(A\) et \(B\) sont voisines et si \(B\) est vide. Retirer la condition « \(B\) vide » permet à chaque tuile d’avancer vers sa place sans se soucier des autres : le coût optimal est la somme des distances de Manhattan des tuiles à leur place, notée \(h_2\). Retirer les deux conditions permet à chaque tuile mal placée de sauter à sa place en un coup : le coût optimal est le nombre de tuiles mal placées, noté \(h_1\).
Le problème relâché doit se résoudre sans recherche : si calculer \(h\) demandait une recherche, guider A* coûterait autant que chercher.
Le taquin : \(h_1\) et \(h_2\)
L’état de la figure est à 12 coups du but. Seule la tuile 5 est à sa place : \(h_1=7\). Les distances de Manhattan, en bleu dans chaque case, s’additionnent en \(h_2=10\). Les deux heuristiques sont admissibles, et \(h_2\) est plus proche du vrai coût. Sur cet état, A* sort 61 nœuds avec \(h_1\) et 17 avec \(h_2\), les égalités de \(f\) étant départagées par l’ordre lexicographique de l’état ; l’approfondissement itératif, sans heuristique, en sort \(4\,860\).
Dominance et maximum
Une heuristique \(h_2\) domine une heuristique \(h_1\) si toutes deux sont admissibles et si \(h_2(n)\geq h_1(n)\) pour tout nœud \(n\).
Une tuile mal placée est à au moins une case de sa place ; sa distance de Manhattan vaut donc au moins 1, et \(h_2\geq h_1\) partout : \(h_2\) domine \(h_1\). Avec des heuristiques consistantes, A* avec \(h_2\) ne développe aucun nœud de plus qu’avec \(h_1\), aux nœuds de \(f=C^*\) près : tout nœud de \(f<C^*\) développé avec \(h_2\) l’est aussi avec \(h_1\). Une heuristique dominante guide plus précisément sans compromettre l’optimalité.
Quand plusieurs heuristiques admissibles sont disponibles, sans qu’aucune ne domine les autres, leur maximum les combine : \[h(n)=\max\big(h_1(n),\ h_2(n),\ \dots,\ h_k(n)\big).\] Chaque \(h_i\) minore \(h^*\), donc leur maximum aussi : il est admissible, et il domine chacune d’elles. Sur l’état de la figure, \(\max(7,10)=10\).
Une bonne heuristique est donc admissible, informative (proche de \(h^*\)) et rapide à calculer. \(h^*\) elle-même serait parfaite, mais la calculer revient à résoudre le problème ; tout le travail de conception consiste à approcher \(h^*\) par un calcul bon marché.
Mesures sur un lot de taquins
Pour comparer les heuristiques sur plus d’un état, 50 états ont été tirés au hasard (graine 221) à chaque distance \(d\) du but, tous les états étant pris pour \(d\leq6\) ; IDS a été mesuré jusqu’à \(d=10\). La table donne le nombre moyen de nœuds développés.
| \(d\) | IDS | A* avec \(h_1\) | A* avec \(h_2\) |
|---|---|---|---|
| 4 | 46,6 | 5,1 | 5,0 |
| 6 | 169,8 | 8,3 | 7,1 |
| 8 | 555,1 | 14,1 | 9,6 |
| 10 | 1704,1 | 31,2 | 15,4 |
| 12 | – | 70,7 | 24,3 |
| 14 | – | 171,8 | 39,8 |
| 16 | – | 425,6 | 90,5 |
| 18 | – | 1006,0 | 153,0 |
| 20 | – | 2403,3 | 258,9 |
L’échelle de la figure est logarithmique : IDS croît bien plus vite que les deux versions d’A*, et l’écart entre \(h_1\) et \(h_2\) se creuse avec \(d\). À \(d=20\), \(h_2\) développe 9 fois moins de nœuds que \(h_1\). Le facteur de branchement effectif \(b^*\) résume ces mesures : c’est le facteur de branchement d’un arbre uniforme de profondeur \(d\) qui contiendrait les \(N\) nœuds sortis de la frontière, défini par \(N=1+b^*+\dots+(b^*)^d\). À \(d=20\), il vaut \(1{,}38\) pour \(h_1\) et \(1{,}21\) pour \(h_2\) : plus il est proche de 1, mieux l’heuristique guide.
Une heuristique qui surestime
On pose \(h'(\text{Rufisque})=230\) au lieu de 149. Comme \(230>h^*(\text{Rufisque})=173\) : \(h'\) n’est plus admissible. Après Dakar, \(f(\text{Rufisque})=26+230=256\) et \(f(\text{Mbour})=83+126=209\). Mbour sort, puis Diourbel (\(203+43=246\)), puis Touba, de priorité \(f=g=251<256\) : A* rend 251 km, après 4 nœuds développés, sans avoir développé Rufisque.
Surestimer \(h(\text{Rufisque})\) fait croire que passer par Rufisque est trop cher, et A* l’écarte : le chemin optimal, 199 km, n’est jamais examiné. Plus \(h\) surestime, plus A* ressemble à la recherche gloutonne.
La recherche locale
La recherche sans chemin
Jusqu’ici, tous les algorithmes construisaient un chemin de l’état initial au but. Pour placer 8 reines sur un échiquier sans qu’aucune n’en attaque une autre, ou pour bâtir l’emploi du temps des salles de l’UCAD, le chemin n’a aucune importance : seul l’état final compte.
La recherche locale (local search) garde un seul état complet, l’état courant, et le remplace à chaque pas par l’un de ses voisins, choisi selon un coût \(h\) à minimiser. Elle ne construit pas d’arbre, et sa mémoire est constante.
Un emploi du temps de 20 cours à placer dans 100 créneaux-salles compte \(100^{20}=10^{40}\) affectations, hors de portée de BFS ou d’A*. Le coût d’une affectation est le nombre de conflits, deux cours dans la même salle au même créneau. Déplacer un seul cours donne \(20\times99=1\,980\) voisins : l’évaluation de tous les voisins d’un état prend une fraction de seconde, et l’état courant s’améliore pas à pas.
Le paysage du coût
La figure représente le coût en une dimension, pour le dessin : chaque abscisse est un état, ses voisins sont les abscisses proches. Une descente qui ne voit que ses voisins ressemble à un marcheur dans le brouillard, qui sent la pente sous ses pieds sans voir la vallée. Elle s’arrête au premier creux, un minimum local, ou sur un plateau, où tous les voisins ont le même coût, même si un meilleur état existe plus loin.
Le hill climbing
- \(e\leftarrow\) un état complet tiré au hasard.
- \(v\leftarrow\) le voisin de plus petit \(h\) ; à égalité, le premier dans l’ordre colonne, ligne.
- Si \(h(v)\geq h(e)\) : rendre \(e\) (minimum local ou plateau). Sinon, \(e\leftarrow v\), et retour en (2).
Le nom vient de la version qui maximise un score ; minimiser \(h\) revient à maximiser \(-h\). Pour les 8 reines, un état place une reine dans chaque colonne et donne la ligne de chacune : \(8^8=16\,777\,216\) états. Un voisin s’obtient en déplaçant une reine dans sa colonne : \(8\times7=56\) voisins. Le coût \(h\) est le nombre de paires de reines qui s’attaquent, sur une même ligne ou une même diagonale ; \(h=0\) est une solution.
Chaque case libre porte le \(h\) obtenu en y déplaçant la reine de sa colonne ; le meilleur voisin est encadré en orange. Depuis l’état de départ, \(h\) vaut 6, puis 4, puis 2 ; au troisième échiquier, le meilleur voisin vaut encore 2, et le hill climbing s’arrête sur un plateau, sans solution.
def conflits(e):
return sum(1 for i in range(8) for j in range(i + 1, 8)
if e[i] == e[j] or abs(e[i] - e[j]) == j - i)
def voisins_r(e):
return [e[:c] + (l,) + e[c + 1:] for c in range(8)
for l in range(8) if l != e[c]]
def hill_climbing(e):
h, pas = conflits(e), 0
while h > 0:
v = min(voisins_r(e), key=conflits)
if conflits(v) >= h:
break
e, h, pas = v, conflits(v), pas + 1
return e, h, pas
print(hill_climbing((3, 6, 1, 7, 4, 3, 5, 7)))((2, 6, 1, 7, 0, 3, 5, 7), 2, 2)La fonction conflits compte les paires \((i,j)\) de colonnes dont les reines sont sur la même ligne, ou sur la même diagonale, quand l’écart des lignes égale l’écart des colonnes. voisins_r construit les 56 voisins, et min prend le premier de plus petit coût. Sur le départ de la figure, le hill climbing s’arrête à \(h=2\) après 2 pas, sur l’état (2, 6, 1, 7, 0, 3, 5, 7).
Taux de succès mesurés
Un seul départ ne dit rien de la fiabilité d’un algorithme aléatoire ; il faut mesurer son taux de succès sur un grand nombre de départs.
rng = random.Random(221)
departs = [tuple(rng.randrange(8) for _ in range(8)) for _ in range(1000)]
res = [hill_climbing(e) for e in departs]
ok = [p for _, h, p in res if h == 0]
print(departs[0], len(ok), round(sum(ok) / len(ok), 2))(3, 6, 1, 7, 4, 3, 5, 7) 166 4.2Sur 1 000 départs tirés au hasard (graine 221), dont le premier est celui de la figure, le hill climbing réussit 166 fois, en \(4{,}2\) pas en moyenne. Deux variantes améliorent ce taux sur les mêmes départs.
| Variante (mêmes 1 000 départs) | Succès | En moyenne, par succès |
|---|---|---|
| hill climbing | \(16{,}6\) % | \(4{,}20\) pas |
| hill climbing, au plus 100 pas latéraux consécutifs | \(95{,}3\) % | \(18{,}47\) pas |
| hill climbing avec redémarrages aléatoires | 100 % | \(6{,}58\) lancers |
Un pas latéral accepte un voisin de même coût, pour traverser un plateau ; limité à 100 pas latéraux consécutifs, il porte le taux à \(95{,}3\) %. Les redémarrages aléatoires relancent le hill climbing depuis un nouvel état tiré au hasard jusqu’au succès : le nombre de lancers suit alors une loi géométrique, d’espérance \(1/0{,}166=6{,}02\) ; la mesure donne \(6{,}58\).
Le recuit simulé
Le hill climbing n’accepte jamais une hausse du coût, et c’est ce qui le bloque. Le recuit simulé accepte parfois de remonter, d’autant plus volontiers que la « température » est élevée.
À chaque pas, un voisin \(v\) est tiré au hasard, et \(\Delta E=h(v)-h(e)\). Il est accepté avec la probabilité \[P(\text{accepter }v)=\begin{cases}1 & \text{si }\Delta E\leq0,\\ e^{-\Delta E/T} & \text{si }\Delta E>0,\end{cases}\qquad T_k=T_0\,\alpha^k,\] où la température \(T\) décroît à chaque pas. Chaud, l’algorithme accepte souvent une hausse et explore ; froid, il n’accepte plus que des baisses.
Le nom vient de la métallurgie : un métal chauffé puis refroidi lentement atteint un état de basse énergie (Kirkpatrick, Gelatt et Vecchi, 1983). Avec \(T_0=2\) et \(\alpha=0{,}995\), \(T\) passe sous \(0{,}01\) au pas \(1\,058\). Une hausse \(\Delta E=1\) est acceptée avec la probabilité \(0{,}607\) à \(T=2\), \(0{,}368\) à \(T=1\) et \(0{,}018\) à \(T=0{,}25\).
À gauche, la probabilité d’accepter une hausse, en fonction de \(T\), pour trois amplitudes ; à droite, \(h\) (en noir) et \(T\) (en orange) au fil des pas d’un recuit lancé depuis le même départ que le hill climbing (\(h=6\)). Le recuit accepte 42 hausses, dont une jusqu’à \(h=12\), et atteint \(h=0\) au pas 442, là où le hill climbing restait bloqué à \(h=2\).
def recuit(e, rng, T0=2.0, alpha=0.995, pas_max=3000):
h, T = conflits(e), T0
for k in range(pas_max):
if h == 0:
return e, 0, k
c = rng.randrange(8)
l = rng.randrange(7)
l = l + (l >= e[c]) # une autre ligne que l'actuelle
v = e[:c] + (l,) + e[c + 1:]
dE = conflits(v) - h
if dE <= 0 or rng.random() < math.exp(-dE / T):
e, h = v, h + dE # accepte, meme une hausse
T = T * alpha # refroidissement geometrique
return e, h, pas_max
rng = random.Random(221)
res = [recuit(e, rng) for e in departs]
ok = [k for _, h, k in res if h == 0]
print(len(ok), round(sum(ok) / len(ok), 1))942 791.0Sur les mêmes 1 000 départs, le recuit réussit 942 fois (\(94{,}2\) %), en \(791{,}0\) pas en moyenne. Les lignes 7 et 8 tirent une ligne différente de la ligne actuelle : un nombre de 0 à 6, augmenté de 1 s’il est au moins égal à la ligne actuelle. La ligne 11 accepte toujours une baisse, et une hausse avec la probabilité \(e^{-\Delta E/T}\).
Recherche locale et recherche systématique
| Recherche systématique (BFS, UCS, A*) | Recherche locale (hill climbing, recuit) | |
|---|---|---|
| Construit un chemin | oui | non |
| Mémoire | \(O(b^d)\) ou plus (sauf DFS, IDS) | \(O(1)\) |
| Garantie d’optimalité | oui (UCS, A*) | non |
| Dit qu’aucune solution n’existe | oui, si l’espace est fini | non |
| Espaces immenses | hors de portée | praticable |
| Usage typique | itinéraires, jeux, planification | emplois du temps, configuration, ML |
La recherche locale passe à l’échelle : sur \(16\,777\,216\) états, le hill climbing n’en évalue que 56 par pas. Elle a deux limites. Les minima locaux et les plateaux font échouer le hill climbing dans \(83{,}4\) % des cas ; le recuit dépend de \(T_0\), de \(\alpha\) et du nombre de pas autorisé. Et elle ne dit jamais qu’aucune solution n’existe : elle peut seulement ne pas en trouver.
Elle est omniprésente en Machine Learning. Entraîner un modèle, c’est chercher les valeurs de ses paramètres \(\boldsymbol\theta\) qui minimisent une perte \(J\) ; la descente de gradient, \[\boldsymbol\theta\leftarrow\boldsymbol\theta-\eta\,\nabla J(\boldsymbol\theta),\] est une recherche locale dans l’espace continu des paramètres : à chaque pas, elle se déplace dans la direction où la perte baisse le plus vite, d’un pas de taille \(\eta\). Elle partage les limites du hill climbing, et ses variantes aléatoires partagent l’idée du recuit ; la Séance 6, puis le cours de Machine Learning, la développent.
Synthèse
Les algorithmes côte à côte
| Algorithme | Frontière | Complet | Optimal (coût) | Temps ; espace | km ; nœuds |
|---|---|---|---|---|---|
| BFS | file FIFO | oui (\(b\) fini) | si coûts égaux | \(O(b^{d+1})\) ; \(O(b^{d+1})\) | 251 ; 6 |
| DFS (arbre) | pile LIFO | si espace fini | non | \(O(b^m)\) ; \(O(bm)\) | 517 ; 10 |
| IDS | pile, limite \(0,1,2,\dots\) | oui (\(b\) fini) | si coûts égaux | \(O(b^d)\) ; \(O(bd)\) | 251 ; 15 |
| UCS | priorité \(g\) | oui (coûts \(\geq\varepsilon>0\)) | oui | \(O(b^{1+\lfloor C^*/\varepsilon\rfloor})\) ; idem | 199 ; 8 |
| recherche gloutonne | priorité \(h\) | en graphe fini | non | \(O(b^m)\) ; \(O(b^m)\) | 251 ; 4 |
| A* | priorité \(g+h\) | oui (coûts \(\geq\varepsilon>0\)) | \(h\) admissible\(^{(*)}\) | exponentiel au pire | 199 ; 6 |
| hill climbing | un état | non | non | selon le paysage ; \(O(1)\) | \(16{,}6\) % (reines) |
| recuit simulé | un état | non | non | fixé par \(T_0\), \(\alpha\) ; \(O(1)\) | \(94{,}2\) % (reines) |
La dernière colonne donne, pour Dakar \(\to\) Touba, la longueur du chemin rendu et le nombre de nœuds développés, ou, pour la recherche locale, le taux de succès sur les 8 reines. La complexité de BFS est donnée pour un but testé à la sortie, \(O(b^d)\) s’il est testé à la génération. \(^{(*)}\) En recherche en graphe sans réouverture, A* demande une heuristique consistante. Seuls UCS et A* rendent les 199 km, et A* en développant le moins de nœuds.
Le choix d’un algorithme
Le choix se fait par une suite de questions, posées dans l’ordre.
- Seul l’état final compte ? Recherche locale : hill climbing avec redémarrages, ou recuit, en mesurant le taux de succès.
- Toutes les actions coûtent autant ? BFS si la mémoire le permet, IDS sinon.
- Les coûts diffèrent, sans information sur le but ? UCS.
- Une heuristique admissible existe (consistante en recherche en graphe) ? A*.
- La mémoire d’A* sature ? IDA*, un DFS limité par un seuil sur \(f\), relevé à chaque itération.
IDA* (*iterative deepening A**) fait pour A* ce qu’IDS fait pour BFS. Sur Dakar \(\to\) Touba, ses seuils successifs valent 169, 175, 183, 194, 196 et 199 ; il développe 20 nœuds au lieu de 6, mais ne garde en mémoire que le chemin courant, et rend les 199 km.
Limites d’A* et lien avec l’apprentissage
A* a trois limites. Sa mémoire : il garde tous les nœuds générés, en nombre exponentiel dans le pire cas ; IDA* et RBFS (recursive best-first search) la ramènent à celle de DFS, au prix de calculs refaits. Son heuristique : sans bonne heuristique, A* n’est que UCS, et concevoir une heuristique admissible et informative n’a rien d’automatique. La taille de certains espaces : au go, \(b\approx250\) et \(d\approx150\), et même A* reste hors de portée ; on y combine la recherche, l’échantillonnage et des heuristiques apprises, dans la recherche arborescente Monte-Carlo (Monte-Carlo tree search, MCTS), la méthode d’AlphaGo.
Les algorithmes de cette séance supposent un modèle parfait du monde : les états, les actions et les coûts sont connus. L’apprentissage intervient à deux endroits quand ce n’est plus le cas. D’abord, l’heuristique peut s’apprendre à partir de données plutôt que se concevoir à la main : AlphaGo estime la valeur d’une position par un réseau de neurones entraîné sur des parties. Ensuite, quand les transitions et les coûts sont inconnus, l’agent ne peut plus simuler ses actions ; il doit apprendre en interagissant avec son environnement : c’est l’apprentissage par renforcement (Séance 6).
Exercices corrigés
Les trois exercices suivants reprennent les raisonnements de la séance sous la forme des réponses attendues : un tableau des tours rempli ligne par ligne, une table de vérification de l’heuristique, une trace de recherche locale. Les deux premiers portent sur la carte de Cheikh, coursier à vélo, qui va de la Poste du Plateau (P) à Ouakam (O) ; les autres lieux sont M, C, L et F, et les nombres sont des temps de trajet en minutes. Les valeurs de l’heuristique \(h\), en orange, ne servent qu’à A*. Les conventions sont celles de la séance : successeurs dans l’ordre alphabétique, but testé à la sortie de la frontière, égalités départagées par l’ordre alphabétique.
Exercice 1 : quatre algorithmes sur la carte de Cheikh
- Dérouler BFS de P à O : pour chaque tour, le nœud qui sort, la file après le tour, les états atteints.
- Dérouler DFS (recherche arborescente) : le nœud qui sort, la pile après le tour, le chemin du nœud sorti.
- Dérouler UCS : le nœud qui sort et son coût \(g\), le tas après le tour, le meilleur \(g\) connu de chaque état atteint.
- Dérouler A* avec l’heuristique \(h\) de la carte : mêmes colonnes, la priorité étant \(f=g+h\).
- Comparer les quatre résultats : chemin, nombre d’étapes, minutes, nœuds sortis.
Méthode. Chaque tour applique les mêmes trois gestes de la recette générique : retirer un nœud selon la règle de l’algorithme, tester le but, puis générer ses successeurs. Seule la règle de retrait change : la tête de la file pour BFS, le sommet de la pile pour DFS, le plus petit \(g\) pour UCS, le plus petit \(f=g+h\) pour A*. Dans les tables, la ligne 0 est l’initialisation, et ce qui vient d’entrer dans la frontière est en gras.
(a) BFS. La file contient d’abord P, seul atteint. Au tour 1, P sort ; ses voisins L et M, non atteints, sont marqués et entrent en bout de file dans l’ordre alphabétique. Au tour 2, L, le plus ancien, sort ; P est déjà atteint, C et O entrent derrière M. O est maintenant dans la file, mais le but n’est testé qu’à la sortie. Au tour 3, M sort et seul F, non atteint, entre ; au tour 4, C sort sans rien ajouter, car F, L et M sont tous atteints ; au tour 5, O sort : c’est le but.
| Tour | Sort | File après le tour (tête à gauche) | Atteints |
|---|---|---|---|
| 0 | – | P | P |
| 1 | P | L, M | P, L, M |
| 2 | L | M, C, O | P, L, M, C, O |
| 3 | M | C, O, F | P, L, M, C, O, F |
| 4 | C | O, F | P, L, M, C, O, F |
| 5 | O (but) | F | P, L, M, C, O, F |
Le chemin se lit par les parents : O a pour parent L, L a pour parent P. BFS rend P–L–O, 15 minutes, après 5 nœuds sortis.
(b) DFS. La pile contient d’abord P. Au tour 1, P sort ; ses fils, L et M, sont empilés en ordre inverse, de sorte que L, premier dans l’ordre alphabétique, se retrouve au sommet. Au tour 2, L sort avec \(g=7\) ; P est sur son chemin et n’est pas repris ; O puis C sont empilés, C au sommet. Au tour 3, C sort avec \(g=9\) ; L est sur le chemin ; M (\(g=12\)) et F (\(g=12\)) sont empilés, F au sommet. Au tour 4, F sort avec \(g=12\) ; C est sur le chemin ; O (\(g=14\)) et M (\(g=22\)) sont empilés, M au sommet. Au tour 5, M sort, mais ses trois voisins, C, F et P, sont sur son chemin P–L–C–F–M : c’est une impasse, rien n’est empilé. Au tour 6, O sort avec \(g=14\) : c’est le but.
| Tour | Sort (\(g\)) | Pile après le tour (sommet à droite), avec \(g\) | Chemin du nœud sorti |
|---|---|---|---|
| 0 | – | P 0 | – |
| 1 | P (0) | M 3, L 7 | P |
| 2 | L (7) | M 3, O 15, C 9 | P–L |
| 3 | C (9) | M 3, O 15, M 12, F 12 | P–L–C |
| 4 | F (12) | M 3, O 15, M 12, O 14, M 22 | P–L–C–F |
| 5 | M (22) | M 3, O 15, M 12, O 14 | P–L–C–F–M |
| 6 | O (14) but | M 3, O 15, M 12 | P–L–C–F–O |
En recherche arborescente, DFS ne tient pas d’ensemble des états atteints : la colonne correspondante est remplacée par le chemin du nœud sorti, seuls ses états étant écartés. La pile contient donc plusieurs nœuds d’un même état, par exemple M avec \(g=3\), 12 et 22, un par chemin. DFS rend P–L–C–F–O, 14 minutes, après 6 nœuds sortis ; O (\(g=15\)) était dans la pile dès le tour 2.
(c) UCS. Le tas est rangé par \(g\) croissant. Au tour 1, P sort et génère M (3) et L (7). Au tour 2, M, le moins cher, sort et génère C (\(3+3=6\)) et F (\(3+10=13\)). Au tour 3, C sort avec \(g=6\) et propose F à \(6+3=9<13\) : le meilleur coût de F passe de 13 à 9, et un nouveau nœud de F entre dans le tas ; l’ancien, à 13, sera ignoré s’il sort. Au tour 4, L sort avec \(g=7\) et génère O (\(7+8=15\)). Au tour 5, F sort avec \(g=9\) et propose O à \(9+2=11<15\) : deuxième mise à jour. Au tour 6, O sort avec \(g=11\) : c’est le but. La table ne montre que les entrées valides du tas ; en gras dans la dernière colonne, les coûts qui viennent d’être établis ou améliorés.
| Tour | Sort | Tas après le tour, par \(g\) croissant | Atteints, meilleur \(g\) connu |
|---|---|---|---|
| 0 | – | P 0 | P 0 |
| 1 | P (\(g=0\)) | M 3, L 7 | P 0, L 7, M 3 |
| 2 | M (\(g=3\)) | C 6, L 7, F 13 | P 0, L 7, M 3, C 6, F 13 |
| 3 | C (\(g=6\)) | L 7, F 9 | P 0, L 7, M 3, C 6, F 9 |
| 4 | L (\(g=7\)) | F 9, O 15 | P 0, L 7, M 3, C 6, F 9, O 15 |
| 5 | F (\(g=9\)) | O 11 | P 0, L 7, M 3, C 6, F 9, O 11 |
| 6 | O (\(g=11\)) but | vide | P 0, L 7, M 3, C 6, F 9, O 11 |
En remontant les parents, O a pour parent F, F a pour parent C (depuis la mise à jour), C a pour parent M et M a pour parent P : UCS rend P–M–C–F–O, 11 minutes, après 6 nœuds sortis.
**(d) A*.** Le tas est rangé par \(f=g+h\). Au tour 1, P sort avec \(f=0+9=9\) et génère M (\(f=3+7=10\)) et L (\(f=7+6=13\)). Au tour 2, M sort avec \(f=10\) et génère C (\(6+4=10\)) et F (\(13+2=15\)). Au tour 3, C sort avec \(f=10\) et propose F à \(g=9\) : mise à jour, et F prend la priorité \(9+2=11\). Au tour 4, F sort avec \(f=11\) et génère O (\(11+0=11\)). Au tour 5, O sort : c’est le but.
| Tour | Sort | Tas après le tour, par \(f\) croissant | Atteints, meilleur \(g\) connu |
|---|---|---|---|
| 0 | – | P 9 | P 0 |
| 1 | P (\(f=0+9=9\)) | M 10, L 13 | P 0, L 7, M 3 |
| 2 | M (\(f=3+7=10\)) | C 10, L 13, F 15 | P 0, L 7, M 3, C 6, F 13 |
| 3 | C (\(f=6+4=10\)) | F 11, L 13 | P 0, L 7, M 3, C 6, F 9 |
| 4 | F (\(f=9+2=11\)) | O 11, L 13 | P 0, L 7, M 3, C 6, F 9, O 11 |
| 5 | O (\(f=11+0=11\)) but | L 13 | P 0, L 7, M 3, C 6, F 9, O 11 |
A* rend P–M–C–F–O, 11 minutes, après 5 nœuds sortis : L, de priorité 13, est resté dans le tas.
(e) Comparaison.
| Algorithme | Chemin rendu | Étapes | Minutes | Nœuds sortis | Ordre de sortie |
|---|---|---|---|---|---|
| BFS (file) | P–L–O | 2 | 15 | 5 | P, L, M, C, O |
| DFS (pile) | P–L–C–F–O | 4 | 14 | 6 | P, L, C, F, M, O |
| UCS (priorité \(g\)) | P–M–C–F–O | 4 | 11 | 6 | P, M, C, L, F, O |
| A* (priorité \(g+h\)) | P–M–C–F–O | 4 | 11 | 5 | P, M, C, F, O |
BFS rend le chemin qui a le moins d’étapes (2), mais il dure 15 minutes ; DFS rend le premier chemin qu’il complète, 14 minutes ; UCS et A* rendent l’optimum, \(C^*=11\) minutes, par le chemin à 4 étapes, sur les sept chemins sans cycle de P à O. A* sort un nœud de moins qu’UCS : L, que UCS développe parce que \(g(\text{L})=7\) est petit, alors qu’il s’éloigne d’Ouakam. Sur la carte, les états développés sont en bleu, numérotés dans l’ordre de sortie, et les états restés dans la frontière en orange.
Erreur fréquente. Arrêter la recherche dès que le but entre dans la frontière. BFS rendrait le même chemin, mais UCS s’arrêterait au tour 4, avec O à 15 minutes, et manquerait la mise à jour du tour 5 ; DFS s’arrêterait au tour 2 avec un chemin de 15 minutes.
Exercice 2 : l’heuristique de Cheikh
- Calculer \(h^*\), le vrai coût restant jusqu’à O, en chaque lieu, et vérifier que \(h\) est admissible.
- Vérifier que \(h\) est consistante sur chacune des 8 routes.
- Calculer \(f=g^*+h\) en chaque lieu, où \(g^*\) est le vrai coût depuis P, et expliquer pourquoi A* sort un nœud de moins qu’UCS.
- Dérouler la recherche gloutonne, de priorité \(h\) : chemin rendu, minutes, nœuds sortis.
- On remplace \(h(\text{M})=7\) par \(h'(\text{M})=12\). Dérouler A* avec \(h'\) et conclure.
(a) \(h^*(v)\) est le coût du plus court chemin de \(v\) à O. Il se calcule en partant du but et en remontant, comme une recherche à coût uniforme depuis O : F est à 2 minutes, par la route directe ; C à \(3+2=5\) par F ; L à 8 par la route directe, mais à \(2+5=7\) par C ; M à \(3+5=8\) par C, contre \(10+2=12\) par F ; P à \(3+8=11\) par M, contre \(7+7=14\) par L.
| Lieu | Plus court chemin vers O | \(h^*\) | \(h\) | Marge \(h^*-h\) |
|---|---|---|---|---|
| P | P–M–C–F–O | 11 | 9 | 2 |
| M | M–C–F–O | 8 | 7 | 1 |
| C | C–F–O | 5 | 4 | 1 |
| L | L–C–F–O | 7 | 6 | 1 |
| F | F–O | 2 | 2 | 0 |
| O | – | 0 | 0 | 0 |
Toutes les marges sont positives ou nulles : \(h\leq h^*\) en chaque lieu, et \(h\) est admissible. La marge nulle en F signifie que \(h\) y est exacte.
(b) Pour une route à double sens entre \(a\) et \(b\), les deux inégalités \(h(a)\leq c+h(b)\) et \(h(b)\leq c+h(a)\) s’écrivent ensemble \(|h(a)-h(b)|\leq c\) : la différence des estimations ne dépasse pas la longueur de la route.
| Route | \(c\) | \(|h(a)-h(b)|\) | Marge |
|---|---|---|---|
| P–M | 3 | \(|9-7|=2\) | 1 |
| P–L | 7 | \(|9-6|=3\) | 4 |
| M–C | 3 | \(|7-4|=3\) | 0 |
| M–F | 10 | \(|7-2|=5\) | 5 |
| C–L | 2 | \(|4-6|=2\) | 0 |
| C–F | 3 | \(|4-2|=2\) | 1 |
| L–O | 8 | \(|6-0|=6\) | 2 |
| F–O | 2 | \(|2-0|=2\) | 0 |
Les 8 marges sont positives ou nulles : \(h\) est consistante. Les marges nulles (en gras) marquent les routes où \(h\) baisse exactement du coût de la route ; ce sont M–C et F–O, sur le chemin optimal, et C–L.
(c) Avec une heuristique consistante, A* sort les nœuds par \(f\) croissant et ne sort aucun nœud de \(f>C^*=11\).
| Lieu | \(g^*\) | \(h\) | \(f=g^*+h\) | Sorti par UCS | Sorti par A* |
|---|---|---|---|---|---|
| P | 0 | 9 | 9 | oui | oui |
| M | 3 | 7 | 10 | oui | oui |
| C | 6 | 4 | 10 | oui | oui |
| F | 9 | 2 | 11 | oui | oui |
| O | 11 | 0 | 11 | oui | oui |
| L | 7 | 6 | 13 | oui | non |
Les cinq lieux de \(f\leq11\) sont sortis par A* ; L, avec \(f=7+6=13>11\), ne l’est pas. UCS, qui ne regarde que \(g\), sort L au tour 4 parce que \(g^*(\text{L})=7<11\). \(f(\text{L})=13\) signifie que tout chemin qui passe par L dure au moins 13 minutes, puisque \(h\) ne surestime pas : L est écarté sans être développé.
(d) La recherche gloutonne range le tas par \(h\) seul. P sort, puis L (\(h=6\)) passe devant M (\(h=7\)), puis O (\(h=0\)), généré par L, sort au tour 3. Elle rend P–L–O, 15 minutes, après 3 nœuds sortis : moins de nœuds qu’A*, mais un chemin plus long de 4 minutes, parce que \(h\) dit ce qui reste et oublie \(g\).
(e) \(h'(\text{M})=12>h^*(\text{M})=8\) : \(h'\) surestime en M et n’est plus admissible. Au tour 1, M reçoit la priorité \(3+12=15\) et L la priorité \(7+6=13\) : L sort le premier, et la recherche continue par C (\(9+4=13\)), F (\(12+2=14\)), puis O, de priorité \(14+0=14<15\).
| Tour | Sort | Tas après le tour, par \(f\) croissant | Atteints, meilleur \(g\) connu |
|---|---|---|---|
| 0 | – | P 9 | P 0 |
| 1 | P (\(f=0+9=9\)) | L 13, M 15 | P 0, L 7, M 3 |
| 2 | L (\(f=7+6=13\)) | C 13, M 15, O 15 | P 0, L 7, M 3, C 9, O 15 |
| 3 | C (\(f=9+4=13\)) | F 14, M 15, O 15 | P 0, L 7, M 3, C 9, O 15, F 12 |
| 4 | F (\(f=12+2=14\)) | O 14, M 15 | P 0, L 7, M 3, C 9, O 14, F 12 |
| 5 | O (\(f=14+0=14\)) but | M 15 | P 0, L 7, M 3, C 9, O 14, F 12 |
A* rend P–L–C–F–O, 14 minutes, au lieu de 11 : M, par où passe le chemin optimal, n’a jamais été développé, parce que sa priorité, 15, est restée au-dessus de celle du but. Avec \(h'(\text{M})=10\) ou 11, A* rend encore 11 minutes, mais après avoir développé certains états deux fois : l’admissibilité est la condition qui garantit le résultat, pas celle qui le rend possible.
Erreur fréquente. Vérifier la consistance dans un seul sens. Sur une route à double sens, \(h(a)\leq c+h(b)\) ne vérifie qu’un sens : il faut aussi \(h(b)\leq c+h(a)\), d’où la valeur absolue.
Exercice 3 : le hill climbing sur 4 reines
Quatre reines sont placées une par colonne sur un échiquier \(4\times4\) ; un état donne la ligne de chaque reine, de la colonne 0 à la colonne 3, et le coût \(h\) est le nombre de paires de reines qui s’attaquent.
- Calculer \(h\) pour l’état \((0,1,2,3)\).
- Combien cet état a-t-il de voisins ? Donner le \(h\) de chacun.
- Dérouler le hill climbing depuis \((0,1,2,3)\), à égalité le premier voisin dans l’ordre colonne, ligne, jusqu’à l’arrêt.
- Sur les \(4^4=256\) états de départ possibles, le hill climbing atteint \(h=0\) dans 101 cas. Combien de lancers faut-il en moyenne avec des redémarrages aléatoires ?
- Depuis l’état final de (c), quelle est la probabilité qu’un recuit simulé accepte un voisin de coût \(h=4\), à \(T=1\) ?
(a) La reine de la colonne \(j\) est sur la ligne \(j\) : pour deux colonnes \(i<j\), l’écart des lignes, \(j-i\), égale l’écart des colonnes, et les deux reines sont sur la même diagonale. Les \(\binom42=6\) paires s’attaquent : \(h=6\), la plus grande valeur possible avec 4 reines.
(b) Un voisin déplace une seule reine dans sa colonne, vers l’une des 3 autres lignes : \(4\times3=12\) voisins. La table donne le \(h\) du voisin obtenu en plaçant la reine de chaque colonne sur chaque ligne ; R marque la position actuelle.
| col. 0 | col. 1 | col. 2 | col. 3 | |
|---|---|---|---|---|
| ligne 0 | R | 4 | 5 | 4 |
| ligne 1 | 4 | R | 4 | 5 |
| ligne 2 | 5 | 4 | R | 4 |
| ligne 3 | 4 | 5 | 4 | R |
Sortir une reine de la diagonale supprime ses 3 conflits sur la diagonale, mais peut en créer : déplacer la reine de la colonne 0 sur la ligne 1 donne \(h=4\), sur la ligne 2, \(h=5\).
(c) Le plus petit \(h\) des voisins vaut 4, atteint plusieurs fois ; le premier dans l’ordre colonne, ligne est la reine de la colonne 0 placée sur la ligne 1 : l’état \((1,1,2,3)\), de coût 4. Le même calcul sur ses voisins donne \((1,0,2,3)\), de coût 2. Là, le meilleur voisin vaut encore 2 : aucun voisin n’améliore \(h\), et le hill climbing s’arrête.
| Pas | État | \(h\) | Meilleur voisin | Amélioration |
|---|---|---|---|---|
| 0 | \((0, 1, 2, 3)\) | 6 | 4 | oui |
| 1 | \((1, 1, 2, 3)\) | 4 | 2 | oui |
| 2 | \((1, 0, 2, 3)\) | 2 | 2 | non : arrêt |
L’arrêt a lieu sur \(h=2\), sans solution : les deux solutions des 4 reines sont \((1,3,0,2)\) et \((2,0,3,1)\), et l’état \((1,0,2,3)\) n’est voisin d’aucune.
(d) Chaque lancer depuis un état tiré au hasard réussit avec la probabilité \(p=101/256=0{,}395\), indépendamment des autres : le nombre de lancers jusqu’au premier succès suit une loi géométrique, d’espérance \(1/p=256/101=2{,}53\).
(e) \(\Delta E=4-2=2>0\) : le recuit accepte ce voisin avec la probabilité \(e^{-\Delta E/T}=e^{-2}=0{,}135\) à \(T=1\). Le hill climbing le refuserait toujours ; c’est cette acceptation occasionnelle d’une hausse qui permet au recuit de quitter un minimum local.
Erreur fréquente. Compter \(4\times4=16\) voisins : la reine reste dans sa colonne et change de ligne, ce qui laisse 3 lignes, et non 4, par colonne.
À retenir
- Un problème de recherche est un sextuplet \((\mathcal S,s_0,\mathrm{Actions},\mathrm{Résultat},c,\mathrm{EstBut})\) ; pour Dakar \(\to\) Touba, \(C^*=199\) km.
- Tous les algorithmes suivent une même recette : une frontière, des états atteints, un parent par nœud ; seule la règle de retrait change.
- BFS rend le chemin qui a le moins d’actions (251 km en 3 routes) ; DFS garde une mémoire \(O(bm)\), mais son résultat dépend de l’ordre des successeurs (517 km) ; IDS réunit les deux qualités.
- UCS, de priorité \(g\), avec le test du but à la sortie, est optimale quand les coûts sont positifs (199 km, 8 nœuds).
- Une heuristique est admissible si \(h\leq h^*\), consistante si \(h(n)\leq c(n,a,n')+h(n')\). La recherche gloutonne, de priorité \(h\), est piégée par Mbour (251 km).
- A*, de priorité \(f=g+h\), est optimal avec une heuristique admissible (199 km, 6 nœuds) ; relaxation, dominance et maximum servent à concevoir \(h\).
- La recherche locale améliore un état complet par ses voisins : sur les 8 reines, le hill climbing réussit dans \(16{,}6\) % des cas, le recuit simulé dans \(94{,}2\) %.
Prochaine séance
Après l’évaluation de mi-parcours de la Séance 4, la Séance 5, « L’IA qui doute », lève l’hypothèse d’un monde connu avec certitude et donne à l’agent le langage des probabilités, du théorème de Bayes et des réseaux bayésiens.
Références
- Russell, Norvig — Artificial Intelligence: A Modern Approach, 4e éd., Pearson, 2020 (ch. 3, « Solving Problems by Searching », et ch. 4, « Search in Complex Environments »).
- Poole, Mackworth — Artificial Intelligence: Foundations of Computational Agents, 3e éd., Cambridge University Press, 2023.
- Pearl — Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
- Hart, Nilsson, Raphael — « A Formal Basis for the Heuristic Determination of Minimum Cost Paths », IEEE Transactions on Systems Science and Cybernetics, 1968.
- Dijkstra — « A Note on Two Problems in Connexion with Graphs », Numerische Mathematik, 1959.
- Kirkpatrick, Gelatt, Vecchi — « Optimization by Simulated Annealing », Science, 1983.
Pour cette séance
Les slides
À lire en ligne
À télécharger
- Code de départ du TP (ZIP, 5 Ko)