L’algoritmo di backtracking enumera un insieme di candidati parziali che, in linea di principio, potrebbero essere completati in vari modi per dare tutte le possibili soluzioni al problema dato. Il completamento viene eseguito in modo incrementale, da una sequenza di passaggi di estensione candidati.
Concettualmente, i candidati parziali sono rappresentati come i nodi di una struttura ad albero, l’albero di ricerca potenziale. Ogni candidato parziale è il genitore dei candidati che differiscono da esso per un singolo passaggio di estensione; le foglie dell’albero sono i candidati parziali che non possono essere estesi ulteriormente.
L’algoritmo di backtracking attraversa questo albero di ricerca in modo ricorsivo, dalla radice verso il basso, in profondità-primo ordine. Ad ogni nodo c, l’algoritmo controlla se c può essere completato in una soluzione valida. Se non può, l’intero sottoalbero radicato a c viene saltato (potato). Altrimenti, l’algoritmo (1) controlla se c stesso è una soluzione valida e, in tal caso, la segnala all’utente; e (2) enumera ricorsivamente tutti i sottoalberi di c. I due test e i figli di ciascun nodo sono definiti dalle procedure specificate dall’utente.
Pertanto, l’albero di ricerca effettivo attraversato dall’algoritmo è solo una parte dell’albero potenziale. Il costo totale dell’algoritmo è il numero di nodi dell’albero effettivo volte il costo di ottenere ed elaborare ciascun nodo. Questo fatto dovrebbe essere considerato quando si sceglie l’albero di ricerca potenziale e si implementa il test di potatura.
PseudocodeEdit
Per applicare il backtracking a una specifica classe di problemi, è necessario fornire i dati P per la particolare istanza del problema che deve essere risolto e sei parametri procedurali, root, reject, accept, first, next e output. Queste procedure dovrebbero prendere i dati dell’istanza P come parametro e dovrebbero fare quanto segue:
- root (P): restituisce il candidato parziale alla radice dell’albero di ricerca.
- reject (P,c): restituisce true solo se il candidato parziale c non vale la pena di essere completato.
- accetta(P,c): restituisce true se c è una soluzione di P e false altrimenti.
- first (P, c): genera la prima estensione del candidato c.
- next(P,s): genera la prossima estensione alternativa di un candidato, dopo l’estensione s.
- output(P,c): usa la soluzione c di P, a seconda dell’applicazione.
L’algoritmo di backtracking riduce il problema alla chiamata backtrack(root (P)), dove backtrack è la seguente procedura ricorsiva:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
Usage considerationsEdit
La procedura di rifiuto dovrebbe essere una funzione con valore booleano che restituisce true solo se è certo che nessuna possibile estensione di c è una soluzione valida per P. Se la procedura non può raggiungere una conclusione definitiva, dovrebbe restituire false. Un risultato vero non corretto può far perdere alla procedura bt alcune soluzioni valide. La procedura può presumere che reject (P,t) abbia restituito false per ogni antenato t di c nell’albero di ricerca.
D’altra parte, l’efficienza dell’algoritmo di backtracking dipende dal rifiuto di restituire true per i candidati che sono il più vicino possibile alla radice. Se reject restituisce sempre false, l’algoritmo troverà comunque tutte le soluzioni, ma sarà equivalente a una ricerca a forza bruta.
La procedura accept dovrebbe restituire true se c è una soluzione completa e valida per l’istanza del problema P e false altrimenti. Si può supporre che il candidato parziale c e tutti i suoi antenati nell’albero abbiano superato il test di rifiuto.
Lo pseudo-codice generale sopra non presuppone che le soluzioni valide siano sempre foglie dell’albero di ricerca potenziale. In altre parole, ammette la possibilità che una soluzione valida per P possa essere ulteriormente estesa per produrre altre soluzioni valide.
La prima e la successiva procedura vengono utilizzate dall’algoritmo di backtracking per enumerare i figli di un nodo c dell’albero, ovvero i candidati che differiscono da c da un singolo passaggio di estensione. La chiamata first (P,c) dovrebbe produrre il primo figlio di c, in un certo ordine; e la chiamata next (P,s) dovrebbe restituire il prossimo fratello del nodo s, in quell’ordine. Entrambe le funzioni dovrebbero restituire un candidato “NULL” distintivo, se il figlio richiesto non esiste.
Insieme, le funzioni root, first e next definiscono l’insieme di candidati parziali e l’albero di ricerca potenziale. Dovrebbero essere scelti in modo che ogni soluzione di P si verifichi da qualche parte nell’albero e nessun candidato parziale si verifichi più di una volta. Inoltre, dovrebbero ammettere un predicato di rifiuto efficiente ed efficace.
Early stopping variantsEdit
Lo pseudo-codice di cui sopra chiamerà output per tutti i candidati che sono una soluzione per l’istanza data P. L’algoritmo può essere modificato per fermarsi dopo aver trovato la prima soluzione, o un numero specificato di soluzioni; o dopo aver testato un numero specificato di candidati parziali, o dopo aver trascorso una