W jaki sposób dopuszczalna heurystyka zapewnia optymalne rozwiązanie?

Używając A * (lub innego algorytmu znajdowania najlepszej ścieżki), mówimy, że zastosowana heurystyka powinna być dopuszczalna , to znaczy nigdy nie powinna przeceniać faktycznej długości ścieżki rozwiązania (lub ruchów).

W jaki sposób dopuszczalna heurystyka zapewnia optymalne rozwiązanie? Najlepiej szukam intuicyjnego wyjaśnienia.

Jeśli chcesz, możesz wyjaśnić za pomocą heurystycznej odległości 8-puzzle na Manhattanie .

Podczas gdy odpowiedź Antona jest absolutnie idealna, postaram się udzielić alternatywnej odpowiedzi: bycie dopuszczalnym oznacza, że ​​heurystyka nie przecenia wysiłku osiągnięcia celu, tj. dla wszystkich n w przestrzeni stanu (w 8 puzzlach oznacza to po prostu dowolną permutację płytek i aktualnie rozważany cel), gdzie h ∗ ( n ) to optymalny koszt osiągnięcia celu.$h(n) \leq h^*(n)$$n$$h^*(n)$

Myślę, że najbardziej logiczną odpowiedzią na pytanie, dlaczego zapewnia optymalne rozwiązania, jeśli h ( n ) jest dopuszczalne, ponieważ sortuje wszystkie węzły w pozycji OTWARTE w porządku rosnącym f ( n ) = g ( n ) + h ( n ), a także , ponieważ nie zatrzymuje się podczas generowania celu, ale podczas jego rozwijania:$A^*$$h(n)$$f(n)=g(n)+h(n)$

1. Ponieważ węzły są rozwijane w porządku rosnącym , wiesz, że żaden inny węzeł nie jest bardziej obiecujący niż obecny. Pamiętaj: h ( n ) jest dopuszczalne, więc posiadanie najniższego f ( n ) oznacza, że ​​ma on możliwość osiągnięcia celu tańszą ścieżką, niż inne węzły w OPEN. I to prawda, chyba że możesz udowodnić coś przeciwnego, tzn. Poprzez rozszerzenie bieżącego węzła.$f(n)$$h(n)$$f(n)$
2. Ponieważ zatrzymuje się tylko wtedy, gdy przechodzi do rozszerzenia węzła celu (w przeciwieństwie do zatrzymania podczas generowania go), masz pewność (od pierwszego punktu powyżej), że żaden inny węzeł nie prowadzi do niego tańszą ścieżką.$A^*$

I to jest zasadniczo wszystko, co znajdziesz w oryginalnym dowodzie Nilssona i in.

Mam nadzieję że to pomoże,

Jeśli funkcja heurystyczna jest niedopuszczalna, wówczas możemy uzyskać oszacowanie, które jest większe niż faktyczny koszt ścieżki z jakiegoś węzła do węzła docelowego. Jeśli oszacowanie kosztu wyższej ścieżki znajduje się na ścieżce o najniższych kosztach (której szukamy), algorytm nie zbada go i może znaleźć inną (nie mniej kosztowną) ścieżkę do celu.

Spójrz na ten prosty przykład.

Niech i G będą odpowiednio węzłem początkowym i bramkowym . Niech h ( N ) będzie oszacowaniem długości ścieżki od węzła N do G , ∀ N na wykresie. Ponadto niech c ( N , X i ) będzie funkcją kosztu krokowego od węzła N do jego sąsiada X i , ∀ N i i = 1 .. m , gdzie $A$$G$$h(N)$$N$$G$$\forall N$$c(N, X_{i})$$N$$X_i$$\forall N$$i=1..m$$m$to liczba sąsiadów (tj. funkcja, która zwraca koszt krawędzi między węzłem N a jednym z jego sąsiadów).$N$$N$

Niech heurystyka będzie

• $h(B) = 3$

• $h(C) = 4$

Ta funkcja heurystyczna jest niedopuszczalna, ponieważ h ( C ) = 4 > c ( C , G ) = $H$

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