Formulation correcte de l'algorithme A *

Question

J'examine les définitions de l'algorithme de recherche de chemin A *, qui semble être défini de manière légèrement différente selon les endroits.

La différence réside dans l'action effectuée lorsque vous passez par les successeurs d'un noeud et que vous trouvez un successeur dans la liste fermée.

• Une approche (proposée par Wikipedia et cet article ) dit: si le successeur est sur la liste fermée, ignorez-le
• Une autre approche (suggestion ici et ici , par exemple) dit: si le successeur est sur la liste fermée, examinez-en le coût. S'il est supérieur au score actuellement calculé, supprimez l'élément de la liste fermée pour un examen ultérieur.

Je suis confus - quelle méthode est correcte? Intuitivement, le premier a plus de sens pour moi, mais je m'interroge sur la différence de définition. L’une des définitions est-elle fausse ou est-ce qu’elle est isomorphe?

Answer 1

La première approche n'est optimale que si le chemin optimal vers un état répété est toujours le premier à suivre. Cette propriété est valable si la fonction heuristique a la propriété cohérence (également appelée monoticité ). Une fonction heuristique est cohérente si, pour chaque nœud n et chaque successeur n ' de n , le coût estimé pour atteindre l'objectif de n n'est pas supérieur au coût en paliers pour accéder à n ' à partir de n , plus le coût estimé pour atteindre l'objectif à partir de n .

La seconde approche est optimale si la fonction heuristique n’est que admissible, c’est-à-dire qu’elle ne surestime jamais le coût pour atteindre l’objectif.

Toute fonction heuristique cohérente est également admissible. Bien que la cohérence soit une exigence plus stricte que l’admissibilité, il faut travailler assez dur pour concevoir des fonctions heuristiques qui sont admissibles mais qui ne sont pas cohérentes.

Ainsi, même si la deuxième approche est plus générale car elle fonctionne avec un sous-ensemble strictement plus grand de fonctions heuristiques, la première approche est généralement suffisante en pratique.

Référence: la sous-section A * recherche: minimisation du coût total estimé de la solution dans la section 4.1 Stratégies de recherche informées (heuristiques) du livre Intelligence artificielle: A Approche moderne .