Jak znaleźć najkrótszą ścieżkę z węzłami czasoprzestrzennymi?

To jest przykład tego, co chcę robić za pomocą kodu. Wiem, że możesz użyć wyszukiwania punktu skoku, aby łatwo przejść z zielonego węzła do czerwonego węzła bez problemów, a nawet A *. Ale jak to obliczyć za pomocą osnowy.

Na obrazku widać, że przejście z zielonego węzła do czerwonego węzła zajmuje tylko 8 ruchów podczas podążania niebieską ścieżką. Niebieska ścieżka natychmiast przenosi twoją pozycję z jednego fioletowego węzła do następnego. Pole pośrodku, które kosztuje 2 ruchy, to punkt między dwiema strefami wypaczenia, do którego musisz się przesunąć, aby się do niego dostać.

Wybranie niebieskiej ścieżki jest wyraźnie szybsze, ponieważ wystarczy przesunąć się w połowie (z grubsza) aż do żółtej ścieżki, ale jak mam to zrobić programowo?

Aby rozwiązać ten problem, załóżmy, że wokół wykresu znajduje się wiele fioletowych „wypaczeń”, których możesz użyć, ORAZ wiemy dokładnie, gdzie każdy purpurowy punkt wypaczy się i gdzie są na wykresie.

Niektóre fioletowe osnowy są dwukierunkowe, a niektóre nie, co oznacza, że ​​czasami możesz wejść w osnowę tylko z jednej strony, ale nie wracać po wypaczeniu.

Zastanawiałem się nad rozwiązaniem i doszedłem do wniosku, że będę w stanie obliczyć problem, sprawdzając odległość do każdego punktu wypaczenia (minus punkty jednokierunkowe) oraz różnicę między tymi punktami a punktami w ich pobliżu .

Program musiałby w jakiś sposób dowiedzieć się, że korzystniej jest wziąć drugą warp zamiast iść od pierwszego skoku. Tak więc zamiast przesunąć 6 miejsc, następnie wypaczać, a następnie przesuwać pozostałe 8 kroków pieszo (co jest również szybsze niż w ogóle nie używanie osnowy), zajmie to 6 ruchów, a następnie dwa ruchy do drugiej osnowy.

EDYCJA: Zdałem sobie sprawę, że niebieska ścieżka zajmie 12 ruchów zamiast 8, ale pytanie pozostaje takie samo.

Większość algorytmów wyszukiwania ścieżek jest definiowana za pomocą wykresów, a nie siatek. Na wykresie połączenie między dwoma odległymi węzłami nie jest tak naprawdę problemem.

Musisz jednak zadbać o swoją heurystykę. W przypadku tuneli czasoprzestrzennych minimalna odległość między dwoma węzłami nie jest już odległością euklidesową, a odległość nie spełnia nierówności trójkąta. Taka heurystyka jest niedopuszczalna dla A *. Dlatego nie możesz łatwo użyć A *.

Oczywiście algorytmy wyszukiwania ścieżki, takie jak Dijkstra, które nie używają heurystyki, nadal będą działać. To bardziej przypomina wyszukiwanie z pełną szerokością i wybierze tunele czasoprzestrzenne bez dodatkowego wysiłku. Jednak Dijkstra odwiedzi więcej węzłów niż A * z dobrą heurystyką. (Dijkstra odpowiada A * z heuristic(x) = 0.)

Myślę, że A * zadziała, jeśli użyjesz heurystyki, która traktuje wszystkie wychodzące tunele czasoprzestrzenne jako tunel czasoprzestrzenny bezpośrednio do celu: heurystyka może nie doceniać odległości, ale nigdy nie może jej przeceniać. Tj. Heurystyka byłaby:

def wormhole_heuristic(x):
  return min(euclidean_distance(x, g) for g in [goal, wormholes...])

Aby uzyskać bardzo dokładną heurystykę, możesz (rekurencyjnie) dodać odległość od punktu końcowego tunelu czasoprzestrzennego do celu lub następnego tunelu czasoprzestrzennego. Tj. Jako wstępne obliczenie można wykonać wyszukiwanie ścieżki na (całkowicie połączonym) podgrodzie zawierającym wszystkie tunele czasoprzestrzenne i cel, gdzie odległość między dwoma węzłami jest ich odległością euklidesową. Może to być korzystne, jeśli liczba tuneli czasoprzestrzennych jest znacznie mniejsza niż liczba osiągalnych komórek w sieci. Nowa heurystyka byłaby:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  via_wormhole = min(euclidean_distance(x, w) + wormhole_path_distance(w, goal) for w in wormholes)
  return min(direct, via_wormhole)

Jak wskazuje @Caleth w komentarzach, wszystko to jest bardzo dostrajalne i możemy poprawić heurystykę pierwszego tunelu czasoprzestrzennego bez wykonywania pełnej ścieżki wyszukiwania przez sieć tuneli czasoprzestrzennych, dodając odległość między ostatnim wyjściem tunelu czasoprzestrzennego a celem. Ponieważ nie wiemy, które wyjście z tunelu czasoprzestrzennego zostanie użyte jako ostatnie i nie możemy przeceniać, musimy założyć wyjście najbliższe celowi:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  to_next_wormhole = min(euclidean_distance(x, w) for w in wormholes)
  from_last_wormhole = min(euclidean_distance(w.exit, goal) for w in wormholes)
  via_wormhole = to_next_wormhole + from_last_wormhole
  return min(direct, via_wormhole)

