Przypuśćmy, że chcę zmienić logikę w A *, próbując znaleźć najbardziej użyteczną ścieżkę (tzn. Ścieżkę o największym zysku) zamiast znaleźć najkrótszą ścieżkę (tj. Tę o najniższym koszcie).

W moim przypadku cel nie jest ustalony jako unikalny węzeł końcowy. Węzeł jest zdefiniowany jako dowolny węzeł posiadający odległośćB od punktu początkowego.

W wersji waniliowej („znalezienie najkrótszej ścieżki”) muszę nie przeceniać kosztu (tj. Znajdować heurystykę mniejszą lub równą rzeczywistemu kosztowi).

W mojej zmodyfikowanej wersji („znalezienie najbardziej użytecznej ścieżki”) krawędzie są oznaczone narzędziem, a nie kosztem i chcę zmaksymalizować ostateczny zysk, biorąc pod uwagę ograniczenie przechodzeniamaksimum krawędzi B. Czy powinienem przecenić narzędzie (tj. Znaleźć heurystykę, która jest większa lub równa rzeczywistej użyteczności), aby A * działało?

EDYTOWAĆ: Bardziej sformalizowany, niech

f(n) = g(n) + h(n)

być użytecznością węzła, składającego się z:

g(n): co zyskuję przechodząc od węzła początkowego donh(n): heurystyka, czyli oszacowanie tego, co zyskuję, przechodzącn do celu (gdzie celem jest węzeł, którego odległość od punktu początkowego jestB)

Powinienh(n) być zawyżonym if(n) być zmaksymalizowanym, aby zidentyfikować najlepszą ścieżkę?

Zauważ, żeB jest budżetem, a zatem może być wydany całkowicie, tzn. nie jest konieczne znalezienie ścieżki krótszej niżB kroki.