Come si esce da un labirinto? Ecco tre strategie infallibili

Immaginiamo di trovarci all’ingresso di un labirinto. Sappiamo solo che c’è sicuramente un’uscita lungo il perimetro, ma non sappiamo dove si trova. Se entriamo in questo labirinto, come possiamo essere sicuri di riuscire ad uscire? E saremmo in grado di trovare il percorso più breve? Se non possiamo vedere il labirinto dall’alto, ci sono tre possibili strategie che possiamo sfruttare per essere certi di uscire: la regola della “mano destra”, l’algoritmo di Tremaux e gli algoritmi di “breadth-first search”. Questi algoritmi di risoluzione di labirinti non soltanto esercizi di orientamento, ma vengono applicati anche nell’informatica, nella robotica e nei videogiochi. In questo articolo vediamo come funzionano e quali sono le possibili soluzioni per uscire da un labirinto.

Uscire da un labirinto, la regola della mano: la appoggiamo sul muro all’entrata, poi seguiamo il muro 

“La regola della mano destra (o sinistra)” ci permette di risolvere un labirinto anche ad occhi chiusi. Questo è uno degli algoritmi più semplici: all’ingresso decidiamo che mano usare e che lato del muro seguire. Appoggiamo la mano al muro e poi iniziamo a camminare senza mai staccarla. Con questa tecnica siamo certi di riuscire a trovare l’uscita in tutti i labirinti che hanno una sola entrata e una sola uscita. Attenzione, però, che non possiamo usarla se ci troviamo già dentro il labirinto e ci siamo persi. In quel caso, potremmo mettere per sbaglio la mano su un “ciclo” o “isola”, cioè un insieme di muri disconnessi dal muro principale, come quelli colorati in blu nell’immagine. Se mettessimo la mano su uno di questi muri e continuassimo a seguirli usando la regola della mano destra, ci troverremo a girare in loop senza arrivare mai all’uscita.

Una strategia che ci permette di trovare la soluzione in tutti i tipi di labirinti, anche quelli in cui ci sono dei loop o in cui l’obiettivo non è trovare l’uscita, ma una stanza centrale con un premio, è l’algoritmo di Trémaux, un algoritmo di depth-first search.

Torniamo indietro se troviamo un vicolo cieco, un incrocio già visto e segniamo dove siamo già passati

Per poter utilizzare l’algoritmo di Trémaux, dobbiamo portarci dietro qualcosa per marchiare gli incroci e le strade che stiamo incontrando. Con questo algoritmo infatti, dobbiamo prendere nota di ogni bivio, esplorare ogni strada a fondo e, ogni volta che raggiungiamo un vicolo cieco o un loop, tornare all'ultimo incrocio e provare un percorso diverso. Questa strategia è nota come “ricerca in profondità” (depth-first search) e consiste nell’andare il più a fondo possibile nel labirinto e tornare indietro solo quando non può più andare avanti.

Concretamente, quello che accade è che iniziamo a camminare nel labirinto seguendo la strada fino a che non arriviamo ad un vicolo cielo (in quel caso torniamo indietro) o un incrocio. A questo punto, ci sono tre possibilità:

• È la prima volta che arriviamo a quell’incrocio: Se è la prima volta che vediamo quell'incrocio, segniamo il percorso da cui siamo arrivati, poi scegliamo arbitrariamente una direzione in cui proseguire e segniamo anche quella.
• È la seconda volta che arriviamo a quell’incrocio, ma da un’altra direzione: Se abbiamo già visto quell'incrocio ma non ci eravamo ancora arrivati da questa direzione, allora segniamo l’attacco tra la direzione da cui siamo arrivati e l’incrocio con due segni (o con una "x") e poi torniamo indietro. Un percorso con due segni è trattato come un muro e non possiamo percorrerlo di nuovo. Questo meccanismo ci permette di sfuggire ai loop.
• Siamo già stati in quelli in quell’incrocio e ci arriviamo da una strada già vista: Se l'incrocio è già stato visitato e arriviamo da un percorso che ha già un segno, allora lo segniamo una seconda volta e scegliamo arbitrariamente una direzione tra i percorsi senza segni, se ce ne sono, oppure tra i percorsi con un solo segno. In ogni caso, aggiungiamo un segno alla direzione scelta.

Questo algoritmo riesce a risolvere tutti i tipi di labirinti e, mettendo due segni per chiudere le strade che non portano alla soluzione, permette a chi arriva dopo di noi di non perdersi e di arrivare all’uscita, perché sanno che devono trattare quei due segni per terra come se fossero dei muri e seguire solo le strade con un unico segno. Questo metodo, però, non garantisce che la strada che mostreremo agli altri sarà la più breve. Per farlo, dobbiamo usare la "ricerca in ampiezza", non in profondità.

Trovare il percorso più breve: esplorare in ampiezza, non in profondità

La “ricerca in ampiezza” (breadth-first search) è una strategia imparentata con l'algoritmo di Trémaux, ma, anziché esplorare le vie che trova fino in fondo, questo algoritmo punta ad esplorare tutte le possibilità, così da non perdersi la soluzione più breve, quella che ottimizza il tragitto. Questo algoritmo ci garantisce che riusciremo a trovare il percorso più breve tra l'entrata e l'uscita, ma ci impiegheremo moltissimo tempo. Se seguiamo questa strategia, camminiamo fino ad un incrocio A, poi scegliamo una direzione arbitraria e continuiamo a camminare fino a che non incontriamo un altro incrocio (B). A questo punto, torniamo indietro per controllare la strada che avevamo precedentemente ignorato (quella restante dell’incrocio A) e continuiamo fino a trovare l’incrocio C. Una volta visto l'incrocio C, ritorniamo all’incrocio B per esplorare le altre possibilità facendo avanti e indietro parecchie volte. Per fare quanto abbiamo descritto, l'algoritmo sostanzialmente riduce il labirinto a un diagramma, per poi trovare la strada più breve tra un estremo all'altro.

Per farlo, percorre tutte le strade fino a che non troviamo l'uscita percorrendo e ripercorrendo i sentieri del labirinto/diagramma decine e decine di volte. Come possiamo immaginare, questo algoritmo è utile solo se siamo dei maratoneti o se possiamo fare le simulazioni al computer e poi seguire la strada più breve che ci indica.

non perderti questo video

La logica del Sudoku: come funziona e quali sono le tecniche per risolverlo