Capire l'algoritmo DFS con il film Shining
L’algoritmo DFS (Depth-First Search, ovvero ricerca in profondità) è una strategia intuitiva per esplorare aree di cui non conosciamo la struttura precisa — la cosiddetta topologia. In parole semplici, consiste nell’esplorare un grafo o un albero (cioè una rete di nodi collegati da archi) spingendosi quanto più possibile lontano dal punto di partenza prima di tornare indietro.
Se stiamo esplorando un albero (struttura senza cicli), oppure un grafo (che può contenere cicli), la DFS procede lungo un ramo finché trova qualcosa, oppure finché non può più andare avanti. Solo a quel punto torna indietro (backtracking) e prova un altro ramo. È come infilarsi in ogni corridoio fino in fondo, uno per uno.
Nel diagramma qui accanto è illustrato il comportamento dell’algoritmo: basta seguire l’ordine numerico per comprendere come avvenga la scansione profonda della struttura.
Ma cosa c’entra tutto questo con Shining, il capolavoro di Stanley Kubrick?
Lo scopriremo tra un attimo...
In termini algoritmici, la DFS segue uno schema molto semplice, che possiamo illustrare chiaramente nel caso di un albero (il caso del grafo è analogo, con qualche precauzione in più per evitare di visitare cicli).
Si parte da un nodo radice (nell'esempio, il nodo 1) e si esplorano i suoi nodi adiacenti — in questo caso, {2, 7, 8}. Per ciascuno di essi, si richiama ricorsivamente una funzione chiamata, di solito, visita.
Il cuore dell’approccio è proprio qui: la funzione visita chiama sé stessa su ciascun nodo figlio, spingendosi in profondità nella struttura fino a quando non ci sono più rami da esplorare. È un esempio classico di ricorsione, un concetto chiave in informatica che può inizialmente sembrare controintuitivo: una funzione che per risolvere un problema... si affida a una copia di sé stessa per risolverne una versione più semplice. Questo stile di ragionamento è fondamentale per comprendere algoritmi che esplorano strutture complesse, come alberi, grafi, labirinti… o magari sentieri innevati nel giardino dell’Overlook Hotel.
Quello che segue è il codice Python che permette di mettere in atto, mediante la funzione (def) di nome visita (con parametro nodo), quanto detto finora:
def visita(nodo):
for adiacente in nodo.adiacenti:
visita(adiacente)Molto semplice, generalizzabile e utile per scrivere tanti altri algoritmi.
Anche nella vita di ogni giorno, del resto, usiamo la DFS: immaginiamo di entrare in una grande casa, con tante stanze e corridoi, in cui non sappiamo dove andare. Un po’ come la villa in cui Jack Torrance decide di trasferirsi con la famiglia…
Di base, se non sai come è fatta la casa, poni l’obiettivo di farlo esplorando ciò che puoi vedere a partire dalla prima stanza: se vedi una porta, entri lì (ti sposti “in profondità”), se ne vedi un’altra la segui, e così via. Quando non ci sono più stanze da esplorare, torni indietro - al limite usando le briciole di Pollicino - e provi un’altra porta, ripetendo lo stesso comportamento.
È lo stesso criterio con cui, per arrivare al punto chiave, esploriamo un labirinto, del quale tipicamente non conosciamo la forma, non abbiamo algoritmi pre-determinati per uscirne e, soprattutto, anche avere una visione d’insieme - dall’alto, come Jack Nicholson in Shining.
La scena è suggestiva per varie ragioni: è plausibile che si tratti di una rappresentazione simbolica della mente del personaggio di Jack, ma al tempo stesso notiamo che il suo osservarla dall’alto non sarà di grande aiuto per orientarsi. La strategia più funzionale per uscire da un labirinto rimane quella utilizzata dal piccolo Daniel e dalla moglie Wendy: visitare il labirinto un po’ per volta, cercando di ricordare soprattutto dove siamo già stati - ed esplorando in profondità la struttura.
Ho creduto talmente tanto in questa idea che ho sviluppato, qualche settimana fa, un piccolo simulatore online per spiegare, mediante gamification, il funzionamento del DFS.