Czy odległość na Manhattanie jest monotoniczna, gdy jest używana jako funkcja heurystyczna?

25

Mam mapę opartą na kwadratach. Dozwolony jest tylko ruch poziomy i pionowy (bez przekątnych). Koszt ruchu wynosi zawsze 1.

Wdrażam algorytm A * na tej mapie, używając odległości Manhattan jako heurystyki odległości. Czy to heurystyka jest spójna? Czy mogę uniknąć sprawdzania g(node)węzłów znajdujących się w zestawie ZAMKNIĘTE?

Edycja: Przez konsekwentne mam na myśli monotonię.

tiles path-finding geometry Emiliano
źródło
1
Jeśli twój koszt ruchu jest jednakowy na każdym polu, możesz zastąpić A * Wyszukiwarką Punktów Skoku
Nick Caplinger
Hej, to miło!
Emiliano

Odpowiedzi:

10

Aby odpowiedzieć na twoje pytanie: odległość manhatten jest spójna, gdy jesteś zmuszony poruszać się pionowo / horyzontalnie wzdłuż nieważonej siatki (można to łatwo zilustrować definicją na Wikipedii) . Tak, w twoim przypadku możesz uniknąć ponownego sprawdzania węzłów w zamkniętym zestawie.

Jednak po zezwoleniu na ruch ukośny lub pod dowolnym kątem manhatten odległość staje się niedopuszczalna, ponieważ przecenia koszty diagonalne, co niekoniecznie oznacza, że ​​nie jest spójna.

BlueRaja - Danny Pflughoeft
źródło
Tak, właśnie takiej odpowiedzi szukałem. Byłoby miło wiedzieć, co się stanie, jeśli funkcja heurystyczna jest h(x) = min(manhattan(p1), manhattan(p2))(tj. Albo p1 albo p2 są dobrym punktem końcowym i chcę dotrzeć do najbliższego). Czy to h(x)wciąż monotoniczne?
Emiliano
1
@happy_emi: Tak, jeśli h(x, p1)i h(x, p2)są spójne, to min(h(x,p1), h(x,p2))również będą spójne. Łatwo to pokazać z definicji na Wikipedii (musielibyśmy to pokazać min(h(x, p1), h(x, p2)) <= distance(x,y) + min(h(y, p1), h(y, p2))dla wszystkich węzłów xi yz przewagą między nimi. Teraz załóżmy, że h(x, p1)jest to minimum; czy możesz pokazać, że jest to zdecydowanie <=prawa strona, wykorzystując fakt, że obie heurystyki są spójne?)
BlueRaja - Danny Pflughoeft
31

Tak, odległość między dwoma punktami na Manhattanie jest zawsze taka sama, jak zwykła odległość między nimi. Możesz myśleć o odległości Manhattanu jako składowych X i Y linii biegnącej między dwoma punktami.

Ten obraz ( z Wikipedii ) dobrze to ilustruje:

Manhattan distances

Zielona linia jest rzeczywista odległość.

W niebieski , czerwony i żółty linii oznaczających samej odległości Manhattan (12 jednostek). Bez względu na kombinację ruchów w górę i w prawo rysujesz od lewego dolnego punktu do prawego dolnego rogu, otrzymasz taką samą całkowitą odległość na Manhattanie.

