L'algorithme de Pledge

Suivre un mur à main gauche ou avancer tout droit semblent des stratégies logiques pour s'échapper d'un labyrinthe, mais elles échouent dans des configurations contenant des piliers isolés ou des obstacles internes. L'algorithme de Pledge résout ce problème en combinant deux actions : avancer tout droit jusqu'à un mur, puis le longer en comptant les changements de direction (on ajoute 1 pour chaque virage à gauche, on soustrait 1 pour chaque virage à droite). Dès que le compteur revient à zéro, on reprend une trajectoire rectiligne.

Cet algorithme porte le nom de John Pledge, un enfant de douze ans qui l'a découvert. Une preuve rigoureuse par l'absurde montre qu'il fonctionne dans tous les cas : si une boucle infinie était possible, elle contradirerait le comportement du compteur. L'article présente des exemples visuels et des animations HTML5 permettant de tester l'algorithme dans différents labyrinthes, y compris des configurations dessinables par l'utilisateur.