Algoritmi per la risoluzione di labirinti

Esistono diversi algoritmi di risoluzione dei labirinti, ovvero metodi automatizzati per la risoluzione dei labirinti. Gli algoritmi random mouse, wall follower, Pledge e Trémaux sono progettati per essere utilizzati all'interno del labirinto da un viaggiatore senza alcuna conoscenza del labirinto, mentre gli algoritmi di riempimento del vicolo cieco e del cammino minimo sono progettati per essere utilizzati da una persona o programma per computer in grado di vedere l'intero labirinto in una volta.

I labirinti che non contengono anelli sono conosciuti come labirinti "semplicemente connessi" o "perfetti" e sono equivalenti a un albero nella teoria dei grafi. Pertanto, molti algoritmi di risoluzione dei labirinti sono strettamente correlati alla teoria dei grafi. Intuitivamente, se uno tirasse e allungasse i percorsi nel labirinto nel modo corretto, il risultato potrebbe essere fatto per assomigliare ad un albero.^[1]

Questo è un metodo banale che può essere implementato da un robot molto poco intelligente o forse da un topo. Bisogna semplicemente procedere seguendo il passaggio corrente fino al raggiungimento di un incrocio, quindi prendere una decisione casuale sulla direzione successiva da seguire. Sebbene un tale metodo alla fine troverebbe sempre la soluzione giusta, questo algoritmo può essere estremamente lento.

Il wall follower, la regola più nota per attraversare i labirinti, è anche noto come regola della mano sinistra o della mano destra. Se il labirinto è semplicemente collegato, cioè tutte le sue pareti sono collegate insieme o al confine esterno del labirinto, mantenendo una mano in contatto con una parete del labirinto si garantisce che il risolutore raggiungerà un'uscita diversa se ce n'è una; in caso contrario, tornerà all'ingresso dopo aver attraversato tutti i corridoi accanto a quella sezione di pareti collegate almeno una volta.

Un'altra prospettiva sul perché i wall following funzionano è topologica. Se le pareti fossero collegate, potrebbero essere deformate in un anello o cerchio.^[2] Quindi il wall follower si riduce a camminare attorno a un cerchio dall'inizio alla fine. Per favorire questa idea, notate che raggruppando insieme componenti collegati delle pareti del labirinto, i confini tra queste sono precisamente le soluzioni, anche se esiste più di una soluzione (vedere le figure a destra).

