Próbuję określić najlepszy czasowo algorytm do wykonania opisanego poniżej zadania.
Mam zestaw rekordów. Dla tego zestawu rekordów mam dane połączeń, które wskazują, jak pary rekordów z tego zestawu łączą się ze sobą. Zasadniczo reprezentuje to wykres nie skierowany, z rekordami będącymi wierzchołkami, a danymi połączenia krawędziami.
Wszystkie rekordy w zestawie zawierają informacje o połączeniu (tj. Nie ma żadnych osieroconych rekordów; każdy rekord w zestawie łączy się z jednym lub kilkoma innymi rekordami w zestawie).
Chcę wybrać dowolne dwa rekordy z zestawu i móc pokazać wszystkie proste ścieżki między wybranymi rekordami. Przez „proste ścieżki” rozumiem ścieżki, które nie mają powtarzających się zapisów na ścieżce (tj. Tylko ścieżki skończone).
Uwaga: dwa wybrane rekordy zawsze będą różne (tj. Wierzchołek początkowy i końcowy nigdy nie będą takie same; bez cykli).
Na przykład:
Jeśli mam następujące rekordy: A, B, C, D, E. a następujący przedstawia połączenia: (A, B), (A, C), (B, A), (B, D), (B, E), (B, F), (C, A), (C, E), (C, F), (D, B), (E, C), (E, F), (F, B), (F, C), (F, E) [gdzie (A, B) oznacza, że rekord A łączy się z rekordem B]
Gdybym wybrał B jako mój rekord początkowy i E jako rekord końcowy, chciałbym znaleźć wszystkie proste ścieżki przez połączenia rekordów, które łączyłyby rekord B z rekordem E.
Wszystkie ścieżki łączące B z E: B-> E B-> F-> E B-> F-> C-> E B-> A-> C-> E B-> A-> C-> F-> E
To jest przykład, w praktyce mogę mieć zestawy zawierające setki tysięcy rekordów.
źródło
Odpowiedzi:
Wydaje się, że można to osiągnąć, przeszukując wykres najpierw w głąb. Przeszukiwanie w głąb znajdzie wszystkie niecykliczne ścieżki między dwoma węzłami. Ten algorytm powinien być bardzo szybki i skalowany do dużych wykresów (struktura danych wykresu jest rzadka, więc zużywa tylko tyle pamięci, ile potrzebuje).
Zauważyłem, że wykres, który wskazałeś powyżej, ma tylko jedną krawędź, która jest kierunkowa (B, E). Czy to była literówka, czy naprawdę jest to wykres skierowany? To rozwiązanie działa niezależnie. Przepraszam, że nie mogłem tego zrobić w C, jestem trochę słaby w tej dziedzinie. Spodziewam się jednak, że będziesz w stanie przetłumaczyć ten kod Java bez większych problemów.
Graph.java:
Search.java:
Wyjście programu:
źródło
Internetowy Słownik Algorytmów i Struktur Danych Narodowego Instytutu Standardów i Technologii (NIST) wymienia ten problem jako „ wszystkie proste ścieżki” i zaleca przeszukiwanie w głąb . CLRS dostarcza odpowiednie algorytmy.
Sprytny technika przy użyciu sieci Petriego znajduje się tutaj
źródło
Oto pseudokod, który wymyśliłem. Nie jest to żaden szczególny dialekt pseudokodu, ale powinien być na tyle prosty do naśladowania.
Każdy chce to rozebrać.
[p] to lista wierzchołków reprezentujących bieżącą ścieżkę.
[x] to lista ścieżek spełniających kryteria
[s] jest wierzchołkiem źródłowym
[d] jest wierzchołkiem docelowym
[c] to bieżący wierzchołek (argument do procedury PathFind)
Załóżmy, że istnieje skuteczny sposób wyszukiwania sąsiednich wierzchołków (wiersz 6).
źródło
Ponieważ istniejąca nierekurencyjna implementacja DFS podana w tej odpowiedzi wydaje się być zepsuta, pozwólcie, że przedstawię taką, która faktycznie działa.
Napisałem to w Pythonie, ponieważ uważam, że jest dość czytelny i niezakłócony szczegółami implementacji (i ponieważ zawiera przydatne
yield
słowo kluczowe do implementacji generatorów ), ale powinno być dość łatwe do przeniesienia na inne języki.Ten kod utrzymuje dwa równoległe stosy: jeden zawierający wcześniejsze węzły w bieżącej ścieżce i jeden zawierający bieżący indeks sąsiadów dla każdego węzła w stosie węzłów (abyśmy mogli wznowić iterację przez sąsiadów węzła, gdy go wycofamy stos). Równie dobrze mogłem użyć pojedynczego stosu par (węzeł, indeks), ale pomyślałem, że metoda z dwoma stosami byłaby bardziej czytelna i być może łatwiejsza do wdrożenia dla użytkowników innych języków.
Ten kod używa również oddzielnego
visited
zestawu, który zawsze zawiera bieżący węzeł i wszystkie węzły na stosie, aby umożliwić mi efektywne sprawdzenie, czy węzeł jest już częścią bieżącej ścieżki. Jeśli zdarzy się, że Twój język ma strukturę danych „uporządkowanego zestawu”, która zapewnia zarówno wydajne operacje push / pop podobne do stosu, jak i wydajne zapytania członkostwa, możesz użyć tego dla stosu węzłów i pozbyć się oddzielnegovisited
zestawu.Alternatywnie, jeśli używasz niestandardowej mutowalnej klasy / struktury dla swoich węzłów, możesz po prostu przechowywać flagę logiczną w każdym węźle, aby wskazać, czy został odwiedzony jako część bieżącej ścieżki wyszukiwania. Oczywiście ta metoda nie pozwoli ci przeprowadzić równolegle dwóch wyszukiwań na tym samym wykresie, jeśli z jakiegoś powodu chcesz to zrobić.
Oto kod testowy demonstrujący działanie funkcji podanej powyżej:
Uruchomienie tego kodu na podanym przykładowym wykresie daje następujące dane wyjściowe:
Zauważ, że chociaż ten przykładowy graf jest nieukierunkowany (tj. Wszystkie jego krawędzie idą w obie strony), algorytm działa również dla dowolnie ukierunkowanych grafów. Na przykład usunięcie
C -> B
krawędzi (przez usunięcieB
z listy sąsiadówC
) daje takie same wyniki, z wyjątkiem trzeciej ścieżki (A -> C -> B -> D
), która nie jest już możliwa.Ps. Łatwo jest skonstruować wykresy, dla których proste algorytmy wyszukiwania, takie jak ten (i inne podane w tym wątku), działają bardzo słabo.
Na przykład rozważmy zadanie znalezienia wszystkich ścieżek od A do B na grafie niekierowanym, gdzie węzeł początkowy A ma dwóch sąsiadów: węzeł docelowy B (który nie ma innych sąsiadów niż A) i węzeł C będący częścią kliki. z n +1 węzłów, na przykład:
Łatwo zauważyć, że jedyna ścieżka między A i B jest bezpośrednia, ale naiwny DFS uruchomiony z węzła A zmarnuje O ( n !) Czas bezużytecznie eksplorując ścieżki wewnątrz kliki, mimo że jest oczywiste (dla człowieka), że żadna z tych ścieżek nie może prowadzić do B.
Można również konstruować DAG o podobnych właściwościach, np. Poprzez połączenie węzła początkowego A węzła docelowego B i dwóch innych węzłów C 1 i C 2 , z których oba łączą się z węzłami D 1 i D 2 , z których oba łączą się z E 1 i E 2 i tak dalej. Dla n warstw węzłów ułożonych w ten sposób naiwne poszukiwanie wszystkich ścieżek od A do B zakończy się marnowaniem O (2 n ) czasu na zbadanie wszystkich możliwych ślepych uliczek, zanim się poddaje.
Oczywiście dodanie krawędzi do węzła docelowego B z jednym z węzłów w klika (inne niż C) lub od ostatniej warstwy DAG, by utworzyć wykładniczo dużą liczbę możliwych ścieżek z A do B, a czysto lokalny algorytm wyszukiwania nie jest w stanie z góry powiedzieć, czy znajdzie taką krawędź, czy nie. Zatem w pewnym sensie niska wrażliwość wyników takich naiwnych wyszukiwań wynika z braku świadomości globalnej struktury wykresu.
Chociaż istnieją różne metody przetwarzania wstępnego (takie jak iteracyjne eliminowanie węzłów liści, wyszukiwanie separatorów wierzchołków pojedynczych węzłów itp.), Których można by użyć do uniknięcia niektórych z tych „ślepych zaułków w czasie wykładniczym”, nie znam żadnych ogólnych sztuczka z przetwarzaniem wstępnym, która może je wyeliminować we wszystkich przypadkach. Ogólnym rozwiązaniem byłoby sprawdzenie na każdym etapie wyszukiwania, czy węzeł docelowy jest nadal osiągalny (za pomocą wyszukiwania podrzędnego) i cofnięcie się wcześniej, jeśli tak nie jest - ale niestety, to znacznie spowolniłoby wyszukiwanie (w najgorszym przypadku proporcjonalnie do wielkości wykresu) dla wielu wykresów, które nie zawierają takich patologicznych ślepych zaułków.
źródło
for path in find_simple_paths(graph, "A", "D"): print(" -> ".join(path))
,print
brak nawiasu.Oto logicznie lepiej wyglądająca wersja rekurencyjna w porównaniu z drugim piętrem.
Wyjście programu
źródło
Rozwiązanie w kodzie C. Opiera się na systemie plików DFS, który wykorzystuje minimalną ilość pamięci.
źródło
To może być późno, ale oto ta sama wersja C # algorytmu DFS w Javie z Casey do przechodzenia dla wszystkich ścieżek między dwoma węzłami przy użyciu stosu. Czytelność jest lepsza w przypadku rekurencji, jak zawsze.
źródło
neighbours.Reverse()
? Czy to jestList<T>.Reverse
?Podobny problem rozwiązałem ostatnio, zamiast wszystkich rozwiązań interesowało mnie tylko najkrótsze.
Użyłem wyszukiwania iteracyjnego „najpierw wszerz”, które wykorzystywało kolejkę statusu ”, z których każdy zawierał rekord zawierający bieżący punkt na wykresie i ścieżkę prowadzącą do niego.
zaczynasz od pojedynczego rekordu w kolejce, który ma węzeł początkowy i pustą ścieżkę.
Każda iteracja po kodzie zdejmuje pozycję z nagłówka listy i sprawdza, czy jest to rozwiązanie (otrzymany węzeł to ten, który chcesz, jeśli tak, to skończymy), w przeciwnym razie konstruuje nowy element kolejki z węzłami łączącymi się z bieżącym węzłem i zmienione ścieżki oparte na ścieżce poprzedniego węzła, z nowym skokiem dołączonym na końcu.
Teraz możesz użyć czegoś podobnego, ale kiedy znajdziesz rozwiązanie, zamiast się zatrzymywać, dodaj to rozwiązanie do swojej „listy znalezionych” i kontynuuj.
Musisz śledzić listę odwiedzonych węzłów, aby nigdy nie cofać się do siebie, w przeciwnym razie masz nieskończoną pętlę.
jeśli chcesz trochę więcej pseudokodu, napisz komentarz lub coś, a ja rozwinę.
źródło
Myślę, że powinieneś opisać swój prawdziwy problem, który za tym stoi. Mówię to, ponieważ prosisz o coś efektywnego czasowo, ale odpowiedź na problem wydaje się rosnąć wykładniczo!
Dlatego nie spodziewałbym się lepszego algorytmu niż czegoś wykładniczego.
Wycofywałbym się i przeglądał cały wykres. Aby uniknąć cykli, po drodze zapisuj wszystkie odwiedzane węzły. Kiedy wrócisz, odznacz węzeł.
Korzystanie z rekursji:
Czy to źle?
edit: Aha, i zapomniałem: Powinieneś wyeliminować wywołania rekurencyjne, wykorzystując ten stos węzłów
źródło
Podstawową zasadą jest to, że nie musisz martwić się o wykresy - jest to standardowy problem znany jako problem z łącznością dynamiczną. Istnieją następujące typy metod, z których można uzyskać węzły są połączone lub nie:
Oto kod C, który próbowałem z minimalną złożonością czasową O (log * n) Oznacza to, że dla 65536 listy krawędzi wymaga 4 wyszukiwań, a dla 2 ^ 65536 wymaga 5 wyszukiwań. Udostępniam swoją implementację z algorytmu: Algorithm Course z Uniwersytetu Princeton
WSKAZÓWKA: Możesz znaleźć rozwiązanie Java z linku udostępnionego powyżej z odpowiednimi wyjaśnieniami.
źródło
znajdź_ścieżki [s, t, d, k]
To pytanie jest stare i już na nie odpowiedział. Jednak żaden nie pokazuje być może bardziej elastycznego algorytmu do osiągnięcia tego samego. Więc wrzucę kapelusz do ringu.
Osobiście
find_paths[s, t, d, k]
przydaje mi się algorytm postaci , gdzie:Korzystanie z nieskończoności w języku programowania dla
d
ik
zapewni Ci wszystkie ścieżki§.§ oczywiście jeśli używasz skierowanego wykresu i chcesz, aby wszystko było nieukierunkowane ścieżki pomiędzy
s
it
trzeba będzie uruchomić to w obie strony:Funkcja pomocnika
Osobiście lubię rekurencję, chociaż czasami może to być trudne, w każdym razie najpierw zdefiniujmy naszą funkcję pomocniczą:
Główna funkcja
Z tego powodu podstawowa funkcja jest trywialna:
Najpierw zwróćmy uwagę na kilka rzeczy:
[]
jest listą niezainicjowaną, zamień ją na odpowiednik dla wybranego języka programowaniapaths_found
jest omijany odniesienie . Jest jasne, że funkcja rekurencyjna nic nie zwraca. Zajmij się tym odpowiednio.graph
przyjmuje jakąś formęhashed
struktury. Istnieje wiele sposobów implementacji wykresu. Tak czy inaczej,graph[vertex]
wyświetla listę sąsiednich wierzchołków w a skierowanym wykresie - odpowiednio dostosuj.źródło
Oto myśl z góry mojej głowy:
źródło
O ile wiem, rozwiązania podane przez Ryana Foxa ( 58343 , Christiana ( 58444 ) i Ciebie ( 58461 )) są prawie tak dobre, jak to tylko możliwe. nie wszystkie ścieżki. Na przykład z krawędziami
(A,B)
,(A,C)
,(B,C)
,(B,D)
a(C,D)
dostaniesz ścieżkiABD
iACD
, ale nieABCD
.źródło
Znalazłem sposób na wyliczenie wszystkich ścieżek, w tym nieskończonych zawierających pętle.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Znajdowanie ścieżek i cykli atomowych
Chcemy znaleźć wszystkie możliwe ścieżki prowadzące z punktu A do punktu B. Ponieważ w grę wchodzą cykle, nie można po prostu przejść i wyliczyć ich wszystkich. Zamiast tego będziesz musiał znaleźć ścieżkę atomową, która nie zapętla się i jak najmniejsze możliwe cykle (nie chcesz, aby cykl się powtarzał).
Pierwsza definicja ścieżki atomowej, którą przyjąłem, to ścieżka, która nie przechodzi dwukrotnie przez ten sam węzeł. Jednak okazało się, że nie wykorzystuje wszystkich możliwości. Po chwili zastanowienia doszedłem do wniosku, że węzły nie są ważne, ale krawędzie są! Tak więc ścieżka atomowa to ścieżka, która nie przechodzi dwukrotnie przez tę samą krawędź.
Ta definicja jest przydatna, działa również dla cykli: atomowy cykl punktu A to atomowa ścieżka, która biegnie od punktu A i kończy się do punktu A.
Realizacja
Aby uzyskać całą ścieżkę zaczynającą się od punktu A, będziemy rekurencyjnie przechodzić przez wykres od punktu A.Podczas przechodzenia przez dziecko utworzymy link child -> parent, aby poznać wszystkie krawędzie, które już przekroczyłem. Zanim przejdziemy do tego dziecka, musimy przejść przez tę połączoną listę i upewnić się, że określona krawędź nie została już przejęta.
Kiedy dotrzemy do punktu docelowego, możemy zapisać znalezioną ścieżkę.
Problem pojawia się, gdy chcesz zwolnić połączoną listę. Zasadniczo jest to drzewo połączone łańcuchem w odwrotnej kolejności. Rozwiązaniem byłoby podwójne połączenie tej listy i po znalezieniu wszystkich atomowych ścieżek uwolnienie drzewa od punktu początkowego.
Ale sprytnym rozwiązaniem jest użycie liczenia referencji (zainspirowane Garbage Collection). Za każdym razem, gdy dodajesz łącze do rodzica, dodajesz jeden do jego liczby odwołań. Następnie, gdy dojdziesz do końca ścieżki, cofasz się i jesteś wolny, podczas gdy liczba odniesień wynosi 1. Jeśli jest wyższa, po prostu usuwasz jedną i zatrzymujesz się.
Szukanie atomowego cyklu A jest tym samym, co szukanie atomowej ścieżki od A do A. Jest jednak kilka optymalizacji, które możemy zrobić. Po pierwsze, kiedy docieramy do punktu docelowego, chcemy zapisać ścieżkę tylko wtedy, gdy suma kosztów krawędzi jest ujemna: chcemy tylko przejść przez cykle absorpcyjne.
Jak widzieliście wcześniej, podczas poszukiwania atomowej ścieżki przechodzi się przez cały wykres. Zamiast tego możemy ograniczyć obszar wyszukiwania do silnie połączonego komponentu zawierającego A. Znalezienie tych komponentów wymaga prostego przejścia grafu za pomocą algorytmu Tarjana.
Łączenie ścieżek i cykli atomowych
W tym momencie mamy wszystkie ścieżki atomowe, które biegną od A do B i wszystkie cykle atomowe każdego węzła, które zostały nam pozostawione do zorganizowania wszystkiego, aby uzyskać najkrótszą ścieżkę. Od teraz będziemy się uczyć, jak znaleźć najlepszą kombinację cykli atomowych na ścieżce atomowej.
źródło
Jak umiejętnie opisali niektórzy z innych plakatów, problem w skrócie polega na wykorzystaniu algorytmu przeszukiwania w głąb do rekurencyjnego przeszukiwania grafu pod kątem wszystkich kombinacji ścieżek między komunikującymi się węzłami końcowymi.
Sam algorytm rozpoczyna się od węzła początkowego, który mu podasz, bada wszystkie jego linki wychodzące i postępuje, rozszerzając pierwszy węzeł potomny drzewa wyszukiwania, które się pojawi, przeszukując coraz głębiej, aż do znalezienia węzła docelowego lub do momentu napotkania węzła która nie ma dzieci.
Wyszukiwanie jest następnie cofane, wracając do ostatniego węzła, którego jeszcze nie zakończyło.
Całkiem niedawno pisałem na ten temat na blogu , zamieszczając przykładową implementację C ++ w procesie.
źródło
Dodając do odpowiedzi Casey Watson, oto kolejna implementacja Java. Inicjowanie odwiedzonego węzła z węzłem początkowym.
źródło