Regola della destra/sinistra
La regola della destra e l'equivalente regola della sinistra sono due algoritmi che formalizzano il modo per uscire da un labirinto.
Descrizione dell'algoritmo[modifica | modifica wikitesto]
Il procedimento consiste nell'appoggiare la mano destra (o la sinistra) alla parete destra del labirinto (o, rispettivamente, alla parete sinistra) all'entrata del labirinto, e scegliere l'unico percorso che permetta di non staccare mai la mano dalla parete scelta, fino a raggiungere una delle eventuali altre uscite, o il punto di partenza.
Nel caso particolare di una sola uscita, l'algoritmo conduce a un vicolo cieco, dal quale si ritorna al punto di partenza semplicemente continuando a seguire la parete prescelta.
Applicabilità dell'algoritmo[modifica | modifica wikitesto]
La regola della destra e la regola della sinistra sono algoritmi equivalenti e conducono sempre a un'uscita, nell'ipotesi che il percorso che compone il labirinto sia semplicemente connesso; nel caso che il labirinto sia invece molteplicemente connesso, questi algoritmi funzionano con certezza solo se applicati partendo da una delle entrate del labirinto, e portano a un'altra uscita oppure alla stessa.
Uno “spazio semplicemente connesso” è uno spazio topologico nel quale per ogni punto si può definire una curva chiusa passante per il punto (lo si può immaginare come un "cappio"), ed è possibile deformare con continuità la curva ("stringere il cappio") all'interno dello spazio, fino a renderla il punto stesso. È possibile dimostrare che ogni spazio semplicemente connesso può essere deformato con continuità fino a diventare un cerchio: il labirinto è quindi topologicamente equivalente a una stanza circolare con una o più porte. È quindi evidente che seguendo la parete interna della stanza si giungerà inevitabilmente a una porta.
Questi algoritmi non possono essere applicati a labirinti tridimensionali.
Voci correlate[modifica | modifica wikitesto]
Collegamenti esterni[modifica | modifica wikitesto]
Maze Transformed, su YouTube.
