Taquin et l'algorithme A*

Version imprimable

27/12/2007, 13h19
husobom

Taquin et l'algorithme A*

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...
27/12/2007, 21h00
Garulfo

Citation:

Envoyé par husobom

Bonjour, [...]Si vous pouviez m'aider ça serait super sympa, merci...

Je peux t'aider. Mais pour ça il faut que tu poses des questions qui montrent que tu as avancée.

Pour la définition d'heuristique, c'est une méthode approximative qui pourrait donner une mauvaise réponse (non optimale, voire fausse) dans certains cas. C'est donc différent d'un algorithme dans le sens où il y a des « trous » dans lequel ton programme peut tomber.

Pour le reste, si tu as des questions, on les attends ;)
27/12/2007, 22h48
husobom

Ben les questions, ça serait de pouvoir faire l'exercice. déjà un indice pour la question 1, et ensuite l'heuristique h0, je comprends pas à quoi ça correspond.
28/12/2007, 16h30
Garulfo

Citation:

Envoyé par husobom

Ben les questions, ça serait de pouvoir faire l'exercice. déjà un indice pour la question 1, et ensuite l'heuristique h0, je comprends pas à quoi ça correspond.

Sais-tu ce qu'est un système de production permettant de passer de l'un à l'autre ? Si oui, essayes d'en fournir un, sinon oublie l'exercice le temps que tu ais rattrapé ton cours peut-être. Ceci vaut pour l'heuristique : commences par rattraper ton cours.