Algoritme de resolució de laberints

S'anomena algoritmes de resolució de laberints, als diferents mètodes automatitzats per resoldre laberints. El ratolí aleatori, seguidor de parets, Pledge, i Trémaux són els algoritmes dissenyats per ser utilitzats dins del laberint per un viatger sense coneixement previ del laberint, mentre que els algoritmes de l'ompliment de culs de sacs i del cami més curt estan dissenyats per ser utilitzats per una persona o ordinador que pot veure tot el laberint a la vegada.

Els laberints sense illes són coneguts com "senzillament connectat", o laberints "perfectes", i són equivalents a un arbre en la teoria de grafs. Per aquest motiu molts algoritmes de resolució de laberints estan estretament relacionats amb la teoria de grafs. Intuïtivament, si s'estiressin els camins d'un laberint de la manera apropiada el resultat podria assemblar-se a un arbre.^[1]

Aquest és un mètode trivial que pot ser implementat per un robot poc intel·ligent o fins i tot un ratolí. És senzillament avançar seguint el passatge actual fins a arribar a un encreuament, i llavors fer una decisió aleatòria sobre quina direcció seguir. Tot i que aquest mètode sempre acaba trobant la solució correcta, és un algoritme que pot ser extremadament lent.

El millor métode conegut per resoldre laberints és el seguidor de paret, també conegut com a regla de la mà dreta o de la mà esquerra. Si el laberint està senzillament connectat, és a dir, totes les seves parets estan connectades entre elles o a la paret exterior, llavors mantenir una mà en contacte amb una paret del laberint garanteix no perdre's i arribar a una sortida diferent, si aquesta existeix; sino l'algoritme retornarà a l'entrada després d'haver passat per tots els passadissos connectats a aquesta secció de parets al meny un cop.