Comment une heuristique admissible assure-t-elle une solution optimale?

Lorsque nous utilisons A * (ou tout autre meilleur algorithme de recherche de chemin), nous disons que l'heuristique utilisée doit être admissible , c'est-à-dire qu'elle ne doit jamais surestimer la longueur (ou les déplacements) réels du chemin de la solution.

Comment une heuristique admissible assure-t-elle une solution optimale? Je recherche de préférence une explication intuitive.

Si vous le souhaitez, vous pouvez expliquer en utilisant l' heuristique de distance de Manhattan du 8-puzzle.

Alors que la réponse d'Anton est absolument parfaite, permettez-moi d'essayer de fournir une réponse alternative: être admissible signifie que l'heuristique ne surestime pas l'effort pour atteindre le but, c'est-à-dire pour tout n dans l'espace d'état (dans le casse-tête 8, cela signifie juste pour toute permutation des tuiles et l'objectif que vous envisagez actuellement) où h ∗ ( n ) est le coût optimal pour atteindre la cible.$h(n) \leq h^*(n)$$n$$h^*(n)$

Je pense que la réponse la plus logique pour voir pourquoi fournit des solutions optimales si h ( n ) est admissible est parce qu'il trie tous les nœuds en OUVERT dans l'ordre croissant de f ( n ) = g ( n ) + h ( n ) et, aussi , car il ne s'arrête pas lors de la génération de l'objectif mais lors de son expansion:$A^*$$h(n)$$f(n)=g(n)+h(n)$

1. Comme les nœuds sont développés dans l'ordre croissant de vous savez qu'aucun autre nœud n'est plus prometteur que le nœud actuel. Rappelez-vous: h ( n ) est admissible de sorte que le fait d'avoir le plus bas f ( n ) signifie qu'il a la possibilité d'atteindre l'objectif par un chemin moins cher que les autres nœuds d'OPEN n'ont pas. Et cela est vrai, sauf si vous pouvez prouver le contraire, c'est-à-dire en développant le nœud actuel.$f(n)$$h(n)$$f(n)$
2. Étant donné que ne s'arrête que lorsqu'il développe le nœud cible (comme opposé à l'arrêt lors de sa génération), vous êtes sûr (du premier point ci-dessus) qu'aucun autre nœud ne mène à un chemin moins cher.$A^*$

Et c'est essentiellement tout ce que vous trouverez dans la preuve originale de Nilsson et al.

J'espère que cela t'aides,

Si la fonction heuristique n'est pas admissible, alors nous pouvons avoir une estimation qui est plus grande que le coût réel du trajet d'un nœud à un nœud cible. Si cette estimation de coût de chemin plus élevé se trouve sur le chemin de moindre coût (que nous recherchons), l'algorithme ne l'explorera pas et il peut trouver un autre chemin (pas le moindre coût) vers l'objectif.

Regardez cet exemple simple.

Soit et G respectivement les nœuds de départ et de but . Soit h ( N ) une estimation de la longueur du chemin du nœud N à G , ∀ N dans le graphique. De plus, soit c ( N , X i ) la fonction de coût de pas du nœud N à son voisin X i , ∀ N et i = 1 .. m , où $A$$G$$h(N)$$N$$G$$\forall N$$c(N, X_{i})$$N$$X_i$$\forall N$$i=1..m$$m$est le nombre de voisins de (c'est-à-dire une fonction qui renvoie le coût du bord entre le nœud $N$$N$ et l'un de ses voisins).

Que l'heuristique soit

• $h(B) = 3$

• $h(C) = 4$

Cette fonction heuristique n'est pas admissible, car h ( C ) = 4 > c ( C , G ) = $H$

$A^*$$A$$B$$G$$A \rightarrow B \rightarrow G$$4$$A \rightarrow C \rightarrow G$$3$