Come si usa un BFS bidirezionale per trovare il percorso più breve?

Question

Come si utilizza un BFS bidirezionale per trovare il percorso più breve? Diciamo che c'è una griglia 6x6. Il punto iniziale è in (0,5) e il punto finale è in (4,1). Qual è il percorso più breve che utilizza il bfs bidirezionale? Non ci sono costi di percorso. Ed è diretto.

Answer 1

Come funziona il BFS bidirezionale?

Esegui simultaneamente due BFS da entrambi i vertici di origine e di destinazione, terminando quando viene scoperto un vertice comune a entrambe le esecuzioni. Questo vertice sarà a metà strada tra la fonte e il bersaglio.

Perché è meglio di BFS?

BFS bidirezionale produrrà risultati molto migliori rispetto al semplice BFS nella maggior parte dei casi. Si supponga che la distanza tra la sorgente e il target sia k e che il fattore di diramazione sia B (ogni vertice ha in media bordi B).

• BFS attraverserà i vertici 1 + B + B^2 + ... + B^k.
• BFS bidirezionale attraverserà i vertici 2 + 2B^2 + ... + 2B^(k/2).

Per il grande B e k, il secondo è ovviamente molto più veloce del primo.

---

Nel tuo caso:

Per semplicità ho intenzione di assumere che non vi siano ostacoli nella matrice. Ecco cosa accade:

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) , .... } 

Ora, abbiamo scoperto che i fronti si intersecano in (1,2), insieme con i percorsi per arrivare dai vertici origine e di destinazione:

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

ora solo bisogno di invertire il percorso 2 e aggiungerlo al percorso 1 (rimozione di uno dei vertici che si intersecano comuni ovviamente), a noi dare il nostro percorso completo:

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