In questo tutorial imparerai cos'è un algoritmo di backtracking. Inoltre, troverai un esempio di approccio al backtracking.
Un algoritmo di backtracking è un algoritmo di risoluzione dei problemi che utilizza un approccio di forza bruta per trovare l'output desiderato.
L'approccio della forza bruta prova tutte le possibili soluzioni e sceglie le soluzioni desiderate / migliori.
Il termine backtracking suggerisce che se la soluzione corrente non è adatta, tornare indietro e provare altre soluzioni. Pertanto, la ricorsione viene utilizzata in questo approccio.
Questo approccio viene utilizzato per risolvere problemi che hanno più soluzioni. Se vuoi una soluzione ottimale, devi optare per la programmazione dinamica.
State Space Tree
Un albero degli stati spaziali è un albero che rappresenta tutti i possibili stati (soluzione o non soluzione) del problema dalla radice come stato iniziale alla foglia come stato terminale.
State Space Tree
Algoritmo di backtracking
Backtrack (x) se x non è una soluzione restituisce false se x è una nuova soluzione aggiungi all'elenco delle soluzioni backtrack (espandi x)
Esempio di approccio al backtracking
Problema: vuoi trovare tutti i modi possibili per disporre 2 ragazzi e 1 ragazza su 3 panchine. Vincolo: la ragazza non dovrebbe essere sulla panchina centrale.
Soluzione: ce ne sono 3 in totale! = 6 possibilità. Proveremo tutte le possibilità e otterremo le possibili soluzioni. Proviamo ricorsivamente tutte le possibilità.
Tutte le possibilità sono:
Tutte le possibilità
Il seguente albero dello spazio degli stati mostra le possibili soluzioni.
Albero degli stati con tutte le soluzioni
Backtracking Algorithm Applications
- Per trovare tutti i Percorsi Hamiltoniani presenti in un grafico.
- Per risolvere il problema N Queen.
- Problema risolvente labirinto.
- Il problema del tour del cavaliere.