Masz wykres z 6 wierzchołkami na siatce ze współrzędnymi:

A ( 0,0)
B ( 4,7)
C ( 7,4)
D (10,4)
E (16,2)
F (16,0)

Możesz wygenerować pełny wykres na tych wierzchołkach i przypisać koszt każdej krawędzi, gdzie koszt dotyczy MAX( ABS( x1 - x2 ), ABS( y1 - y2 ) )standardowych krawędzi, a koszt 0 dla tuneli czasoprzestrzennych.

To da ci koszty (jako macierz przylegania):

   A  B  C  D  E  F
- -- -- -- -- -- --
A  -  7  7 10 16 16
B  7  -  0  6 12 12
C  7  0  -  3  9  9
D 10  6  3  -  0  6
E 16 12  9  0  -  2
F 16 12  9  6  2  -

Jeśli istnieją wypaczenia jednokierunkowe, wówczas należy tworzyć krawędzie na wykresie (lub macierz przylegania), które idą w tym kierunku, ale nie w przeciwnym kierunku.

Następnie możesz użyć algorytmu Dijkstry z kolejką priorytetową .

Zacznij od Ai popchnij każdą sąsiednią krawędź do kolejki priorytetowej:

Format: (ścieżka: koszt)

queue     = [ (A-B : 7), (A-C : 7), (A-D : 10), (A-E : 16), (A-F : 16) ]

Gdy przedmioty są wypychane do kolejki - śledź minimalny koszt dla każdego wierzchołka i pchaj ścieżki do kolejki tylko wtedy, gdy jest on niższy niż istniejący koszt minimalny.

min-costs = { A: 0, B: 7, C: 7, D: 10, E: 16, F: 16 }

Usuń pierwszy element z kolejki i, jeśli jego koszt nadal odpowiada kosztowi minimalnemu, wepchnij wszystkie ścieżki złożone utworzone przez tę ścieżkę i jej sąsiednie krawędzie z powrotem do kolejki priorytetowej (jeśli ścieżki złożone mają niższy koszt niż istniejące minimum):

Usunąć: (A-B : 7)

• Spróbuj (A-B-A : 14)- odrzuć jako wyższy koszt
• Spróbuj (A-B-C : 7)- odrzuć jako taki sam koszt
• Spróbuj (A-B-D : 13)- odrzuć jako wyższy koszt
• Spróbuj (A-B-E : 19)- odrzuć jako wyższy koszt
• Spróbuj (A-B-F : 19)- odrzuć jako wyższy koszt

Usunąć (A-C : 7)

• Spróbuj (A-C-A : 14)- odrzuć jako wyższy koszt
• Spróbuj (A-C-B : 7)- odrzuć jako taki sam koszt
• Spróbuj (A-C-D : 10)- odrzuć jako taki sam koszt
• Spróbuj (A-C-E : 16)- odrzuć jako taki sam koszt
• Spróbuj (A-C-F : 16)- odrzuć jako taki sam koszt

Usunąć (A-D : 10)

• Spróbuj (A-D-A : 20)- odrzuć jako wyższy koszt
• Spróbuj (A-D-B : 16)- odrzuć jako wyższy koszt
• Spróbuj (A-D-C : 13)- odrzuć jako wyższy koszt
• Spróbuj (A-D-E : 10)- wstaw do kolejki
• Spróbuj (A-D-F : 16)- odrzuć jako taki sam koszt

Teraz kolejka będzie wyglądać następująco:

queue     = [ (A-D-E : 10), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 16 }

Usunąć (A-D-E : 10)

• Spróbuj (A-D-E-A : 26)- odrzuć jako wyższy koszt
• Spróbuj (A-D-E-B : 22)- odrzuć jako wyższy koszt
• Spróbuj (A-D-E-C : 19)- odrzuć jako wyższy koszt
• Spróbuj (A-D-E-D : 10)- odrzuć jako taki sam koszt
• Spróbuj (A-D-E-F : 12)- wstaw do kolejki

Kolejka to:

queue     = [ (A-D-E-F : 12), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 12 }

Usuń (A-D-E-F : 12), znajdź, że dotarłeś do węzła docelowego w cenie 12.

Uwaga: ścieżki (A-B-C-D-E-F), (A-C-D-E-F)i (A-D-E-F)wszystkie mają ten sam koszt minimum 12.

Skonfiguruj macierz zawierającą wszystkie wierzchołki i użyj algorytmu Floyda-Wallensteina lub algorytmu Bellmana-Forda. Oba zaowocują macierzą z najkrótszymi możliwymi ścieżkami między wszystkimi punktami. Następnie możesz iterować po macierzy, aby znaleźć najkrótszą ścieżkę łączącą dwa punkty. (twój problem jest taki sam jak asymetryczny TSP).