TD — Séance 3 — L’IA qui cherche
Formuler, explorer, guider la recherche
Formuler un problème de recherche, dérouler à la main BFS, DFS, IDS, UCS, la recherche gloutonne et A* dans un tableau des tours, juger une heuristique, et tracer un hill climbing. Durée : une séance de TD.
Successeurs générés dans l’ordre alphabétique ; à priorité égale, l’ordre alphabétique départage ; but testé à la sortie de la frontière. Les nœuds sortis sont comptés but compris. Dans un tableau des tours, la ligne 0 est l’initialisation. DFS est en recherche arborescente : il n’écarte que les états du chemin courant.
Exercice 1 : le passeur de Foundiougne
À Foundiougne, un pêcheur doit faire passer d’une rive (G) à l’autre (D) d’un bolong un chacal, une chèvre et un sac de mil. Sa pirogue ne porte que lui et, au plus, l’un des trois. Laissés sans le pêcheur sur une même rive, le chacal mange la chèvre, et la chèvre mange le mil. Chaque traversée coûte 1.
- Un état est noté par un mot de quatre lettres donnant la rive (G ou D) du pêcheur, du chacal, de la chèvre et du mil, dans cet ordre. Donner l’état initial et le test du but.
- Combien d’états ce codage compte-t-il ? Lister les états interdits, en disant pour chacun ce qui s’y passe.
- Donner les actions applicables dans l’état initial et l’état atteint par chacune. Lesquelles mènent à un état sûr ?
- Dérouler BFS depuis l’état initial, en n’engendrant que des états sûrs. Donner, pour chaque profondeur, les états atteints pour la première fois.
- En déduire le nombre de traversées d’une solution la plus courte et le nombre de solutions de cette longueur. Écrire l’une d’elles comme une suite de traversées (« avec la chèvre », « seul »…).
- Donner le plus grand nombre de successeurs sûrs d’un état atteignable, et la profondeur \(d\) de la solution.
Exercice 2 : la carte d’Ousmane — BFS, DFS, IDS
Ousmane, livreur à moto à Ziguinchor, part de l’Escale (E) pour l’Université Assane Seck (U). Les autres quartiers sont Boucotte (B), Kandé (K), Lyndiane (L), Néma (N) et Tilène (T). Les nombres sont des temps de trajet en minutes ; chaque route se parcourt dans les deux sens.
Dérouler BFS de E à U en remplissant le tableau ci-dessous. Donner le chemin rendu, son nombre d’étapes et sa durée.
Tour Sort File après le tour Atteints 0 1 2 3 4 5 6 7 8 Dérouler DFS de E à U. Donner le chemin rendu et sa durée, et la plus grande taille atteinte par la pile.
Tour Sort (\(g\)) Pile après le tour (sommet à droite) Chemin du nœud sorti 0 1 2 3 4 5 6 7 8 Dérouler l’approfondissement itératif (IDS) : pour chaque limite de profondeur \(\ell=0,1,2,\dots\), donner les nœuds sortis dans l’ordre, jusqu’à la limite qui trouve U. Combien de nœuds IDS sort-il au total ? Quel chemin rend-il ?
Limite Nœuds sortis, dans l’ordre Nombre 0 1 2 3 4 Comparer les trois chemins rendus et dire, pour chacun, ce que l’algorithme garantit.
Exercice 3 : la carte d’Ousmane — UCS
Énumérer les chemins sans cycle de E à U avec leur durée, et en déduire \(C^*\).
Dérouler UCS de E à U. Signaler chaque mise à jour d’un meilleur coût.
Tour Sort Tas après le tour Atteints, meilleur \(g\) 0 1 2 3 4 5 6 7 8 Donner le chemin rendu, sa durée et le nombre de nœuds sortis. Expliquer pourquoi U, généré avant le dernier tour, ne sort pas tout de suite.
Un camarade arrête UCS dès que U est généré. Quel chemin rend-il ?
Exercice 4 : une heuristique pour Ousmane
On dispose de l’estimation \(h\) suivante du temps restant jusqu’à U (en orange).
Calculer \(h^*\) en chaque quartier et vérifier que \(h\) est admissible. Où \(h\) est-elle exacte ?
Vérifier la consistance de \(h\) en complétant la table.
Route E–B E–T B–K B–L T–L T–N K–U L–U N–U K–L \(c\) 7 6 12 12 2 5 11 8 7 5 \(|h(a)-h(b)|\) marge Dérouler la recherche gloutonne de E à U (priorité \(h\)) : chemin, durée, nœuds sortis.
Tour Sort Tas après le tour Atteints, meilleur \(g\) 0 1 2 3 4 5 6 7 8 Dérouler A* de E à U (priorité \(f=g+h\)) : chemin, durée, nœuds sortis.
Tour Sort Tas après le tour Atteints, meilleur \(g\) 0 1 2 3 4 5 6 7 8 Calculer \(f=g^*+h\) en chaque quartier, où \(g^*\) est le vrai coût depuis E. Quels quartiers UCS sort-il qu’A* ne sort pas, et pourquoi ?
On remplace \(h(\text{L})=8\) par \(h'(\text{L})=11\). Dérouler A* avec \(h'\) et conclure.
Rassembler, pour BFS, DFS, IDS, UCS, la recherche gloutonne et A*, le chemin, la durée et le nombre de nœuds sortis.
Exercice 5 : trois heuristiques pour un taquin
L’état \(e\) ci-dessous est à 10 coups du but.
- Calculer \(h_1(e)\), le nombre de tuiles mal placées.
- Calculer \(h_2(e)\), la somme des distances de Manhattan, tuile par tuile.
- On définit \(h_3\) comme le nombre de tuiles qui ne sont pas sur leur ligne, plus le nombre de tuiles qui ne sont pas sur leur colonne. Calculer \(h_3(e)\). Montrer que, pour tout état, \(h_1\leq h_3\leq h_2\). De quelle relaxation \(h_3\) est-elle le coût optimal ? En déduire qu’elle est admissible.
- Donner les successeurs de \(e\), avec pour chacun \(h_2\) et \(f=1+h_2\). Lequel A* avec \(h_2\) développe-t-il au tour suivant ?
- Depuis \(e\), A* sort 37 nœuds avec \(h_1\) et 16 avec \(h_2\). Expliquer cet écart par la dominance.
Exercice 6 (approfondissement) : 5 reines
Cinq reines sont placées une par colonne sur un échiquier \(5\times5\) ; un état donne la ligne de chaque reine, de la colonne 0 à la colonne 4, et le coût \(h\) est le nombre de paires de reines qui s’attaquent.
Calculer \(h\) pour l’état \((0,0,0,0,0)\).
Combien un état a-t-il de voisins ? Pour l’état \((0,0,0,0,0)\), donner le \(h\) de chacun dans la grille (une case par ligne et par colonne ; la case de la reine actuelle reste vide).
col. 0 col. 1 col. 2 col. 3 col. 4 ligne 0 ligne 1 ligne 2 ligne 3 ligne 4 Dérouler le hill climbing depuis \((0,0,0,0,0)\), à égalité le premier voisin dans l’ordre colonne, ligne : à chaque pas, l’état, son \(h\) et le meilleur voisin, jusqu’à l’arrêt. L’état final est-il une solution ?
Sur les \(5^5=3\,125\) états de départ, le hill climbing atteint \(h=0\) dans 2 269 cas. Combien de lancers faut-il en moyenne avec des redémarrages aléatoires ?
Un recuit simulé est dans l’état final de (c). Quelle est la probabilité qu’il accepte un voisin de coût 2, puis un voisin de coût 3, à \(T=2\), puis à \(T=0{,}5\) ?
Montrer qu’une heuristique consistante qui vaut 0 sur les buts est admissible.
Pour cette séance
Le cours
Les slides
À lire en ligne
À télécharger
- Code de départ du TP (ZIP, 5 Ko)