Ostatnio natknąłem sięto (Edytuj: Problem A) interesujący problem z hakera Spotify na początku tego roku, który polega na określeniu przełączania na skrzyżowaniach wagonów kolejowych w celu skierowania pociągu z powrotem do punktu początkowego. Pociąg musi dotrzeć w tym samym kierunku, w którym jechał, a pociąg nigdy nie może się cofnąć na torach.

Jak rozumiem, problem można modelować jako nieukierunkowany (?) Wykres, w którym musimy znaleźć najkrótszy cykl z pewnego wierzchołka lub wykryć, że taki cykl nie istnieje. Jednakże interesującą częścią jest to, że dla wierzchołka v, wierzchołki sąsiadujące z v zależą od ścieżki podjętej do v, więc w pewnym sensie wykres można uznać za ukierunkowany, chociaż kierunek ten jest zależny od ścieżki.

Moją pierwszą myślą było zamodelowanie każdego węzła jako 3 oddzielne wierzchołki, A, B i C, gdzie A <-> B i A <-> C, a następnie skorzystaj z pierwszego wyszukiwania, aby zbudować drzewo wyszukiwania, aż znajdziemy oryginał wierzchołek, ale jest to skomplikowane przez zastrzeżenie powyżej, mianowicie, że przylegania dla danego wierzchołka zależą od poprzedniego wierzchołka, który odwiedziliśmy. Oznacza to, że w naszym drzewie BFS węzły mogą mieć wielu rodziców.

Oczywiście proste wyszukiwanie BFS nie wystarczy do rozwiązania tego problemu. Wiem, że istnieją algorytmy do wykrywania cykli na wykresie. Jednym z podejść może być wykrycie wszystkich cykli, a następnie każdego cyklu, wykrycie, czy ścieżka jest prawidłowa. (tj. nie odwraca kierunku)

Czy ktoś inny ma wgląd w podejście do rozwiązania tego problemu?

AKTUALIZACJA: W komentarzach zastosowałem podejście zaproponowane przez @Karussell.

Oto moje rozwiązanie na githubie.

Sztuką było modelowanie sytuacji za pomocą wykresu opartego na krawędziach, a nie tradycyjnego wykresu opartego na wierzchołkach. Plik wejściowy dostarczony w konkursie jest już dogodnie określony pod względem krawędzi, więc plik ten można łatwo wykorzystać do zbudowania wykresu opartego na krawędziach.

Program wykorzystuje dwie ważne klasy: Road i Solver. Droga ma dwa pola całkowite, j1 i j2. j1 reprezentuje złącze źródłowe, a j2 reprezentuje złącze docelowe. Każda droga jest jednokierunkowa, co oznacza, że ​​możesz podróżować tylko z j1 do j2. Każda droga zawiera także listę połączonych dróg i drogi macierzystej. Klasa Road zawiera również metody statyczne do konwersji między ciągami znaków używanymi w pliku wejściowym i indeksami całkowitymi reprezentującymi punkty A, B i C na każdym połączeniu.

Dla każdego wpisu w pliku wejściowym dodajemy dwie drogi do mapy mieszającej, jedną drogę dla każdego kierunku między dwoma skrzyżowaniami. Mamy teraz listę wszystkich dróg, które biegną między skrzyżowaniami. Musimy po prostu połączyć drogi na skrzyżowaniach za pomocą przełączników A, B i C. Jeśli droga kończy się na skrzyżowaniu.A, sprawdzamy drogi, które zaczynają się w Junction.B i Junction.C, i dodajemy te drogi jako sąsiednie. Funkcja buildGraph () zwraca Drogę, której docelowym węzłem (j2) jest „1A” == indeks 0.

W tym momencie tworzony jest nasz wykres. Aby znaleźć najkrótszą ścieżkę, po prostu użyłem BFS, aby przejść przez wykres. Pozostawiamy korzeń nieoznaczony i zaczynamy od kolejkowania przylegań korzenia. Jeśli znajdziemy drogę, której docelowym skrzyżowaniem jest „1A” (indeks 0), znaleźliśmy najkrótszy cykl przez punkt początkowy. Gdy zrekonstruujemy ścieżkę przy użyciu właściwości nadrzędnej każdej Drogi, jest to trywialna sprawa, aby odpowiednio ustawić przełączniki zgodnie z wymaganiami problemu.

Dziękuję Karussellowi za zaproponowanie tego podejścia. Jeśli chcesz umieścić swój komentarz w formularzu odpowiedzi z krótkim wyjaśnieniem, zaakceptuję go. Dzięki także @Origin. Muszę przyznać, że nie w pełni podążyłem za logiką twojej odpowiedzi, ale z pewnością nie oznacza to, że nie jest poprawna. Gdyby ktoś rozwiązał ten problem za pomocą swojego rozwiązania, bardzo chciałbym go zobaczyć.