Percorso più breve: DFS, BFS o entrambi?

Question

So che solo BFS può trovare il percorso più breve in un grafico non ponderato, ma ho anche letto su un paio di siti in cui le persone affermavano che BFS o DFS potevano farlo. Volevo solo confermare che questi erano probabilmente errori e che solo BFS può farlo (non ero del tutto fiducioso anche dopo aver fatto una rapida ricerca su google). Se non sono corretto, qualcuno può spiegare come è possibile che DFS dia il percorso più breve.

Answer 1

DFS non produce necessariamente percorsi più brevi in ​​un grafico non orientato. BFS sarebbe la scelta giusta qui.

Ad esempio, si consideri un grafico formato prendendo gli angoli di un triangolo e collegandoli. Se si tenta di trovare il percorso più breve da un nodo a un altro utilizzando DFS, si otterrà la risposta errata a meno che non si segua lo spigolo che collega direttamente i nodi di inizio e di destinazione.

Spero che questo aiuti!

Answer 2

Iterative deepening search (IDS), che consiste in molti round di ricerca con profondità limitata (in pratica DFS, ma interrompi la ricerca se hai raggiunto un limite di profondità d) che aumenta gradualmente la profondità da 1, troverà il percorso più breve in un grafico non ponderato.

// Iterative deepening search 
// isGoal is a function that checks whether the current node is the goal 
function ids(graph, start, isGoal) { 
    maxDepth = 1 
    do { 
     found = dls(graph, start, isGoal, maxDepth, 0) 
     // Clear the status whether a node has been visited 
     graph.clearVisitedMarker(); 
     // Increase maximum depth 
     depth = depth + 1 

    // You can slightly modify the dls() function to return whether there is a 
    // node beyond max depth, in case the graph doesn't have goal node. 
    } while (found == null) 

    return found 
} 

// Depth-limited search 
// isGoal is a function that checks whether the current node is the goal 
function dls(graph, currentNode, isGoal, maxDepth, currentDepth) { 
    if (graph.visited(currentNode)) { 
     return null 
    } 
    graph.setVisited(currentNode) 

    if (isGoal(currentNode)) { 
     return currentNode 
    } 

    // Stop searching when exceed max depth 
    // This is the only difference from DFS 
    if (currentDepth >= maxDepth) { 
     return null 
    } 

    for (adjNode in graph.getAdjacent(currentNode)) { 
     found = dls(graph, adjNode, goal, maxDepth, currentDepth + 1) 
     if (found != null) { 
      return found 
     } 
    } 

    return null 
} 

Funziona, poiché si aumenta gradualmente la distanza consentita dal nodo di partenza: un nodo che ha distanza A + 1 non sarà esplorato prima un nodo che ha la distanza A, a causa del limite di profondità.

Una preoccupazione comune è che i nodi con distanza a saranno rivisitati (d - a + 1) volte dove d è la profondità del percorso più breve verso l'obiettivo. Dipende dal grafico o albero di ricerca se vogliamo parlare di prestazioni. Su un albero di ricerca con un grande fattore di ramificazione, i nodi generati a profondità d diventano il termine dominante, quindi non c'è molto di un problema con la rivisitazione. BFS inutilizzabile per questo caso a causa del requisito di spazio esponenziale, ma IDS utilizzerà solo lo spazio polinomiale.

Answer 3

Sia BFS che DFS forniranno il percorso più breve da A a B se implementato correttamente.

Consideriamo l'intero grafico come un albero. Fondamentalmente, BFS eseguirà ogni livello di albero e scoprirà il percorso attraversando tutti i livelli. Nel contrasto, DFS verrà eseguito su ciascun nodo foglia e individuerà il percorso quando attraversi il nodo lungo quel percorso. Entrambi utilizzano la ricerca del percorso di scarico, quindi entrambi garantiranno di trovare il percorso più breve, sempre se implementate correttamente questi algoritmi.

I pro ei contro per l'utilizzo di BFS e DFS è la seguente:

BFS, utilizza più memoria, attraversare tutti i nodi

DFS, utilizza meno memoria, potrebbe essere un po 'più veloce se si è fortunati a raccogliere il percorso del nodo foglia contiene il nodo a cui sei interessato. (Non deve necessariamente attraversare tutti i nodi).

Answer 4

Una prospettiva per capire: BFS in un grafico senza peso e direzione è uguale a Dijkstra (peso = 1, una direzione), quindi capire perché Dijkstra ha ragione potrebbe aiutare. Maggiori dettagli saranno aggiunti se avrò fatto attraverso.