Zrobiłem kilka badań i wydaje mi się, że brakuje mi jednej małej części tego algorytmu. Rozumiem, jak działa wyszukiwanie wszerz, ale nie rozumiem, jak dokładnie doprowadzi mnie do określonej ścieżki, w przeciwieństwie do zwykłego informowania mnie, gdzie może przejść każdy węzeł. Myślę, że najłatwiejszym sposobem wyjaśnienia mojego pomieszania jest podanie przykładu:
Załóżmy na przykład, że mam taki wykres:
Moim celem jest przejście od punktu A do E (wszystkie krawędzie są nieważone).
Zaczynam na A, bo to jest moje pochodzenie. Ustawiam w kolejce A, po czym natychmiast usuwam A z kolejki i eksploruję go. Daje to B i D, ponieważ A jest połączone z B i D. W ten sposób ustawiam w kolejce zarówno B, jak i D.
Wyciągam B z kolejki i badam go i stwierdzam, że prowadzi do A (już zbadanego) i C, więc ustawiam w kolejce C. Następnie usuwam D z kolejki i stwierdzam, że prowadzi to do E, mojego celu. Następnie usuwam C z kolejki i stwierdzam, że prowadzi to również do E, mojego celu.
Wiem logicznie, że najszybszą ścieżką jest A-> D-> E, ale nie jestem pewien, jak dokładnie pomaga wyszukiwanie wszerz - jak mam nagrywać ścieżki tak, że po skończeniu mogę przeanalizować wyniki i zobaczyć że najkrótszą ścieżką jest A-> D-> E?
Zauważ też, że tak naprawdę nie używam drzewa, więc nie ma węzłów „nadrzędnych”, są tylko dzieci.
Odpowiedzi:
Technicznie rzecz biorąc, samo przeszukiwanie wszerz (BFS) nie pozwala znaleźć najkrótszej ścieżki, po prostu dlatego, że BFS nie szuka najkrótszej ścieżki: BFS opisuje strategię wyszukiwania wykresu, ale nie mówi, że musisz szukać coś konkretnego.
Algorytm Dijkstry dostosowuje BFS, aby umożliwić znalezienie najkrótszych ścieżek z jednego źródła.
Aby pobrać najkrótszą ścieżkę od początku do węzła, musisz zachować dwa elementy dla każdego węzła na wykresie: jego bieżącą najkrótszą odległość i poprzedni węzeł na najkrótszej ścieżce. Początkowo wszystkie odległości są ustawione na nieskończoność, a wszystkie poprzedniki są puste. W twoim przykładzie ustawiasz odległość A na zero, a następnie kontynuujesz BFS. Na każdym kroku sprawdzasz, czy możesz poprawić odległość potomka, tj. Odległość od początku do poprzednika plus długość eksplorowanej krawędzi jest mniejsza niż aktualnie najlepsza odległość dla danego węzła. Jeśli możesz poprawić dystans, wyznacz nową najkrótszą ścieżkę i pamiętaj o poprzedniku, przez który ta ścieżka została zdobyta. Gdy kolejka BFS jest pusta, wybierz węzeł (w twoim przykładzie jest to E) i przejdź przez jego poprzedników z powrotem do początku.
Jeśli brzmi to trochę zagmatwane, wikipedia ma fajną sekcję dotyczącą pseudokodów na ten temat.
źródło
Jak wskazano powyżej, BFS może tylko być użyte do znalezienia najkrótszej ścieżki w wykresie, jeżeli:
Nie ma pętli
Wszystkie krawędzie mają taką samą wagę lub nie mają wagi.
Aby znaleźć najkrótszą ścieżkę, wszystko, co musisz zrobić, to zacząć od źródła i przeprowadzić najpierw szerokie wyszukiwanie i zatrzymać się po znalezieniu docelowego węzła. Jedyną dodatkową rzeczą, którą musisz zrobić, jest posiadanie tablicy previous [n], która będzie przechowywać poprzedni węzeł dla każdego odwiedzanego węzła. Poprzednie źródło może mieć wartość null.
Aby wydrukować ścieżkę, po prostu wykonaj pętlę przez poprzednią tablicę [] od źródła do miejsca docelowego i wydrukuj węzły. DFS można również wykorzystać do znalezienia najkrótszej ścieżki na wykresie w podobnych warunkach.
Jeśli jednak wykres jest bardziej złożony, zawiera ważone krawędzie i pętle, to potrzebujemy bardziej wyrafinowanej wersji BFS, czyli algorytmu Dijkstry.
źródło
To print the path, simple loop through the previous[] array from source till you reach destination.
Ale poprzednie źródło jest zerowe. Myślę, że to, co masz na myśli to,backtrace from destination using the previous array until you reach the source
.Z tutoriala tutaj
źródło
Zmarnowałem 3 dni i
ostatecznie rozwiązałem pytanie
dotyczące wykresu używane do
znajdowania najkrótszej odległości
za pomocą BFS
Chcesz podzielić się doświadczeniem.
Straciłem 3 dni próbując wszystkich powyższych alternatyw, weryfikując i weryfikując ponownie i ponownie powyżej
, to nie jest problem.
(Spróbuj poświęcić czas na szukanie innych problemów, jeśli nie znajdziesz żadnych problemów z powyższymi 5).
Więcej wyjaśnień z komentarza poniżej:
Załóżmy, że powyżej
wykres idzie w dół
Dla A, przyległe są B i C
Dla B, przyległe to D i E
Dla C, przyległe to F i G
powiedzmy, węzeł początkowy to A
kiedy dojdziesz do punktu A, do, B i C, najkrótsza odległość do B&C z punktu A wynosi 1
kiedy osiągniesz D lub E, przez B, najkrótsza odległość do A i D to 2 (A-> B-> D)
podobnie A-> E to 2 (A-> B-> E)
również A-> F i A-> G wynosi 2
Więc teraz zamiast 1 odległości między węzłami, jeśli wynosi 6, po prostu pomnóż odpowiedź przez 6, na
przykład,
jeśli odległość między nimi wynosi 1, to A-> E wynosi 2 (A-> B-> E = 1 + 1 )
jeśli odległość między nimi wynosi 6, to A-> E wynosi 12 (A-> B-> E = 6 + 6)
tak, bfs mogą obrać dowolną ścieżkę,
ale obliczamy dla wszystkich ścieżek
jeśli musisz przejść od A do Z, wtedy podróżujemy wszystkimi ścieżkami od A do pośredniego I, a ponieważ będzie wiele ścieżek, odrzucamy wszystkie oprócz najkrótszej ścieżki do I, a następnie kontynuuj ponownie najkrótszą ścieżką do następnego węzła J,
jeśli istnieje wiele ścieżek od I do J, bierzemy tylko najkrótszy
przykład,
załóżmy , że
A -> I mamy odległość 5
(STEP) załóżmy, że I -> J mamy wiele ścieżek o odległości 7 i 8, ponieważ 7 jest najkrótsza
bierzemy A -> J jako 5 (A-> I najkrótsza) + 8 (teraz najkrótsza) = 13,
więc A-> J jest teraz 13
powtarzamy teraz powyżej (KROK) dla J -> K i tak dalej, aż otrzymamy do Z
Przeczytaj tę część 2 lub 3 razy i narysuj na papierze, na pewno dostaniesz to, co mówię, powodzenia
źródło
Na podstawie acheron55 odpowiedzi napisałem możliwą implementację tutaj .
Oto krótkie podsumowanie tego:
Jedyne, co musisz zrobić, to śledzić ścieżkę, po której osiągnięto cel. Prostym sposobem na to jest wciśnięcie
Queue
całej ścieżki używanej do osiągnięcia węzła, a nie samego węzła.Korzyścią z tego jest to, że po osiągnięciu celu kolejka zawiera ścieżkę używaną do osiągnięcia tego celu.
Ma to również zastosowanie do wykresów cyklicznych, w których węzeł może mieć więcej niż jednego rodzica.
źródło
Odwiedzam ten wątek po pewnym okresie bezczynności, ale biorąc pod uwagę, że nie widzę dokładnej odpowiedzi, oto moje dwa centy.
Przeszukiwanie wszerz zawsze znajdzie najkrótszą ścieżkę na nieważonym wykresie. Wykres może być cykliczny lub acykliczny.
Zobacz poniżej pseudokod. Ten pseudokod zakłada, że używasz kolejki do implementacji BFS. Zakłada również, że możesz oznaczyć wierzchołki jako odwiedzone i że każdy wierzchołek przechowuje parametr odległości, który jest inicjowany do nieskończoności.
Zauważ, że to podejście nie działa w przypadku wykresów ważonych - zobacz algorytm Dijkstry.
źródło
Poniższe rozwiązanie działa dla wszystkich przypadków testowych.
źródło