Backtracking
Il backtracking è una tecnica di ricerca delle soluzioni di un problema. La tecnica del backtracking esplora in profondità le possibili soluzioni in un albero di ricerca a partire da un nodo di origine fino all'ultimo nodo successore del ramo. Una volta analizzato il nodo in profondità ( ricerca in profondità ) l'algoritmo torna indietro per visitare il nodo predecessore più vicino, non ancora esplorato, appartenente al medesimo ramo. La tecnica del backtracking permette di analizzare in profondità l'insieme delle varie soluzioni alternative al fine di selezionare la soluzione migliore.
Il backtracking è caratterizzato da una complessità esponenziale. La complessità cresce in modo più che proporzionale rispetto al fattore di ramificazione. È una tecnica poco efficiente per analizzare problemi non NP-completi. Per ridurre la complessità dell'algoritmo di backtracking si ricorre spesso alle tecniche euristiche.
Scelte irreversibili. La tecnica del backtracking è utilizzata nella ricerca off-line. Nel caso della ricerca online l'uso del backtracking è, invece, condizionata al fatto che le scelte siano reversibili. In tale caso una mossa irreversibile causerebbe l'interruzione permanente dell'esplorazione di ricerca poiché l'agente di ricerca non potrebbe tornare indietro ( backtracking ) sul nodo predecessore. È importante sottolineare che tale rischio può presentarsi anche in caso di scelte reversibili se l'ambiente operativo è dinamico, parzialmente osservabile e non è sicuro.
Backjumping. Una variante della ricerca backtracking è la ricerca backjumping. La ricerca backjumping consente di effettuare un "salto all'indietro" ( backjumping ) dalla variabile corrente all'ultima variabile conflittuale, evitando così di dover prima analizzare tutte le varianti di assegnazione dei valori nelle ultime variabili cronologiche non conflittuali. Questa tecnica è particolarmente più utile ed efficiente, rispetto al semplice backtracking, nella soluzione dei problemi con vincoli CSP ( problema di soddisfacimento dei vincoli ).
