Spiegate BFS e DFS in termini di backtracking

Question

Wikipedia ricerca in profondità:

profondità prima ricerca (DFS) è un algoritmo per l'attraversamento o la ricerca un albero, struttura ad albero, o un grafico. Uno inizia nella radice (selezionando un nodo come root nel caso del grafico) ed esplora il più lontano possibile lungo ogni ramo prima del backtracking.

Quindi, qual è la larghezza Prima ricerca?

"un algoritmo che seleziona il partendo nodo, controlla tutti i nodi Backtracks, sceglie il percorso più breve, scelto nodi vicini Backtracks, scelsero il percorso più breve, infine trova il percorso ottimale perché di attraversamento ciascun percorso a causa di continue indietreggiamento.

Regex 012.396 La potatura di- backtracking?

Il termine backtracking confonde a causa della sua varietà di utilizzo. find di UNIX per la potatura di un utente SO spiegato con il backtracking. Regex Buddy usa il termine "backtracking catastrofico" se non limiti l'ambito dei tuoi Regex. Sembra essere un termine ombrello troppo usato. Quindi:

1. Come si definisce "backtracking" specificamente per Teoria dei grafi?
2. Che cos'è il "backtracking" in Larghezza Prima ricerca e profondità Prima ricerca?

[Aggiunto]

Buone definizioni su backtracking ed esempi

1. The Brute-force method
2. di Stallman (?) Inventato termine "dependency-directed backtracking"
3. Backtracking e regex esempio
4. Depth First Search definition.

Answer 1

La confusione è disponibile in causa backtracking è qualcosa che accade durante la ricerca, ma si riferisce anche ad una specifica tecnica di problem-solving in cui viene fatto un sacco di backtracking. Tali programmi sono chiamati backtrackers.

Immagine di guida in un quartiere, tenendo sempre il primo turno che si vede (supponiamo che non ci siano loop) finché non si raggiunge un punto morto, a quel punto si ritorna all'intersezione della successiva strada non visitata. Questo è il "primo" tipo di backtracking, ed è approssimativamente equivalente all'utilizzo colloquiale della parola.

L'utilizzo più specifico si riferisce a una strategia di risoluzione dei problemi simile alla ricerca in profondità, ma al backtrack quando si rende conto che non vale la pena continuare su alcuni sottoalberi.

In un altro modo: un DFS ingenuo visita ciecamente ciascun nodo fino a raggiungere l'obiettivo. Sì, "backtracks" sui nodi foglia. Ma un backtracker anche i backtrack su rami inutili. Un esempio è la ricerca di una scheda di boggle per le parole. Ogni tessera è circondata da altri 8, quindi l'albero è enorme e DFS ingenuo può richiedere troppo tempo. Ma quando vediamo una combinazione come "ZZQ", possiamo tranquillamente fermare la ricerca da questo punto, dal momento che aggiungere più lettere non farà una parola.

Amo queste conferenze della prof.ssa Julie Zelenski. Risolve 8 regine, un rompicapo di sudoku e un puzzle di sostituzione dei numeri usando il backtracking, e tutto è ben animato. Programming Abstractions, Lecture 10 Programming Abstractions, Lecture 11

Un albero è un grafico in cui ogni coppia di vertici hanno un solo percorso tra di loro. Questo elimina la possibilità di cicli. Quando stai cercando un grafico, di solito hai una logica per eliminare comunque i cicli, quindi il comportamento è lo stesso. Inoltre, con un grafico diretto, non puoi seguire i bordi nella direzione "sbagliata".

Da quello che posso dire, nel documento Stallman hanno sviluppato un sistema logico che non si limita a dire "sì" o "no" su una query ma in realtà suggerisce correzioni per query errate facendo il minor numero di modifiche. Puoi vedere dove potrebbe entrare in gioco la prima definizione di backtracking.