Bonjour, alors j'ai un exo de Td sur le taquin que j'aimerais bien comprendre. Bon on va le faire à la rentrée mais j'aimerais bien comprendre avant.
J'ai mi ça dans la partie Lisp car la dernière question doit se faire en lisp
On a les configurations initiale et finale qui sont :
init -- final
2 | 8 | 3 -- 1 | 2 | 3
1 | 6 | 4 -- 8 | 0 | 4
7 | 5 | 0 -- 7 | 6 | 5
et les questions sont les suivantes :
1. Définissez un système de production permettant de passer d'un état à un autre.
2. Considérez chacune des heuristiques suivantes :
- h0(x) = 0
- h1(x) = nombre de pièces mal placées
- h2(x) = somme des déplacements minimum à effectuer pour amener chaque pièce à sa place (somme des distances de Manhattan )
a) A quelle stratégie s'apparente A* lorsque l'heuristique h0 est utilisée
b) Utiliser l'algorithme A* pour résoudre cette instance du taquin, en considérant uniquement l'heuristique h1. Pour cela remplissez le tableau suivant :
Liste Open triée selon f | Liste closed | Etat à développer | valeur g | valeur h | valeur f
c) Ecrire le programme Lisp qui permet de résoudre cette instance du problème, en utilisant h2.
Voila, bon la notion d'heuristique est très floue, j'ai raté le cours sur l'algo A*, et ils avaient fait un exemple, et la même avec le cours, j'ai dû mal à comprendre ( comme toujours pour la théorie ). Si vous pouviez m'aider ça serait super sympa, merci...
Partager