MichaelHouse
źródło
2
Świetna odpowiedź: krótka, słodka, do rzeczy i z ładnym zdjęciem.
Tom „Blue” Piddock
1
Ta odpowiedź jest bliska, ale niepoprawna. Ten obraz nie pokazuje, że odległość na Manhattanie jest spójna (w rzeczywistości, jeśli uważasz zieloną linię za odległość, nie jest ona spójna!) , A także argument, że nie musi ponownie sprawdzać węzłów, ponieważ „odległość Manhattan między dwa punkty są zawsze takie same ” nie dotyczy (stwierdzenie to jest również prawdziwe h(x) = 1000, co oczywiście nie jest spójne) . On może uniknąć ponownego sprawdzenia węzłów, ale tylko dlatego, Manhatten odległość jest zgodna, co ta odpowiedź nie pokazuje.
BlueRaja - Danny Pflughoeft
2
Uważam, że według definicji, którą połączyłeś, odległość na Manhattanie jest spójna. Odległość zielonej linii wykorzystałaby inną heurystykę. Linie czerwona, niebieska i żółta pokazują, że odległość między dwoma węzłami pozostaje taka sama (przy użyciu tej samej heurystyki). Zbliżanie się zmniejsza heurystykę, a oddalanie się zwiększa heurystykę. Spełnia to monotoniczny wymóg PO. Podczas konstruowania wykresu z węzłem na każdym „skrzyżowaniu” odległość na Manhattanie jest spójna. Gdyby to był inny scenariusz (np. Dopuszczenie ruchu po przekątnej), heurystyka byłaby zła.
MichaelHouse
2
Powiedziałem już, że Manhatten Distance jest spójny, ale nie z powodów, o których wspominasz. Twoja odpowiedź nie wykazuje spójności, podobnie jak twój argument w komentarzach. „Spójna / monotoniczna heurystyka” ma precyzyjną definicję (podaną w moim powyższym linku) , która nie jest tym samym co funkcja monotoniczna, dla której wydaje się, że ją mylisz. Stwierdzenie „zbliżenie się zmniejsza heurystykę, a dalsze oddalenie zwiększa heurystykę” nie jest wystarczające, aby wykazać jej spójność, np. 2*manhattenspełnia to, ale nie jest konsekwentne.
BlueRaja - Danny Pflughoeft
3
Nie wiem, dlaczego mówisz, że to nieprawda , wydajesz się nalegać, aby ta odpowiedź była niepełna . Dowód w twojej odpowiedzi wydaje się być równie słaby: „manhatten dystans jest spójny ...”, następnie powtarzasz pierwotne specyfikacje pytania, a następnie, jak byłoby to niedopuszczalne, gdyby scenariusz był inny . Nie czułem się tak, jakby odpowiedź wymagała pełnego matematycznego dowodu. Jeśli uważasz, że to pytanie tego wymaga, prosimy o dołączenie go do swojej odpowiedzi, a ja go zagłosuję. Dzięki za konstruktywną krytykę.
MichaelHouse
6

W odpowiedzi na odpowiedź Byte56 chciałbym zwrócić uwagę, że w twoim konkretnym zbiorze danych użycie Manhattan Distance jako funkcji heurystycznej będzie zawsze zawsze idealną heurystą w tym sensie, że zawsze zwróci rzeczywisty koszt ścieżki (zakładając, że istnieje nic „nie blokuje” ścieżek).

Należy również zauważyć, że wszystkie węzły we właściwym kierunku (poziomo lub pionowo) dają taką samą oczekiwaną odległość (ponieważ istnieje wiele równie krótkich ścieżek do celu). Należy pamiętać, że kolejka priorytetowa (zestaw otwarty) powinna, w przypadku powiązanych priorytetów, najpierw usunąć kolejność dodanego węzła (LIFO - Last In First Out). W ten sposób zbadane zostaną tylko te węzły, które znajdą się na optymalnej ścieżce . Jeśli sprawdzisz równie odpowiednie węzły w trybie FIFO (First In First Out), będziesz skutecznie badać wszystkie węzły, które są częścią najlepszej ścieżki. Ten problem powstaje, ponieważ istnieje wiele równie dobrych ścieżek do węzła celu.

Thorkil Holm-Jacobsen
źródło
„(zakładając, że nic nie blokuje ścieżki)” - to dość duże założenie. Jeśli nic nie blokuje ścieżki, nie trzeba na początku algorytmu znajdowania ścieżki!
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft: To prawda, to była tylko myśl pojawiająca się, gdy patrzy się na obraz Byte56. Reszta jest jednak prawdziwa.
Thorkil Holm-Jacobsen
4

Nie jestem pewien, co rozumiesz przez „zawsze” konsekwentny. Czy odległość Manhattanu na stałej siatce jest niezależna od obranej ścieżki? Tak, jak powiedziała odpowiedź Byte56.

Jednak na przykład odległość Manhattanu nie jest niezmienna w przypadku rotacji. Np. Odległość Manhattanu ( norma L1 ) między punktem początkowym a punktem (10,10)wynosi |10-0| + |10-0| = 20. Jeśli jednak obrócisz swoje współrzędne o 45 stopni (więc teraz twój stały punkt leży wzdłuż jednego z kierunków siatki), znajdziesz teraz ten sam punkt, w którym znajduje się teraz (10sqrt(2),0), a więc odległość Manhattanu do początku 10sqrt(2)~14.14.

dr jimbob
źródło
+1 za wskazanie tego; OTOH, odległość Manhattanu jest niezmienna pod obrotami 90 stopni, które są naprawdę jedynymi, które można wykonać „konsekwentnie” na dyskretnej siatce.
Steven Stadnicki
1
Dobry połów, choć wspomniał, że dozwolony jest tylko ruch poziomy i pionowy.
Thorkil Holm-Jacobsen
1
Pierwotne pytanie dotyczyło zgodności jak w monotonii.
Emiliano