Backtracking

Ricerca con backtracking

Il backtracking (in italiano, si può definire "monitoraggio a ritroso") è una tecnica per trovare soluzioni a problemi in cui devono essere soddisfatti dei vincoli. Questa tecnica enumera tutte le possibili soluzioni e scarta quelle 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.

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.

Esempi

Un problema risolvibile con questo metodo è quello della soddisfacibilità booleana 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 ${\displaystyle x\land y}$, la tecnica procede nel seguente modo:

x	y	${\displaystyle x\land y}$	Passaggio
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 "SI" if x and y else "NO"

vals = [False, True]
print("x\ty")
for x in vals:
    for y in vals:
        print(f"{x}\t{y}\t{prop(x,y)}")

Produce come risultato:

x       y
False   False   NO
False   True    NO
True    False   NO
True    True    SI

Voci correlate

• Prolog
• Ricerca operativa

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul backtracking

Collegamenti esterni

• Backtracking, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• Backtracking, su Vocabolario Treccani, Istituto dell'Enciclopedia Italiana.
• backtracking, su sapere.it, De Agostini.
• (EN) Eric W. Weisstein, Backtracking, su MathWorld, Wolfram Research.