John Pledge di Exeter aveva 12 anni , ancora studente  quando inventò l’algoritmo per uscire da un labirinto che porta il suo nome.

L’algoritmo di Pledge è così strutturato:

1 Scegli una direzione arbitraria, esempio Nord, e seguila

2 procedi verso Nord fino a quando non incontri un ostacolo

3 gira a sinistra fin a quando l’ostacolo non sarà alla tua destra

4 Gira intorno all’ostacolo, tenendolo a destra, fino a quando la rotazione totale non sarà pari a zero

5 ritorna al punto 2

Rispetto all’algoritmo visto nella lezione 5, si capisce subito che la chiave sta nel punto 4.

L’animale segue l’ostacolo non più quando la rotazione è un multiplo di 360 ma quando e solo quando la rotazione è zero.

L’algoritmo di Pledge permette all’animale di uscire dal labirinto senza cadere in trappole che la porteranno a ripetere lo stesso percorso

L’algoritmo di Pledge raccoglie informazioni locali aggiungendo giri a sinistra come numeri positivi e gira a destra come valori negativi a una variabile chiamata Total Turning. Grazie ad una informazione locale, riesce ad ottenere esiti su un fenomenglobale, quale l’uscita dal labirinto.

Ecco il codice:

https://scratch.mit.edu/projects/195315144/#editor

L’animale quindi avanza fino a quando non colpisce una barriera. Gira a sinistra, aggiungendo la misura dell’angolo della svolta alla rotazione totale e quindi esegue il resto dell’algoritmo fino a che la rotazione totale è uguale a zero gradi (non 360º) che indica che il robot ha navigato intorno alla barriera. L’algoritmo ripristina la rotazione totale a zero e il robot si sposta di nuovo in avanti finché non colpisce un’altra barriera. E così via.

     Una discussione completa dell’algoritmo di Pledge può essere trovata nel libro Turtle Geometry , di Harold Abelson e Andrea A. diSessa pubblicati dalla MIT Press nel 1980.

 

SI possono creare anche labirinti più complessi, sempre con lo stesso codice, ecco un esempio:

 

http://scratch.mit.edu/projects/2823071/

Ecco un video del robot lego Mindstorm che esce da un labirinto usanto l’algoritmo di Pledge

Bibliografia (se siete interessati alla struttura matematica)

http://download.kataweb.it/mediaweb/pdf/espresso/scienze/1984_188_M.pdf

Un video tutorial:

 

Una bella tesi su Pledge ed altri algoritmi:

https://pdfs.semanticscholar.org/0d97/707cad71c5e9df5fdc384901f92c2c89dc22.pdf

 

https://en.wikipedia.org/wiki/Maze_solving_algorithm

Vai alla barra degli strumenti