Un peu de science pour trouver Charlie

Par défaut

Randal S. Olson est étudiant en informatique à l’université du Michigan. Il a, entre autres, été récompensé pour sa thèse sur l’automatisation de l’apprentissage de la marche pour les robots. Mais, ici, ce qui nous intéresse est un travail annexe mené sur Charlie, le personnage qui se cache dans les pages des albums « Où est Charlie? ». Après avoir lu l’article de Slate qui proposait une méthode de recherche approximative, Randal Olson a décidé d’optimiser la solution.

Dans la théorie de Slate, il y a 68 emplacements recensés où Charlie se trouve de manière préférentielle. Fort de cette distribution de points, Slate identifie deux bandes susceptibles de contenir Charlie le plus souvent (Waldo en anglais dans l’infographie ci-dessous).

131111_heresWaldo2

Mais Randal S.Olson voulait aller plus loin en établissant un algorithme susceptible d’améliorer encore la probabilité de trouver Charlie en suivant le meilleur chemin possible sur les pages des albums. Problème, les 68 points identifiés donnent un nombre de combinaisons très importants, qui mettraient même à mal les capacités de calculs des plus puissants supercalculateurs. Randal S. Oslon a donc décidé de développer une solution plus efficace.

Il a employé un algorithme génétique, c’est à dire, qu’au lieu de donnée une solution exacte, il donne la solution la plus proche possible et la plus efficace pour répondre au problème donné. Voici donc le chemin de recherche le plus efficace, selon le jeune chercheur :

waldo-ga-optimal-search-path

 

Dans un premier temps, Randal S. Olson a précisé ne pas avoir testé sa méthode car il n’avait pas conservé ses anciens albums. L’éditeur a entendu le message et lui a fait parvenir l’intégrale. Résultat : l’auteur de l’étude affirme mettre moins de 10 secondes par illustration.

J’ai également testé cette méthode. J’avoue que je prends plus de 10 secondes, mais je n’ai que bac +2. Toutefois, moi, j’ai trouvé Carmen Sandiego à 8 ans !

Cadeau bonus : une fausse bande annonce (en anglais) de l’adaptation cinéma de « Où est Charlie? »

Source : http://www.randalolson.com/2015/02/03/heres-waldo-computing-the-optimal-search-strategy-for-finding-waldo/


© https://whereonearthiswaldo.wordpress.com (Projet qui propose a qui veut d’imprimer un Charlie géant, pour être vue du ciel )

© slate.com

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s