Un algorithme pour trouver Charlie le plus rapidement possible

Antoine Oury - 20.02.2015

Zone 51 - Insolite - Où est Charlie ? Waldo - algorithme découverte - Randy Olson Computer Science


La question a taraudé des milliers d'enfants depuis 1987, et quelques adultes : Où est Charlie ? Le personnage rayé de blanc et de rouge a fatigué pas mal d'yeux, mais un étudiant américain assure avoir trouvé un moyen infaillible pour débusquer la silhouette filiforme dans la foule, en moins de 10 secondes.

 

 

Le chemin optimal pour trouver Charlie, selon Randal Olson

 

 

Le week-end de Randal Olson, étudiant en sciences informatiques, s'annonçait ralenti par d'importantes chutes de neige : ni une, ni deux, il a décidé de se pencher sur un vieux projet. En novembre 2013, le journaliste Ben Blatt révélait dans Slate une méthode qu'il jugeait infaillible pour trouver Charlie, le plus rapidement possible. En gros, Blatt procédait par bande, en scrutant les doubles pages de gauche à droite, et en ignorant volontairement les bords et le milieu des dessins, où Charlie ne se trouve jamais.

 

Olson avait une tout autre théorie, et estimait que la solution de Slate était loin d'être optimale : il salue néanmoins la recension des 68 endroits où se trouvait Charlie dans les 7 livres signés par Martin Handford, réalisée par le journal. À partir de ces données, Olson a réalisé une estimation par noyau, permettant d'analyser une densité de probabilité. Celle de trouver Charlie à tel ou tel endroit de la page.

 

Il ne restait « plus qu'à » déterminer le moyen le plus simple et rapide de parcourir les 68 points où Charlie pouvait se trouver sur la double page : « Simple, non ? Pas du tout. Ces 68 points peuvent être reliés selon environ 2.48 x 1096 manières différentes, soit plus que le nombre d'atomes dans l'univers », souligne avec esprit Olson. 

 

L'étudiant aura donc préféré un algorithme génétique, qui recherche, à la place d'une solution exacte, une solution optimale. En suivant grossièrement le chemin proposé par l'algorithme, Olson assure que Charlie est trouvé en moins de 10 minutes. Mais l'étudiant souligne également que « [c]omme beaucoup de choses dans l'existence, le plaisir de trouver Charlie relève de la manière de faire, et pas de l'accomplissement ».

 

 




Commentaires

Pas de commentaires

Poster un commentaire

 

grin LOL cheese smile wink smirk rolleyes confused surprised big surprise tongue laugh tongue rolleye tongue wink raspberry blank stare long face ohh grrr gulp oh oh downer red face sick shut eye hmmm mad angry zipper kiss shock cool smile cool smirk cool grin cool hmm cool mad cool cheese vampire snake exclaim question

Vous répondez au commentaire de

Cliquez ici pour ne plus répondre à ce commentaire

* Laisser vide pour ne pas reçevoir de notification par email de nouveaux commentaires.