Discussion :

[sn@ke51]

Bonjour a tous,

Alors voila je suis en train de développer une résolution du taquin en C++ avec l'algorithme A*.

J'utilise déjà deux heuristiques :

-Celle de manhattan
-Celle du nombre de pièces mal placées...

Ces deux la sont les plus connues, mais j'aimerai utiliser une troisième heuristique...

Connaissez vous une autre heuristique et si oui plus perfectionnée que les deux précédentes?

Merci d'avance

[Twindruff]

Tu peux faire sa somme des distances de manhattan de chaque pièce à leur destination, c'est encore plus efficace que les deux que tu as citées

[sn@ke51]

Tu peux faire sa somme des distances de manhattan de chaque pièce à leur destination, c'est encore plus efficace que les deux que tu as citées

C'est pas ce que fait manhattan?

Dans ma fonction manhattan, je calcule le nombre de deplacements de la piece pour arriver a l'etat final (destination)... Et je le fais pour toutes les pieces et je retourne donc le nombre de coups total...

[khayyam90]

S'il s'agit de prendre d'autres heuristiques, on peut aussi prendre

somme de (pour chaque pièce le nombre de voisins corrects [0,1,2,3,4])

[Twindruff]

C'est pas ce que fait manhattan?

Dans ma fonction manhattan, je calcule le nombre de deplacements de la piece pour arriver a l'etat final (destination)... Et je le fais pour toutes les pieces et je retourne donc le nombre de coups total...

ah quand tu as dis "distance de manhattan" tout court j'ai cru que tu faisais la distance de manhattan du vide à sa destination seulement

[sn@ke51]

S'il s'agit de prendre d'autres heuristiques, on peut aussi prendre

somme de (pour chaque pièce le nombre de voisins corrects [0,1,2,3,4])

Ok merci

Je vais faire ca...

Vous connaissez un lien ou il y a toutes les heuristiques pour le taquin?

Merci a tous.

[sn@ke51]

S'il s'agit de prendre d'autres heuristiques, on peut aussi prendre

somme de (pour chaque pièce le nombre de voisins corrects [0,1,2,3,4])

Apres avoir code cette heuristique, le bench est affreux... Elle est 10x plus lente que le nombre de pieces mal placees.

Dommage

[khayyam90]

Je n'ai pas dit qu'elle serait rapide. Elle convient au problème.