Se il labirinto non è semplicemente collegato (ovvero se l'inizio o gli estremi sono al centro della struttura circondati da anelli di passaggio o i percorsi si incrociano e si sovrappongono e tali parti del percorso della soluzione sono circondate da anelli di passaggio), questo metodo non raggiungerà l'obiettivo.

Un'altra preoccupazione è che si dovrebbe fare attenzione a iniziare a seguire le pareti all'ingresso del labirinto. Se il labirinto non è semplicemente collegato e si inizia a seguire il muro in un punto arbitrario all'interno del labirinto, ci si potrebbe trovare intrappolati lungo un muro separato che gira su sé stesso e che non contiene ingressi o uscite. Nel caso in cui il wall follower inizi in ritardo, si provi a segnare la posizione in cui è iniziato il wall following. Poiché seguire il muro riporterà sempre al punto di partenza, se ci si imbatte nel proprio punto di partenza una seconda volta, si può concludere che il labirinto non è semplicemente collegato e si dovrebbe passare a un muro alternativo non ancora seguito. Si veda l'algoritmo di Pledge, di seguito, per una metodologia alternativa.

Seguire le pareti può essere fatto in labirinti tridimensionali o di dimensioni superiori se i suoi passaggi di dimensioni superiori possono essere proiettati su un piano in modo deterministico. Ad esempio, se in un labirinto tridimensionale si può presumere che i passaggi "su" conducano a nord-ovest e che i passaggi "giù" possano condurre a sud-est, allora possono essere applicate le seguenti regole standard. Tuttavia, a differenza del caso a 2 dimensioni, ciò richiede che l'orientamento corrente sia noto, per determinare quale direzione è la prima a sinistra o a destra.

I labirinti possono essere risolti con il metodo del wall follower, a condizione che l'ingresso e l'uscita del labirinto siano sulle pareti esterne del labirinto. Se tuttavia, il risolutore inizia all'interno del labirinto, potrebbe trovarsi in una sezione disgiunta dall'uscita e l'utilizzatore continuerà a girare intorno al proprio anello. L'algoritmo Pledge (che prende il nome da Jon Pledge di Exeter) può risolvere questo problema.^[3][4]

L'algoritmo Pledge, progettato per aggirare gli ostacoli, richiede una direzione scelta arbitrariamente verso cui andare, che sarà preferenziale. Quando viene incontrato un ostacolo, una mano (diciamo la mano destra) viene mantenuta lungo l'ostacolo mentre vengono contati gli angoli ruotati (la rotazione in senso orario è positiva, la rotazione in senso antiorario è negativa). Quando il solutore si trova di nuovo nella direzione preferenziale originale, e la somma angolare delle virate eseguite è 0, il solutore lascia l'ostacolo e continua a muoversi nella sua direzione originale.

La mano viene rimossa dal muro solo quando sia la "somma dei giri effettuati" che la "direzione corrente" sono a zero. Ciò consente all'algoritmo di evitare trappole a forma di lettera maiuscola "G". Supponendo che l'algoritmo giri a sinistra al primo muro, ci si gira a 360 gradi dalle pareti. Un algoritmo che tiene traccia della "direzione corrente" conduce in un ciclo infinito in quanto lascia la direzione del muro più in basso a destra a sinistra e corre di nuovo nella sezione curva sul lato sinistro. L'algoritmo Pledge non lascia il muro più a destra a causa del fatto che la "somma dei giri effettuati" non è zero in quel punto (nota 360 gradi non è uguale a 0 gradi). Segue il muro tutt'intorno, lasciandolo infine a sinistra fuori e proprio sotto la forma della lettera.

Questo algoritmo consente a una persona con una bussola di orientarsi da qualsiasi punto all'interno verso un'uscita esterna di qualsiasi labirinto bidimensionale finito, indipendentemente dalla posizione iniziale del solutore. Tuttavia, questo algoritmo non funzionerà nel fare il contrario, vale a dire trovare la strada da un'entrata all'esterno di un labirinto a un obiettivo finale al suo interno.

L'algoritmo di Trémaux, inventato da Charles Pierre Trémaux,^[5] è un metodo efficace per trovare la via d'uscita da un labirinto che richiede di tracciare linee sul pavimento per segnare un percorso ed è garantito che funzioni per tutti i labirinti che hanno passaggi ben definiti,^[6] ma non è garantito il percorso più breve.

L'algoritmo funziona secondo le seguenti regole:

• Segna ogni percorso una volta, quando lo segui. I segni devono essere visibili su entrambe le estremità del percorso. Pertanto, se vengono creati come segni fisici, anziché archiviati come parte di un algoritmo informatico, lo stesso segno dovrebbe essere fatto ad entrambe le estremità del percorso.
• Non seguire mai un percorso che ha già due segni su di esso.
• Se arrivate a un incrocio che non ha segni (tranne forse per quello sul percorso in cui siete entrati), scegliete un percorso arbitrario non contrassegnato, seguitelo e contrassegnatelo.
• Altrimenti:
  • Se il percorso in cui sei entrato ha un solo segno, girati e ritorna lungo quel percorso, segnandolo di nuovo. In particolare, questo caso dovrebbe verificarsi ogni volta che si raggiunge un vicolo cieco.
  • In caso contrario, scegli arbitrariamente uno dei percorsi rimanenti con il minor numero di segni (zero se possibile, altrimenti uno), segui quel percorso e contrassegnalo.

Quando finalmente raggiungi la soluzione, i percorsi segnati esattamente una volta indicano una via di ritorno all'inizio. Se non c'è uscita, questo metodo ti riporterà all'inizio dove tutti i percorsi sono contrassegnati due volte. In questo caso, ogni percorso viene percorso esattamente due volte, una volta in ciascuna direzione. La camminata risultante è chiamata doppia traccia bidirezionale.^[7]

Fondamentalmente, questo algoritmo, scoperto nel XIX secolo, è stato usato circa cento anni dopo come ricerca approfondita.^[8][9]

Il riempimento dei vicoli ciechi è un algoritmo per risolvere labirinti che riempie tutti i vicoli ciechi, lasciando vuoti solo i modi corretti. Può essere utilizzato per risolvere labirinti su carta o con un programma per computer, ma non è utile per una persona all'interno di un labirinto sconosciuto poiché questo metodo esamina l'intero labirinto contemporaneamente. Il metodo consiste nel:

1) trovare tutti i vicoli ciechi nel labirinto;

2) "riempire" il percorso da ciascun vicolo cieco fino al raggiungimento di una biforcazione;

3) alcune zone non diventeranno vicoli ciechi fino a quando non verranno rimossi altri vicoli ciechi.

Il riempimento a vicolo cieco non può "tagliare" accidentalmente l'inizio dalla fine poiché ogni fase del processo preserva la topologia del labirinto. Inoltre, il processo non si fermerà "troppo presto" poiché il risultato finale non può contenere vicoli ciechi. Pertanto, se si riempie un vicolo cieco su un labirinto perfetto (labirinto senza anelli), rimarrà solo la soluzione. Se viene fatto su un labirinto parzialmente intrecciato (labirinto con alcuni anelli), allora ogni possibile soluzione rimarrà, ma niente di più.^[10]

Se gli viene data una visione onnisciente del labirinto, un semplice algoritmo ricorsivo può dire come arrivare alla fine. All'algoritmo verrà assegnato un valore X e Y iniziale. Se i valori X e Y non si trovano su un muro, il metodo chiamerà sé stesso con tutti i valori X e Y adiacenti, assicurandosi che non abbia già utilizzato quei valori X e Y prima. Se i valori X e Y sono quelli della posizione finale, salverà tutte le precedenti istanze del metodo come percorso corretto. Ecco un codice di esempio in Java:

