Algorytm odnajdywania ścieżek dla pociągów

Question

Próbuję znaleźć rozwiązanie do odnajdywania ścieżki w grze pociągów, w której występują różne rodzaje bifurkacji. Chcę, żeby pociąg jechał z jednej szyny na drugą, wszystko jest zaimplementowane, poza ścieżką.

Potrzebuję uzyskać listę szyn, aby pociąg mógł podążać. Teraz problem polega na tym, jak uzyskać listę.

• Próbowałem A *, nie działało, ponieważ przestaje wyszukiwać, czy węzeł (szyna) jest już odwiedzony. To jest problem, ponieważ być może drogą do osiągnięcia punktu jest podróżowanie najdłuższą trasą.
• Wypełnione wypełnienie powodziowe, tym razem sprawiło, że nie zatrzymało się wyszukiwanie, jeśli już odwiedzono, problem polega na tym, jak zrekonstruować ścieżkę i jak to się wybiera, że ​​nie może cofnąć się ponownie.

Chodzi o to, że są przypadki, w których pociąg musi wielokrotnie przejeżdżać przez kolej, aby dotrzeć do celu.

Wszelkie pomysły?

Punkt początkowy to A, koniec B. Jak widać zielona ścieżka to sposób, w jaki powinien podróżować. Okrągły okrąg to szyny, które pociąg pokona więcej niż jeden raz, w tym przypadku 2 razy.

I oczywiście, trzeba pochodzić z 2 Black dostać się do 3 czerwone. Nie możesz po prostu przejść do 1czarnego-> 2red-> 1red-> 3red.

Answer 1

Patrząc na ten obraz

Okazuje się problem byłby reprezentowany również przez directed graph. Każdemu przystankowi i każdemu węzłowi należy przypisać dwa węzły na wykresie, po jednym dla każdego kierunku pociągu. Dijkstra's algorithm działa idealnie na skierowanych wykresach, więc gdy już masz problem w tej formie, reszta jest łatwa.

Na przykład na powyższym obrazku, począwszy od A, przechodzimy na junction 1. Stamtąd jest tylko jedno miejsce, do którego można się przenieść, junction 2, więc pojawi się strzałka od A ->junction 1 i strzałka od junction 1 ->junction 2. Bez względu na to, jaki wybierzesz, kończysz na junction 1, ale poruszasz się w innym kierunku, więc stamtąd tworzymy oddzielny węzeł.Z tego miejsca możesz wybrać opcję A lub B.

Zauważ, że usunąłem jedną z J1 „s, gdyż jest zbędny (jest tylko jedno miejsce, aby przejść).

Jeśli pociąg może się zatrzymać i zawrócić na przystankach takich jak A, możemy połączyć te dwa węzły za pomocą krawędzi w obu kierunkach lub po prostu połączyć je w jeden węzeł.

Można podać wagi krawędzi w celu określenia odległości.

Answer 2

Wypełnienie powodziowe powinno naprawdę zrobić (użyłem tego w podobnym przypadku) - ale trzeba tylko ostrożnie pracować z przełącznikami i segmentami.

Algorytmy powinny mieć możliwość przejścia tego samego segmentu w innym kierunku, ale nie w tym samym. To znaczy. każdy segment naprawdę powinien być traktowany jako dwa osobne.

zrekonstruować ścieżkę należy przypisać numery segmentów podczas zalewając je tak, aby każdy osiągnął z N-1 oznaczona N - wtedy, gdy ruch do tyłu, segmenty śledzenia powinny być wykonane tak, że liczba systematycznie zmniejszać o jeden.

To naprawdę rodzaj BFS.