ALGORITMI PER LABIRINTI

Ita Daedalus implet
Innumeras errore vias vixque ipse reverti
Ad limen potuit
(Ovidio, Metamorfosi, 8.166-68)
  • La regola della destra
  • Il metodo di Tremaux
  • Il metodo di Ore

    • La regola della destra

    Entra nel labirinto. Quando ti trovi a un nodo prendi il ramo più a destra. Se arrivi a un vicolo cieco, ritorna sui tuoi passi fino all'ultimo nodo e prendi il ramo più a destra tra quelli ancora inesplorati. (Nota teminologica: nella geografia dei labiriniti una biforcazione è detta 'nodo', un segmento tra due nodi e detto 'ramo').

    Il modo migliore per visualizzare questo argoritmo è toccare con la mano destra il muro alla propria destra per tutto il labirinto, senza saltare mai un ramo situato alla propria destra.

    Naturalmente la "regola della sinitra" funziona altrettanto bene. È solo necessario essere coerenti una volta entrati nel labirinto.



    Il metodo di Tremaux

    Entra nel labirinto. Dapprima vai dove ti pare, contressegando il sentiero con un filo, o con sassolini, o molliche di pane, o con qualsasi cosa tu abbia a disposizione. Continua cosi' finche' arrivi:


    Se arrivi a un vicolo cieco, ritorna al nodo precedente, assicurandoti di contrassegnare il percorso anche a ritroso: in tal modo, se entri ed esci da un vicolo cieco, questo avrà due piste di briciole di pane. Ciò ti permetterà di evitarlo in futuro--nell'algoritmo di Tremaux non si esplora mai un ramo piu' di due volte.
    Se arrivi a un nodo già attraversato, fai così:

    1. se sei arrivato da un ramo fino ad allora inesplorato (una sola pista di briciole di pane dietro di te) ripercorri quello stesso ramo fino al nodo precedente, altrimenti
    2. se c'è un ramo ancora inesplorato a partire dal nodo, prendi questa dirizione, altrimenti:
    3. prendi qualsiasi ramo che sia stato percorso una sola volta.
    Queste regole esauriscono l'algoritmo di Tremaux. Seguendole scrupolosamente farai un giro completo del labirinto, attraversando ogni ramo due volte, in ciascuna direzione. Ovviamente, puoi anche fermarti quando raggiungi la meta, se non è necessario percorrere l'intero labirinto.



    Il metodo di Ore

    Entra nel labirinto. Se non sei gia' a un nodo, raggiungi quello piu' vicino. Se non sai quale direzione conduca a quello piu' vicino, vai a caso fino a incontrare un nodo. Poi contrassegna in qualche maniera questo nodo: sara' la tua casa base.

    Partendo dal nodo base, esplora ogni ramo che si diparte da questo. Metti un contrassegno --ad esempio un ciottolo--all'entrata ddi ciascun ramo quando cominci a percorrelro. Esplora ciascun ramo solo fino al nodo successivo. Poi metti un ciottolo all'estremita' lontana del ramo e ritorna sui tuoi passi fino alla casa base.

    Identifica i vicoli ciechi (ad es. con un ciottolo rosso, o chiudendoli con uno spago). Una volta contrassegnato in questo modo, un ramo potrà essere ignorato in futuro. Se un ramo gira su se stesso e ritorna al nodo originario, contrassegnalo come un vicolo cieco: è altrettanto privo di utilità.

    A te interessa individuare quei rami che conducono a nodi con rami nuovi. Alla fine dell'esplorazione preliminare ciascun percorso potenziale verso la meta a un ciottolo a ciascuna estremità, e tu ti trovi di nuovo al nodo base.

    Adesso esplora fino a una profondità di due nodi. Cammina lungo ciascun ramo che non sia un vicolo cieco fino al nuovo nodo, ed esplora allo stesso modo ciascun ramo che si diparte da questo. Aggiungi un ciottolo a ciascuna estremità dei rami primari, cosicché adesso avranno due ciottoli su ciascuna estremità, e metti un ciottolo su ciascuna estremità dei nuovi rami secondari. Cio' ti consentira' di ritrovare la strada fino al nodo base: il ramo che conduce a quest'ultimo ha un ciottolo in piu' rispetto agli altri. Come in precedenza, contrassegna le entrate dei vicoli cieco e dei percorsi circolari. Se un ramo conduce a un nodo già esplorato (con un almeno un ciottolo segnaletico) contrassegna anche questo sentiero a entrambe le estremità. Alla fine sarai tornato sui tuoi passi e ti ritroverai di nuovo al nodo base.

    Nella terza fase di esplorazione, spingiti fino a una distanza di tre nodi dal nodo base, aggiungendo un ciottolo a ciascuna estremita' di ogni ramo esplorato.

    Prosegui l'esplorazione sempre piu' in profondita', fino a raggiungere la meta. L'algoritmo di Ore ti permetterà di individuare la via più breve verso la meta (misurata in rami, non in linea d'aria). Ovviamente l'andamento dell'esplorazione non seguirà questa via più breve, ma se, ad es., la via più breve attraversa cinque nodi allora la troverai nella quinta fase dell'esplorazione, e saprai che quella e' la via più breve.

    ----

    Da W. Poundstone, I Labirinti della Ragione (Pan Libri, 1991)

    Hosted by www.Geocities.ws

    1