Discussion :

[antoine_mo]

Bonjour à tous, je viens de terminer (enfin je pense un programme qui résout le fameux Taquin ('8-puzzle') en utilisant le A* pour parcourir le graphe. J'ai vraiment cherché, cherché, mais je n'arrive pas à trouver une réponse claire.

Certains jeux sont solubles, d'autres non, je dirais 'de base' (test des permutations paires et impaires notamment). Quand je teste mon programme avec une map que j'ai créée en partant d'un taquin résolu, tout va bien jusqu'à atteindre une complexité qui fait qu'il ne trouve pas de solution... à une case près ! En fait je me demande si je ne repasse pas par un état connu.... tous les états possibles sont 'fermés'.

Donc ma question : le A* permet-il TOUJOURS de trouver un chemin (à condition que le taquin soit soluble) ou peut-il échouer selon la complexité du puzzle ? Je m'arrache les cheveux sur cette map depuis une semaine....

Merci d'avance
(ps, j'ai bien mis des règles pour tester les poids des états déjà fermés par rapport à un nouveau potentiel).

[Alikendarfen]

Quelle heuristique as-tu utilisé pour évaluer les coûts ?
As-tu écarté des chemins sur la base de cette heuristique ?

Quand tu dis "qu'il ne trouve pas de solution... à une case près !", comment est il possible que seulement une case soit mal placée (et non pas deux) ??

[antoine_mo]

Merci pour cette réponse. J'ai utilisé deux heuristiques (Manhattan et distance euclidienne, soit l'une soit l'autre). Pour ce qui est d'écarter des chemins, je pense que oui, puisque lorsque d'un nœud déjà fermé se représente comme un nœud potentiel avec un poids meilleur, c'est le nouveau que je retiens. De même pour un nœud préalablement ouvert.

Pour information toujours, le sujet mentionnait que le coût d'une transition d'un noeud à l'autre serait de 1. Le G initial est donc de 1, puis incrémenté à chaque parcours de noeud.

Effectivement, pour les cases, j'ai fait un abus de langage : ce n'est pas à une case près, mais à une permutation près (vide et case). A titre d'exemple:

10-2-3-4
15-6-11-8
9-X-7-2
13-14-1-12

passera bien, alors que si j'inverse le X (vide) et le 9 :

10-2-3-4
15-6-11-8
X-9-7-2
13-14-1-12

il ne trouvera pas de chemin. Il semble s'arrêter dans un cas où les noeuds suivants sont tous open ou close, chacun avec un poids inférieur à ce que serait le potentiel des noeuds étudiés.

Je ne veux pas trop poster le code pur et dur, car c'est un sujet assez répandu dans les écoles d'infos et le but n'est pas de faire les devoirs des gens. En tous cas, merci d'avoir étudié la question.