Trouver un trésor plus rapidement avec des conseils angulaires

Résumé : Un touriste égaré souhaite retrouver son chemin vers la gare de train la plus proche. Heureusement pour lui, au cours de sa recherche, il rencontre de nombreuses personnes enclines à le renseigner. Toutefois, la plupart ne connaissent pas la direction exacte à suivre. N'ayant qu'une vague idée du chemin à prendre, lorsqu'elles sont interrogées, elles ré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 avons apportées à ces deux questions dans un article récemment publié [BDPP18]. Le problème abordé ici, plus connu dans la littérature sous l'appellation de chasse au trésor, n'avait encore jamais été étudié en présence de conseils angulaires.
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-02118362
Contributor : Yoann Dieudonné <>
Submitted on : Friday, May 3, 2019 - 8:15:00 AM
Last modification on : Wednesday, July 10, 2019 - 9:54:29 AM

File

bouchard_et_al.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02118362, version 1

Citation

Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc, Franck Petit. Trouver un trésor plus rapidement avec des conseils angulaires. ALGOTEL 2019 - 21èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2019, Saint Laurent de la Cabrerisse, France. ⟨hal-02118362⟩

Share

Metrics

Record views

73

Files downloads

608