Era il 1986, un giovane di belle speranze chiamato Eros Ramazzotti vinse il 36° Festival di Sanremo con il brano “Adesso tu” in cui canta “andare avanti senza arrivare mai".
Questa potrebbe non essere la strategia migliore anche nel risolvere tanti problemi algoritmici, per i quali, invece, è meglio andare avanti finché possibile, per poi tornare indietro e provare un'altra strada.
In inglese, questo procedere guardingo porta il nome poco poetico di backtracking.
Lo troviamo implementato in un algoritmo di ricerca in profondità (DFS) per la creazione di quei labirinti che, specie in estate, popolano le riviste di giochi e passatempi.
Alcuni di essi sembrano partoriti dalla mente del mitico Dedalo, talmente appaiono intricati: decine di bivi separano l'ingresso dall'uscita e un solo percorso è quello giusto (labirinto perfetto). Noi, sotto l’ombrellone, siamo avvantaggiati nell'impresa perché possiamo contare su una bellissima vista aerea dell'intera “struttura”, ma provate solo a immaginare le difficoltà di un povero Teseo senza il provvidenziale filo.
Come funziona il backtracking?
In inglese, questo procedere guardingo porta il nome poco poetico di backtracking.
Lo troviamo implementato in un algoritmo di ricerca in profondità (DFS) per la creazione di quei labirinti che, specie in estate, popolano le riviste di giochi e passatempi.
Alcuni di essi sembrano partoriti dalla mente del mitico Dedalo, talmente appaiono intricati: decine di bivi separano l'ingresso dall'uscita e un solo percorso è quello giusto (labirinto perfetto). Noi, sotto l’ombrellone, siamo avvantaggiati nell'impresa perché possiamo contare su una bellissima vista aerea dell'intera “struttura”, ma provate solo a immaginare le difficoltà di un povero Teseo senza il provvidenziale filo.
Come funziona il backtracking?
Sostanzialmente consiste in una funzione (nel codice che ho messo a punto è un metodo di classe) che richiama sé stessa un numero imprecisato di volte fino al verificarsi di certe condizioni (funzione ricorsiva).
def genera_labirinto(self, x, y):
self.visitato[y, x] = True
self.griglia[y, x] = 0 # Segna il passaggio
random.shuffle(self.direzioni)
for dy, dx in self.direzioni:
nx, ny = x + dx, y + dy
if 0 <= nx < self.larghezza and 0 <= ny < self.altezza and not self.visitato[ny, nx]:
self.griglia[y + dy // 2, x + dx // 2] = 0 # Rimuove il muro intermedio
self.genera_labirinto(nx, ny)
self.griglia[y, x] = 0 # Segna il passaggio
random.shuffle(self.direzioni)
for dy, dx in self.direzioni:
nx, ny = x + dx, y + dy
if 0 <= nx < self.larghezza and 0 <= ny < self.altezza and not self.visitato[ny, nx]:
self.griglia[y + dy // 2, x + dx // 2] = 0 # Rimuove il muro intermedio
self.genera_labirinto(nx, ny)
Spiegazione:
- L'algoritmo marca la cella corrente (x, y) come visitata.
- Tenta di esplorare tutte le direzioni possibili (randomizzate).
- Il backtracking si verifica quando:
- l'algoritmo raggiunge una cella da cui non può più avanzare (tutte le celle adiacenti sono già state visitate o sono fuori dai limiti).
- oppure ha finito di esplorare tutte le direzioni possibili da una cella; a questo punto, l'esecuzione torna indietro (backtrack) alla chiamata precedente nella pila di ricorsione.
- Al termine della chiamata ricorsiva self.genera_labirinto(nx, ny), il controllo torna alla funzione chiamante per provare la direzione successiva nel ciclo for.
Esempio pratico:
Supponiamo di essere in una cella (5, 5).
- L'algoritmo prova a spostarsi in una direzione, ad esempio a destra verso (7, 5).
- Dalla cella (7, 5)
continua l'esplorazione ricorsivamente. - Quando l'esplorazione da (7, 5) finisce, l'algoritmo fa backtracking tornando a (5, 5).
- Da (5, 5) prova poi a esplorare un'altra direzione, ad esempio verso il basso (5, 7).
- Questo processo continua finché tutte le direzioni da (5, 5) sono state esplorate.
- A quel punto, fa backtracking alla cella precedente da cui siamo arrivati.
Alcune delle principali tipologie di labirinto
- Labirinto perfetto, quello di questo esempio (senza cicli)
- Labirinto imperfetto (con cicli)
- Labirinto a corridoi largamente spaziati
- Labirinto con stanze e corridoi
- Labirinto con struttura gerarchica (tipo albero)
- Labirinto a griglia esagonale
- Labirinto estremo (difficoltà massima)
