Backtracking

Da Wikipedia, l'enciclopedia libera.
Ricerca con backtracking

Il backtracking (in italiano, ritorno all'indietro) è 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[modifica | modifica wikitesto]

I possibili tipi di backtracking sono molti, con funzionamento diverso, caratteristiche diverse e vantaggi diversi. I più conosciuti sono:

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[modifica | modifica wikitesto]

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 x \and y, la tecnica procede nel seguente modo:

x y x \and 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")

Produce come risultato

x= False
y= False        NO
y= True         NO

x= True
y= False        NO
y= True         SI

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]