int[][] maze = new int[width][height]; // The maze
boolean[][] wasHere = new boolean[width][height];
boolean[][] correctPath = new boolean[width][height]; // The solution to the maze
int startX, startY; // Starting X and Y values of maze
int endX, endY;     // Ending X and Y values of maze

public void solveMaze() {
    maze = generateMaze(); // Create Maze (1 = path, 2 = wall)
    for (int row = 0; row < maze.length; row++)  
        // Sets boolean Arrays to default values
        for (int col = 0; col < maze[row].length; col++){
            wasHere[row][col] = false;
            correctPath[row][col] = false;
        }
    boolean b = recursiveSolve(startX, startY);
    // Will leave you with a boolean array (correctPath) 
    // with the path indicated by true values.
    // If b is false, there is no solution to the maze
}
public boolean recursiveSolve(int x, int y) {
    if (x == endX && y == endY) return true; // If you reached the end
    if (maze[x][y] == 2 || wasHere[x][y]) return false;  
    // If you are on a wall or already were here
    wasHere[x][y] = true;
    if (x != 0) // Checks if not on left edge
        if (recursiveSolve(x-1, y)) { // Recalls method one to the left
            correctPath[x][y] = true; // Sets that path value to true;
            return true;
        }
    if (x != width - 1) // Checks if not on right edge
        if (recursiveSolve(x+1, y)) { // Recalls method one to the right
            correctPath[x][y] = true;
            return true;
        }
    if (y != 0)  // Checks if not on top edge
        if (recursiveSolve(x, y-1)) { // Recalls method one up
            correctPath[x][y] = true;
            return true;
        }
    if (y != height - 1) // Checks if not on bottom edge
        if (recursiveSolve(x, y+1)) { // Recalls method one down
            correctPath[x][y] = true;
            return true;
        }
    return false;
}

L'algoritmo di routing labirinto^[11] è un metodo overhead basso per trovare la strada tra due posizioni qualsiasi del labirinto. L'algoritmo viene inizialmente proposto per il dominio dei multiprocessori di chip (CMP) e garantisce il funzionamento per qualsiasi labirinto basato su griglia. Oltre a trovare percorsi tra due posizioni della griglia (labirinto), l'algoritmo può rilevare quando non esiste un percorso tra l'origine e la destinazione. Inoltre, l'algoritmo deve essere utilizzato da un viaggiatore interno senza alcuna conoscenza precedente del labirinto con complessità di memoria fissa indipendentemente dalle dimensioni del labirinto; che richiedono 4 variabili in totale per trovare il percorso e rilevare le posizioni non raggiungibili. Tuttavia, l'algoritmo non è quello di trovare il percorso più breve.

L'algoritmo di instradamento del labirinto utilizza la nozione di Manhattan distance (MD) e si basa sulla proprietà delle griglie che l'MD incrementa / decrementa esattamente di 1 quando si sposta da una posizione a 4 posizioni vicine. Ecco lo pseudocodice senza la capacità di rilevare posizioni non raggiungibili.

Point src, dst;// Source and destination coordinates
// cur also indicates the coordinates of the current location
int MD_best = MD(src, dst);// It stores the closest MD we ever had to dst
// A productive path is the one that makes our MD to dst smaller
while (cur != dst) {
    if (there exists a productive path) {
        Take the productive path;
    } else {
        MD_best = MD(cur, dst);
        Imagine a line between cur and dst;
        Take the first path in the left/right of the line; // The left/right selection affects the following hand rule
        while (MD(cur, dst) != MD_best || there does not exist a productive path) {
            Follow the right-hand/left-hand rule; // The opposite of the selected side of the line
    }
}

Quando un labirinto ha più soluzioni, il risolutore potrebbe voler trovare il percorso più breve dall'inizio alla fine. Esistono diversi algoritmi per trovare percorsi più brevi, molti dei quali provenienti dalla teoria dei grafi. Uno di questi algoritmi trova il percorso più breve implementando una prima ricerca, mentre un altro, l'algoritmo A *, utilizza una tecnica euristica. L'algoritmo di ricerca breadth-first utilizza una coda per visitare le celle in ordine crescente di distanza dall'inizio fino al raggiungimento del traguardo. Ogni cella visitata deve tenere traccia della sua distanza dall'inizio o quale cella adiacente più vicina all'inizio ha causato l'aggiunta alla coda. Quando viene trovata la posizione finale, segui il percorso delle celle all'indietro fino all'inizio, che è il percorso più breve. La prima ricerca nella sua forma più semplice ha i suoi limiti, come trovare il percorso più breve nei grafici ponderati.

• labirinti
• Algoritmo di generazione del labirinto

• Think Labyrinth: Maze algoritmi, su astrolog.org. (dettagli su questi e altri algoritmi di risoluzione dei labirinti)
• MazeBlog: risolvere labirinti usando l'analisi delle immagini, su cb.uu.se (archiviato dall'url originale il 20 settembre 2015).
• Video: simulazione di risoluzione di labirinti, su youtube.com.
• Simon Ayrinhac, La corrente elettrica risolve i labirinti, su iopscience.iop.org.

Portale Informatica

Portale Matematica