Rilasciato · in miglioramento
Algorithm
Il backtracking costruisce una soluzione passo dopo passo e annulla le scelte che violano un vincolo, per permutazioni, N regine e sudoku.
Il backtracking costruisce la risposta un passo alla volta esplorando in profondità un albero degli stati e, appena le scelte fatte violano un vincolo, torna al passo precedente per provare un'altra opzione. Il codice ripete tre azioni: scegliere un candidato, esplorare ricorsivamente e annullare la scelta al ritorno.
A differenza della forza bruta, che genera ogni candidato completo prima di verificarlo, il backtracking pota presto i rami senza speranza e spesso risolve lo stesso problema con ordini di grandezza di passi in meno. È l'approccio standard per elencare permutazioni e combinazioni e per i problemi di soddisfacimento di vincoli come le N regine, il sudoku o la colorazione dei grafi, ed è alla base dei motori di espressioni regolari e dei solutori SAT: lo si incontra quindi sia nei colloqui tecnici sia nel codice in produzione.
Conviene partire da enumerazioni senza potatura, come sottoinsiemi e permutazioni, per imparare lo schema scegliere, esplorare, annullare. Poi si passa al controllo dei vincoli e alla potatura con le N regine e il sudoku. Infine si contano i nodi visitati per vedere l'effetto della potatura e si confrontano gli stessi problemi con la programmazione dinamica.
Con lo stato vuoto come radice e ogni scelta come arco, ogni candidato diventa un cammino che il backtracking percorre in profondità.
Si aggiunge un candidato alla soluzione parziale, si scende ricorsivamente e lo si rimuove al ritorno, così tutti i rami condividono un'unica lista.
Se una soluzione parziale non può più portare a una risposta, si salta l'intero sottoalbero, riducendo in pratica uno spazio di ricerca esponenziale.
Tenere in insiemi o array colonne, diagonali, righe o riquadri già occupati permette di capire in tempo costante se una scelta viola una regola.
permutations blocca con un array used gli elementi già scelti e genera tutte le permutazioni con lo schema scegliere, esplorare, annullare, salvando ogni cammino completo come copia con path[:]. n_queens tiene in insiemi le colonne e le due diagonali (row - c, row + c), salta subito le caselle attaccate e conta le soluzioni. Eseguendo python backtracking.py si stampano le 6 permutazioni di [1, 2, 3] e 92, il numero di soluzioni per 8 regine.
backtracking.py
def permutations(items):
result, path = [], []
used = [False] * len(items)
def backtrack():
if len(path) == len(items):
result.append(path[:]) # store a copy of the full path
return
for i, x in enumerate(items):
if used[i]:
continue
used[i] = True # choose
path.append(x)
backtrack() # explore
path.pop() # unchoose
used[i] = False
backtrack()
return result
def n_queens(n):
cols, diag, anti = set(), set(), set()
def place(row):
if row == n:
return 1
count = 0
for c in range(n):
if c in cols or row - c in diag or row + c in anti:
continue # prune: square is attacked
cols.add(c); diag.add(row - c); anti.add(row + c)
count += place(row + 1)
cols.remove(c); diag.remove(row - c); anti.remove(row + c)
return count
return place(0)
print(permutations([1, 2, 3]))
print(n_queens(8)) # 92
python backtracking.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Backtracking.
Fai domande, condividi la tua esperienza e scambia opinioni su Backtracking.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.