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 .

— Ashwin
źródło

@Ashwin Intuicyjnie, ponieważ gdy algorytm znajduje ścieżkę o długości

, wypróbował już każdą inną ścieżkę, która może mieć długość co najwyżej . Dlatego twoja funkcja heurystyczna nigdy nie może przeceniać kosztów do celu. Spróbuj sam, wykonując funkcję heurystyczną, która może przeceniać.

k

$k$ $k$

— Pål GD

Odpowiedzi:

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 w przestrzeni stanu (w 8 puzzlach oznacza to po prostu dowolną permutację płytek i aktualnie rozważany cel), gdzie 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 jest dopuszczalne, ponieważ sortuje wszystkie węzły w pozycji OTWARTE w porządku rosnącym a także , ponieważ nie zatrzymuje się podczas generowania celu, ale podczas jego rozwijania: $A^*$ $h(n)$ $f(n)=g(n)+h(n)$

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: jest dopuszczalne, więc posiadanie najniższego 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)$
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,

— Carlos Linares López
źródło

Dzięki. Pomogło. Miałeś na myśli jakiś dowód Nilssona i in. Kto to jest? I gdzie mogę znaleźć dowód?

— Ashwin,

@Ashwin Zobacz książkę „ Principles of Artificial Intelligence ” (około strony 80) Nilsa J. Nilssona (1982).

— nbro

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.

wprowadź opis zdjęcia tutaj

Niech i będą odpowiednio węzłem początkowym i bramkowym . Niech będzie oszacowaniem długości ścieżki od węzła do , na wykresie. Ponadto niech będzie funkcją kosztu krokowego od węzła do jego sąsiada , i , 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 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$

h (do) = 4 > do (do, sol) = 2)

$h(C) = 4 > c(C, G) = 2$

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

— Anton
źródło

Dobrze. Ale w jaki sposób dopuszczalna heurystyka zapewnia optymalne rozwiązanie?

— Ashwin

Może się zdarzyć, że - h (b) <h (c) przy jednoczesnym dopuszczalnym obu h (b) i h (c), ale rzeczywista koszt (b)> rzeczywista koszt (c) prawda? Więc b zostanie wybrane jako następna ścieżka, na której tak jak w rzeczywistości c dałby najlepszą ścieżkę.

— Ashwin

W przypadku pierwszego komentarza: dopuszczalna heurystyka zapewnia znalezienie najkrótszej ścieżki. Samo rozwiązanie jest optymalne, jeśli heurystyka jest spójna .

— Anton

W przypadku drugiego komentarza: jeśli heurystyka jest dopuszczalna, A-> B można wybrać dla następnego węzła do rozwinięcia, ale potem A * wybierze A-> C, a nie A-> B-> G. A na końcu skończy się na A-> C-> G.

— Anton

Ponieważ A * działa w ten sposób. Rozszerza węzeł z najmniejszą sumą odległości do tego węzła + ocena heurystyczna z tego węzła. d (A, G) + h (G) = 4 + 0 = 4 oraz d (A, C) + h (C) = 1 + coś <= 2 (ponieważ jest to dopuszczalne). Więc C ma niższą sumę, a A * ją wybierze. W ten sam sposób rozwinie G i znajdzie najmniejszą ścieżkę.

— Anton