1. Trouver un trésor plus rapidement avec des conseils angulaires
- Author
-
Bouchard, Sébastien, Dieudonné, Yoann, Pelc, Andrzej, Petit, Franck, DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Département d'Informatique et d'Ingénierie (DII), and Université du Québec en Outaouais (UQO)
- Subjects
Mobile agent ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,[INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] ,Deterministic algorithm ,Treasure hunt ,Algorithme déterministe ,Agent mobile ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,Chasse au trésor - Abstract
International audience; Un touriste égaré souhaite retrouver son chemin vers la gare de train la plus proche. Heureusement pour lui, au coursde sa recherche, il rencontre de nombreuses personnes enclines à le renseigner. Toutefois, la plupart ne connaissentpas la direction exacte à suivre. N'ayant qu'une vague idée du chemin à prendre, lorsqu'elles sont interrogées, ellesrépondent en levant et en écartant simplement les bras pour indiquer un angle où la gare recherchée peut se trouver.Selon la précision du renseignement (c'est-à-dire de la largeur de l'angle), le touriste peut évidemment être amené àprendre des chemins l'écartant de la bonne direction.De tels renseignements sont-ils de nature à amener notre touriste à destination en suivant un algorithme déterministe ?Et dans l'affirmative, après avoir parcouru quelle distance ? Le présent papier présente les réponses que nous avonsapportées à ces deux questions dans un article récemment publié [BDPP18]. Le problème abordé ici, plus connu dansla littérature sous l'appellation de chasse au trésor, n'avait encore jamais été étudié en présence de conseils angulaires.
- Published
- 2019