Tip:
Highlight text to annotate it
X
Tutaj zdobędziecie intuicję dlaczego
optymistyczna heurystyka funkcji h, znajdzie ścieżkę o najmniejszym koszcie.
Kiedy A kończy, zwraca ścieżkę p z estymowanym kosztem c.
Okazuje się, że c jest również rzeczywistym kosztem,
ponieważ u celu funkcja h ma wartość 0
i koszt ścieżki jest całkowitym kosztem szacowanym przez funkcję f.
Wszystkie ścieżki na granicy
mają szacowany koszt większy niż c,
co wiemy ponieważ granica jest rozszerzana w porządku "najtańszy najpierw".
Jeśli h jest optymistyczne, wtedy szacowany koszt
jest mniejszy niż prawdziwy koszt
i ścieżka p musi mieć koszt mniejszy niż rzeczywisty koszt
dowolnej ścieżki w granicy.
Każda ścieżka poza granicą
musi mieć koszt większy
ponieważ krok kosztu jest nie mniejszy niż 0.
To oznacza, że ścieżka p musi być ścieżką o najmniejszym koszcie.
Ten argument, co powinienem powiedzieć, obowiązuje tylko dla
dzrzewa przeszukiwań.
Dla przeszukiwań grafów ten argument jest trochę bardziej skomplikowany,
choć ogólna zasada pozostaje taka sama.