L'algoritmo del labirinto è un algoritmo di ricerca utilizzato per trovare il percorso più breve e conveniente fra due punti all'interno di un complesso. L'obiettivo quindi è trovare il percorso che richiede minor strada, evitando pareti e gli ostacoli presenti nel labirinto.
Il modo più classico per risolvere questo tipo di problema è utilizzare un algoritmo di ricerca. Nell'esempio illustrato useremo l'algoritmo di ricerca in profondità (DFS) per leggere il labirinto e trovare quindi il percorso più breve tra due punti.
Ricapitolando il nostro algoritmo funziona in questo modo: partendo dal punto di partenza del labirinto l'algoritmo legge il labirinto in profondità spostandosi da un punto all'altro finché non trova un punto "libero". Durante "l'esplorazione" l'algoritmo tiene traccia dei punti visitati, in modo da evitare di farli due volte. Quando viene trovato il punto di arrivo l'algoritmo torna indietro e registra il percorso.
Il codice Python illustrato utilizza una classe Labyrinth per scrivere il labirinto e una classe Navigator per leggerlo. La classe Labyrinth ha un metodo add_wall per aggiungere pareti/ostacoli al labirinto e un metodo is_valid_pos per verificare se posizioni sono valide (cioè non contengono pareti o ostacoli). La classe Navigator ha un metodo solve che utilizza l'algoritmo DFS per esplorare il labirinto e trovare il percorso più conveniente.
Il codice inizia scrivendo un labirinto di dimensioni 10x10 con un punto di partenza in alto a sinistra e un punto di destinazione in basso a destra. Poi vengono aggiunte alcune pareti al labirinto utilizzando il metodo add_wall della classe Labyrinth.
Poi viene creato un oggetto Navigator e viene usato il metodo solve per trovare il percorso più breve. Il metodo solve restituisce una lista di tuple, dove ogni tupla rappresenta una posizione del labirinto nel percorso più breve.
Si conclude con il percorso in output.
Codice:
import numpy as np
class Labyrinth:
def __init__(self, shape, start, end):
self.shape = shape
self.start = start
self.end = end
self.grid = np.zeros(shape, dtype=np.int8)
def add_wall(self, pos):
self.grid[pos[0], pos[1]] = 1
def is_valid_pos(self, pos):
return (pos[0] >= 0 and pos[0] < self.shape[0] and
pos[1] >= 0 and pos[1] < self.shape[1] and
self.grid[pos[0], pos[1]] == 0)
class Navigator:
def __init__(self, labyrinth):
self.labyrinth = labyrinth
def solve(self):
path = []
visited = set()
self._dfs(self.labyrinth.start, path, visited)
return path
def _dfs(self, pos, path, visited):
if pos == self.labyrinth.end:
path.append(pos)
return True
if pos in visited:
return False
visited.add(pos)
path.append(pos)
for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
next_pos = (pos[0] + direction[0], pos[1] + direction[1])
if self.labyrinth.is_valid_pos(next_pos):
if self._dfs(next_pos, path, visited):
return True
path.pop()
return False
# Esempio qui sotto:
shape = (10, 10)
start = (0, 0)
end = (9, 9)
labyrinth = Labyrinth(shape, start, end)
labyrinth.add_wall((2, 2))
labyrinth.add_wall((3, 2))
labyrinth.add_wall((4, 2))
labyrinth.add_wall((5, 2))
labyrinth.add_wall((5, 3))
labyrinth.add_wall((5, 4))
labyrinth.add_wall((4, 4))
labyrinth.add_wall((3, 4))
labyrinth.add_wall((2, 4))
navigator = Navigator(labyrinth)
path = navigator.solve()
print(path) # Output: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (5, 3), (5, 2), (4, 2), (3, 2), (2, 2), (2, 1), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 0), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8), (9, 9)]
Output:
Potete provarlo online qui!
