La méthode pledge
La main gauche
Vous êtes dans un labyrinthe. Il fait nuit. Pour en sortir, d'abord avançons prudemment tout droit jusqu’à rencontrer un mur et nous longeons ce mur avec notre main gauche.
Mais si vous tombez sur un ilot ou un pilier, il y a peu de chance que vous réussissiez.
Afin de résoudre ce problème, nous avançons prudemment jusqu'au mur,
Puis, nous le longeons avec la main gauche, jusqu'à ce que nous soyons dans la même direction que celle du départ.
Nous avançons tout droit jusqu'au prochain mur, et nous le suivons avec la main gauche.
Mais dans le premier labyrinthe cette méthode ne fonctionne plus.
Alors comment résoudre ce problème ?
L 'algorithme de Pledge
John Pledge, un garçon de douze ans a eu cette idée, il ne suffit pas de marcher en ligne droite et de garder le mur à gauche, mais il faut aussi compter les changements de direction.
Nous supposons dans les exemples que tous les angles sont droits. Nous n' avons que deux possibilités tourner à droite ou gauche selon un angle de 90°.
Au départ le décompte est à 0. A chaque fois que la valeur est à 0, nous allons tout droit jusqu'au prochain mur.
Sinon, on compte les changements de direction en augmentant d'un point lorsque je tourne à gauche, et en diminuant d'un point lorsque je tourne à droite .
L 'algorithme
Compteur =0
1. aller tout droit juqu'au mur.
2. longer le mur par la gauche (ou la droite mais toujours du même côté), et compter les changements de direction (+ 1 à gauche, -1 à droite).
Lorsque le décompte des changements atteint 0, passer à l'instruction 1.
