Algorithme de Pledge

L'algorithme de Pledge est un algorithme de résolution de labyrinthe. Cet algorithme est considéré comme l'un des plus efficaces pour sortir d'un labyrinthe avec une vue locale même dans l'obscurité^[1]. Cet algorithme est une alternative à la méthode de la main, méthode qui ne fonctionne pas dans le cas des labyrinthe à îlots. Le principe de base, est de longer les murs, tout en évitant de rester coincé sur un même îlot. Pour cela, l'algorithme nous permet de savoir le moment où il faut lâcher le mur^[2].

L'algorithme de Pledge a été découvert par John Pledge, un Britannique de 12 ans^[3]. Il existe très peu d'information à ce jour sur sa vie où même sur la date exacte à laquelle il aurait trouvé cet algorithme^[4].

Pour comprendre l'algorithme de Pledge il faut supposer que tous les angles du labyrinthe sont droits. Nous ne pouvons donc nous déplacer qu'à gauche ou à droite. On imagine donc un décompte qui commence à zéro. On commence en avançant tout droit jusqu'à tomber sur un mur. Puis on longe le mur par la droite (ou par la gauche, le principal est de toujours prendre le même côté). À chaque fois qu'on tourne à droite, on ajoute 1 au décompte et à chaque fois qu'on tourne à gauche, on enlève 1 au décompte. Lorsque le décompte revient à zéro, on arrête de longer le mur et on avance tout droit jusqu'à ce qu'on arrive face à un mur. puis on recommence (on longe le mur par la droite, ou gauche, et on modifie le décompte à chaque angle). Il faut répéter ces étapes jusqu'à avoir trouvé la sortie du labyrinthe^[3]. Avec cette méthode, il est donc possible de sortir de n'importe quel labyrinthe (où que l'on commence et même s'il y a des ilots) sauf dans le cas où la sortie est une trappe dans le plafond plutôt qu'une porte au bout d'un couloir^[5].

• Résolution de labyrinthe

• sur Interstices.info

• Portail de l’informatique