Backtracking
Da Wikipedia, l'enciclopedia libera.
Il backtracking (in italiano, ritorno all'indietro) è una tecnica per trovare soluzioni a problemi in cui devono essere soddisfatti dei vincoli. Con questa tecnica si considerano successivamente tutte le possibili soluzioni, scartando man mano le condizioni che non soddisfano i vincoli.
Una tecnica classica consiste nell'esplorazione di strutture ad albero e tenere traccia di tutti i nodi e i rami visitati in precedenza, in modo da poter tornare indietro al più vicino nodo che conteneva un cammino ancora inesplorato nel caso che la ricerca nel ramo attuale non abbia successo. I nodi a profondità uguale rappresentano i possibili valori di una variabile.
Una applicazione del backtracking è nei programmi per giocare a scacchi, che generano tutte le mosse possibili per una profondità di N mosse a partire da quella attuale e poi esaminano con il backtracking le varie alternative, selezionando alla fine quella migliore.
Il backtracking ha una complessità esponenziale, quindi è poco efficiente nell'affrontare problemi che non siano NP-completi. In generale, comunque, l'algoritmo integra euristiche che permettono di diminuirne la complessità.
Questa tecnica è alla base del linguaggio di programmazione Prolog.
[modifica] Tipi di Backtracking
I possibili tipi di backtracking sono molti, con funzionamento diverso, caratteristiche diverse e vantaggi diversi. I più conosciuti sono:
- Backtracking cronologico(BT).
- Backjumping (BJ).
- Conflict-Directed backjumping (CBJ).
- Forward checking with simple backtracking (FC).
- Backmarking with simple backtracking (BM).
I primi quattro algoritmi vengono definiti algoritmi fondamentali, in quanto rappresentano diverse “filosofie” di base e diversi metodi per mettere in pratica il backtracking; mentre l'ultimo è invece un noto esempio di algoritmo ibrido, cioè un algoritmo che può essere considerato una variazione degli algoritmi fondamentali, ma che proprio per la sua differenza dagli algoritmi da cui deriva può portare numerosi vantaggi.
[modifica] Esempi
Un problema risolvibile con questo metodo è quello della soddisfacibilità di una proposizione in logica del primo ordine (K-SAT). L'algoritmo procede impostando il valore di ogni variabile, finché la formula non è soddisfatta (supponiamo che sia soddisfacibile).
Per semplicità prendiamo la formula 
, la tecnica procede nel seguente modo:
| x | y | |
|
|---|---|---|---|
| Falso | Falso | Falso | backtrace di y |
| Falso | Vero | Falso | backtrace di x |
| Vero | Falso | Falso | backtrace di y |
| Vero | Vero | Vero | Soluzione |
L'esempio in forma di codice Python (il codice non si ferma quando trova il risultato):
def prop(x,y):
return (x and y)
vals = [False, True]
for x in vals:
print "x=",x
for y in vals:
print "y=",y,
if prop(x,y):
print "\tSI"
else:
print "\tNO"
print
Produce come risultato
x= False y= False NO y= True NO x= True y= False NO y= True SI
