Un randonneur est perdu en forêt. Il connait la forme de la forêt et ses dimensions. Il est capable de marcher en ligne droite, de suivre un arc de cercle, de mesurer la distance parcourue et de tourner selon l’angle de son choix. Tant qu’il n’est pas sur la frontière de la forêt, il ne peut pas savoir s’il est près de sortir de la forêt. Quelle est la meilleure stratégie pour être certain de sortir de la forêt tout en minimisant la distance parcourue dans le pire des cas ?

Richard Bellman
1920-1984

Ce problème a été proposé pour la première fois par Richard Bellman en 1955. On remarque rapidement que les hypothèses ne sont pas très réalistes : dans une vraie forêt, il est difficile de marcher exactement en ligne droite et, près de la frontière, on peut percevoir la sortie. Bellman a néanmoins choisi ce cadre simplifié pour présenter plus aisément un problème mathématique d’optimisation : déterminer un chemin garantissant la sortie d’une région géométrique, tout en minimisant la distance maximale à parcourir. Présenter cela sous la forme d’un randonneur perdu rend les stratégies plus accessibles.

Il y a plusieurs manières de définir la meilleure stratégie pour sortir de la forêt, on aurait pu définir que la meilleure stratégie est celle qui permet de sortir de la forêt avec une distance moyenne minimale, mais ici, on définit la meilleure stratégie par celle dont la distance maximale soit minimale.

Pour ce problème, on va utiliser le terme diamètre pour représenter la distance maximale entre deux points de la forêt. Si la forêt a une forme circulaire, cela correspond à la définition usuelle du diamètre d’un cercle. Voici trois exemples de forêt avec un diamètre de 1.

Le chemin qu’on recherche pour sortir de la forêt est appelé chemin d’évasion.

Grosse forêt : la ligne droite

On pourrait croire que la meilleure stratégie consiste à marcher en ligne droite. Ainsi, la distance maximale serait le diamètre de la forêt. Le pire cas est donc quand le randonneur part d’un point extrême et il se dirige en ligne droite vers le point le plus éloigné.

Par définition du diamètre, peu importe le point où est le randonneur au départ, sa distance (en ligne droite) avec tous les points à la frontière est plus petite que le diamètre.

C’est effectivement la stratégie optimale pour les grosses forêts. Une forêt est dite grosse, si elle peut contenir un losange formé de deux triangles équilatéraux et tel que sa grande diagonale est le diamètre de la forêt. Un tel losange a deux angles de 60° et deux angles de 120°. Voici des exemples de grosses forêts avec les losanges.

Une forêt qui n’est pas grosse, c’est-à- dire qu’elle ne peut pas contenir un losange dont la grande diagonale est égale au diamètre de la forêt et dont les angles soient 60° et 120°, sera appelée une forêt étroite. Voici des exemples de forêts étroites avec les losanges.

En 1973, Gerriets et Poole, ont démontré que ce losange avec des angles de 60° et de 120° peut contenir tous les chemins de longueur égale à sa grande diagonale. Donc pour tout chemin d’une longueur plus petite que la grande diagonale du losange, il existe une manière de le contenir complètement dans le losange, donc il ne peut être une trajectoire d’évasion.

Voici des exemples de chemins de longueur égale à la grande diagonale inclus dans le losange.

Cela veut dire que la ligne droite est la meilleure trajectoire d’évasion pour une forêt en forme de ce losange et pour toutes les grosses forêts qui contiennent ce losange. Dans ces cas-ci, le pire cas est de marcher tout le diamètre de la forêt.

On peut démontrer que toutes les forêts en forme de polygone régulier (à l’exception du triangle) sont des grosses forêts, donc le chemin d’évasion pour toutes ces formes est une ligne droite.

Maintenant, on va s’intéresser à deux cas de forêts étroites.

Forêt étroite : rectangle

Cette fois-ci, on considère une forêt très longue et de largeur 1. Marcher en ligne droite n’est pas une bonne stratégie : si le randonneur part presque parallèlement aux grands côtés, il risque de marcher longtemps avant de sortir. Il faut donc envisager un chemin comportant des virages.

Pour vérifier qu’un chemin permettra toujours au randonneur de sortir de la forêt rectangulaire, il faut s’assurer qu’il existe toujours deux points sur le chemin entre lesquels la distance horizontale est au moins 1, et ce quelle que soit l’orientation du chemin dans la forêt.

La distance horizontale entre deux points est la différence en valeur absolue des coordonnées en \(x\) des deux points en considérant l’axe des \(x\) parallèles aux côtés de longueur 1 du rectangle.

\[d_{horizontale}(A(x_A, y_B), B(x_B, y_B) = |x_A – x_B|\]

Si cette distance horizontale atteint au moins 1, alors quelle que soit la position du randonneur, un de ces points sera à l’extérieur de la forêt.

Stratégie 1 :

Le randonneur marche sur une distance \(\sqrt{2},\) puis effectue un virage de 90°. Dans le pire cas, il devra marcher encore \(\sqrt{2}\) avant de sortir.

En effet, ces deux segments forment deux côtés adjacents d’un triangle rectangle isocèle dont la plus petite hauteur est 1 (largeur de la forêt).

Quelque soit l’orientation du randonneur, on peut toujours trouver deux points de son chemin dont la distance horizontale est comprise entre 1 et 2. Un cas extrême est lorsque l’hypoténuse est parallèle aux côtés de longueur 1 pour une distance horizontale de 2 et l’autre cas extrême est lorsque l’hypoténuse est perpendiculaire aux côtés de longueur 1 pour une distance de 1.

Ainsi quelle que soit l’orientation initiale du randonneur, l’un des sommets du triangle se trouvera nécessairement à l’extérieur de la forêt.

Avec cette stratégie, le randonneur peut donc s’assurer de sortir après avoir par- couru, dans le pire cas une distance totale de \(2 \sqrt{2} \approx 2,828.\)

Cette approche simple fournit une première borne supérieure, soit \(2 \sqrt{2},\) pour la distance d’évasion.
Mais on peut encore améliorer la stratégie en remplaçant le virage droit par un angle de 60°, comme on le verra dans la stratégie suivante.

Stratégie 2 :

Le randonneur parcourt deux côtés d’un triangle équilatéral dont la hauteur est 1, c’est-à-dire la largeur de la forêt. Ce triangle a donc des côtés de longueur de

\[ \displaystyle \frac{2\sqrt{3}}{3}.\]

Ainsi, si le randonneur marche le long de deux côtés consécutifs, la distance totale parcourue dans le pire cas est

\[2 \times \displaystyle \frac{2\sqrt{3}}{3}= \frac{4\sqrt{3}}{3} \approx 2,309\]

Dans cette configuration, on peut toujours trouver deux points sur la trajectoire, en fait deux sommets du triangle, dont la distance horizontale (projetée sur la largeur de la forêt) est comprise entre

\[ 1 \text{ et }\displaystyle \frac{2\sqrt{3}}{3}.\]

Autrement dit, quelle que soit l’orientation initiale du randonneur, au moins un sommet du triangle se retrouvera à l’extérieur de la forêt.

Ce trajet constitue bien un chemin d’évasion, plus court que celui de la stratégie 1.

Viktor Zalgaller
1920-2020

Stratégie 3 :

En 1961, Viktor Zalgaller propose un chemin plus court d’une longueur d’environ 2,2783 formé de quatre segments rectilignes et de deux arcs de cercle. L’amélioration par rapport au chemin précédent est de l’ordre de 2 %. (La construction détaillée et la démonstration qu’il s’agit bien d’un chemin d’évasion se trouvent dans l’encadré Chemin de Zalgaller.) Cette solution est meilleure que la ligne droite, tant que le diamètre de la forêt rectangulaire est supérieur à la longueur du chemin de Zalgaller.

Forêt étroite : le triangle équilatéral

Abram Besicovitch
1891-1970

Soit la forêt en forme d’un triangle équilatéral de côté 1. Son diamètre est 1 et il ne contient pas le losange dont la grande diagonale correspond au diamètre, c’est une forêt étroite. La ligne droite de longueur 1 permet de sortir de la forêt, mais il y a mieux.

En 1965, Abraham Besicovitch trouve une meilleure stratégie que la ligne droite pour le cas de la forêt en triangle équilatéral. Un chemin en zigzag de trois segments permet au randonneur de sortir dans le pire cas après une distance d’environ 0,982. Ce chemin est composé de 3 segments de longueur \(\sqrt{3/28}\) et si on considère deux côtés consécutifs comme les côtés d’un triangle isocèle, la valeur des angles aigus est

\[ \alpha = \arcsin \displaystyle \left ( \frac{1}{\sqrt{28}} \right ) \approx 10,893°.\]

Et maintenant ?

Zhipeng Deng

Ce problème du randonneur perdu dans la forêt est toujours étudié par les chercheurs. En 2025, Zhipeng Deng propose une nouvelle approche, à la place de déplacer le randonneur dans la forêt, il fait tourner et translater la forêt autour du randonneur.¹

Cette reformulation permet de calculer des stratégies optimales pour des forêts de formes complexes, voire en trois dimensions, à l’aide d’algorithmes numériques.

Bref, ce problème ludique a donné naissance à une véritable branche de la géométrie algorithmique. Il a inspiré des recherches pendant plus de soixante ans et demeure encore aujourd’hui un sujet actif d’étude. Au-delà du contexte d’un randonneur perdu, il s’agit en fait d’un problème fondamental : comment garantir la sortie d’un ensemble sans information sur sa position exacte ?

Les stratégies optimales trouvées pour les triangles et les rectangles ont des applications en robotique, en navigation autonome, en traitement d’images, et même dans certaines méthodes d’optimisation numérique. Ce qui semblait au départ un jeu d’esprit s’avère être une porte d’entrée vers des stratégies profondes et modernes.

PDF