Jak korzystać z dwukierunkowego BFS, aby znaleźć najkrótszą ścieżkę?

Question

Jak korzystać z dwukierunkowego BFS, aby znaleźć najkrótszą ścieżkę? Załóżmy, że istnieje siatka 6x6. Punkt początkowy znajduje się w (0,5), a punkt końcowy jest w (4,1). Jaka jest najkrótsza ścieżka przy użyciu dwukierunkowych plików bf? Nie ma kosztów ścieżki. I jest nieukierunkowany.

Answer 1

Jak działa BFS dwukierunkowy?

Jednocześnie uruchom dwa BFS z obu wierzchołków źródłowego i docelowego, kończąc po wykryciu wierzchołka wspólnego dla obu przebiegów. Ten wierzchołek będzie w połowie drogi między źródłem a celem.

Dlaczego jest lepszy niż BFS?

Dwukierunkowy BFS przyniesie znacznie lepsze wyniki niż prosty BFS w większości przypadków. Załóżmy, że odległość między źródłem i celem to k, a współczynnik rozgałęzienia to B (każdy wierzchołek ma przeciętnie krawędzie B).

• BFS będzie przechodzić przez wierzchołki o wartościach 1 + B + B^2 + ... + B^k.
• Dwukierunkowe BFS będzie przechodzić przez wierzchołki o wartościach 2 + 2B^2 + ... + 2B^(k/2).

Dla dużych B i k drugi jest oczywiście znacznie szybszy od pierwszego.

---

W twoim przypadku:

Dla uproszczenia będę zakładać, że nie ma żadnych przeszkód w matrycy. Oto co się dzieje:

iteration 0 (init): 
front1 = { (0,5) } 
front2 = { (4,1) } 

iteration 1: 
front1 = { (0,4), (1,5) } 
front2 = { (4,0), (4,2), (3,1), (5,1) } 

iteration 2: 
front1 = { (0,3), (1,4), (2,5) } 
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) } 

iteration 3: 
front1 = { (0,2), (1,3), (2,4), (3,5) } 
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), } 

iteration 4: 
front1 = { (0,1), (1,2), .... } 
front2 = { (1,2) , .... } 

Teraz odkryliśmy, że fronty przecinają się (1,2), wraz ze ścieżkami podjętych tam od wierzchołków źródłowych i docelowych:

path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) 
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2) 

Teraz musimy tylko odwrócić ścieżkę 2 i dołączyć ją do ścieżki 1 (usuwając jeden z powszechnych przecinających się wierzchołków oczywiście), aby dać nam pełną ścieżkę:

(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)