Algorithme de Pledge

 

L'algorithme de Pledge

 

L'algorithme de Pledge, ou le moyen de sortir d'un labyrinthe quand on est plongé dans l'obscurité.Cet algorithme porte le nom de celui qui l’a découvert : un petit garçon de douze ans, qui s’appelait John Pledge.
La problématique :Vous vous baladiez dans un labyrinthe, en pleine journée et l'aventurier que vous êtes n'a pas vu la nuit tomber, il fait noir !Que faire pour vous sortir de ce labyrinthe et rejoindre votre maison ?

 

 

 

Les diverses solutions :L'aventurier qui est en vous se souvient de ses cours de programmations et effectivement plusieurs idées lui sont venues en tête !
Vous vous êtes rappelé de l'existence de l'algorithme de parcours en largeur ainsi que de l'algorithme de parcours en profondeur, vous pensez que vous allez vous en sortir !Petit hic ! Il fait nuit noire !Aucun moyen de vous repérer, de créer ou ne serait-ce que trouver un quelconque repère...
"Aucun problème" vous direz vous à vous-même, il y a toujours la célèbre astuce d'avancer jusqu'à rencontre un mur puis de le longer. A force de patience, vous vous en sortirez à coup sûr.

 

Haha, "heureux les simples d'esprit !".Pourquoi me demanderez-vous ? Cette idée semble être une alternative parfaite quand on ne voit pas.Je vous répondrais simplement que votre plan comporte est gros risque...J'ai nommé....

"L'Ilot"

Imaginez avancer et rencontrer un mur qui vous ferait tourner en rond ! C'est encore un peu flou pour vous ? Une image vos mieux que de grands discours.

 

Vous comprenez ? Vous ne pourrez pas utiliser cette méthode.
Mais alors, comment faire me direz-vous ?On pourrait au moins avancer jusqu'à ce fameux ilot, suivre le mur jusqu'à se retrouver dans notre position initiale et continuer jusqu'à trouver un nouveau mur à longer, ainsi l'ilot ne sera plus un souci !

 

Et encore une fois, je vous dirais que ce n'est pas non plus la bonne solution à adopter, voici la preuve en image.


"Bon, cela suffit ! Je veux pouvoir sortir de ce labyrinthe de malheur, il existe forcément une sortie !"

 

 

La résolution :Pour nous sortir de ce bourbier, il va falloir que vous utilisiez l'algorithme de Pledge.
Dans un premier temps, partons du principe que nous ne pouvons pas escalader un mur, faute de matériel, et que nous ne pouvions que tourner à droite et à gauche lorsqu'un mur se présente devant nous.
Nous allons établir deux choses importantes :⦁ Il nous faut créer un compteur qui sera initialisé à zéro⦁ Nous allons choisir une direction de référence (gauche ou droite)Ceci étant fait, nous pouvons passer à la suite.L'algorithme de Pledge repose sur deux étapes, ça tombe bien, vous souhaitez sortir de ce dédale le plus vite possible il me semble ?

Le principe :L'algorithme de Pledge nécessite que vous comptiez vos changements de direction en enlevant un point à votre compteur lorsque vous tournez du côté de votre direction de référence et en ajoutant un point à votre compteur quant à l'inverse vous prenez l'autre direction.Les étapes :Première étape : Avancez jusqu'à rencontre un mur, puis passez à la seconde étape.Deuxième étape : Longez le mur par votre direction de référence et ce, jusqu'à ce que le décompte la variation des points de votre compteur arrive à zéro.Une fois à zéro, vous pouvez repasser à la première étape.
C'est aussi simple que ça, plus loin, voici plusieurs exemples de résolution de labyrinthe effectués grâce à ce fameux algorithme.

S'il était effectivement impossible de sortir du labyrinthe en suivant cet algorithme, c'est que vous seriez piégé dans un labyrinthe où la porte serait fermée !

 

En d'autres termes, si sortie il y a, l'algorithme de Pledge la trouvera !

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *