Rendez-vous au supermarché
Deux personnes se perdent dans les allées d’un supermarché. Que vaut-il mieux faire pour qu elles se retrouvent au plus vite ? S’arrêter et attendre, ou continuer à marcher?
La meilleure stratégie semble être d’aller à la sortie du magasin et d’attendre: l’autre personne devra nécessairement passer par là. Le temps d’attente maximal sera celui qui vous sépare de la fermeture du magasin.
La stratégie de l’immobilisation et de l’attente ne marche que si une personne seulement s’arrête. Si les deux s’arrêtent,
le temps d’attente maximal est soit infini (si vous vous laissez enfermer jour après jour) soit, de nouveau, égal au temps qui vous sépare de la fermeture.
En supposant qu’une des personnes s’arrête pendant que l’autre continue à marcher, le temps maximal est la durée nécessaire à l’exploration du magasin entier, durée qui dépend elle-même de la disposition du magasin. Si les allées sont toutes visibles depuis un même point, la recherche est grandement facilitée. Les prisons, d’ailleurs, et les forts militaires sont dessines selon ce principe. Afin de simplifier le travail, la personne immobile est priée de se mettre à l’intersection de deux allées.
Une autre stratégie serait une recherche au hasard, chaque personne s’éloignant de son point de départ d’une distance proportionnelle à la racine carrée du temps. L’aire balayée par chacun serait alors un cercle centré sur la position initiale. Comme les deux cercles doivent se chevaucher suffisamment pour que la rencontre ait lieu, le temps de recherche doit être au moins proportionnel au carré de la distance entre les centres des cercles. Si certaines allées sont bloquées, le problème se ramène à celui du mouvement sur une courbe fractale. La durée de recherche sera alors proportionnelle à la distance précédente élevée, non au carré, mais à un exposant fractionnaire (2,1 par exemple, ou 1.8).
Pour répondre à cette question, il faut d’abord savoir si les deux personnes se sont mises d’accord sur ce qu’il fallait faire en cas de séparation. S’il y a eu accord sur une stratégie de recherche (l’un attend, l’autre cherche, par exemple), le problème est la version asymétrique du problème du rendez- vous; sinon, c’en est la version symétrique.
J’ai présenté les solutions à ce problème, pour diverses configurations de lieux, dans le Journal de contrôle et d’optimisation de la Société de mathématiques industrielles cl appliquées (SIAM). Dans tous les cas où des solutions exactes ont été obtenues, les deux personnes marchaient aussi vite que possible, tout le temps. La stratégie d’immobilisation d’une des personnes n’est certainement pas optimale. Par exemple, un modèle simplifié dans lequel les deux personnes sont à la distance 1 l’une de l’autre, il faudrait un temps égal à ( 1 + 3)/2 = 2 pour que la rencontre ait lieu. Si tout le monde bouge, ce temps est réduit à 13/8, soit 1,61.
Le seul cas connu où la stratégie de l’attente est optimale est celui de deux personnes placées dans un supermarché circulaire. Si l’un attend, l’autre le trouvera nécessairement.
Tous ces résultats supposent que les personnes se trouvent quand elles se rencontrent ou lorsqu’elles sont à très faible distance l’une de l’autre, ce qui est le cas dans un supermarché aux heures d’affluence. Le cas d’un supermarché vide n’a, à ma connaissance, pas été envisagé.
Je vous conseille de marcher le long du côté du supermarché où se trouvent les caisses et de regarder dans toutes les allées. Si ça ne marche pas, repartez dans l’autre sens, en regardant à nouveau les allées et les caisses. Si ça ne marche toujours pas, essayez la queue au rayon boucherie. Faites un dernier passage le long des caisses, puis demandez qu’un appel radio soit fait dans le magasin.