Problème de la traversée du désert

La base contient une réserve de n (unités de carburant). La jeep a une capacité de 1 (unité de carburant). Se déplacer de x (unités de distance) coûte x unités de carburant, x étant un réel quelconque compris entre 0 et 1[6]. Les dépôts de carburants sont faits à des endroits arbitraires, et en quantité arbitraire. Chaque voyage amène la jeep à retourner à sa base dans la variante d'exploration du désert, mais le dernier voyage se termine réservoir vide le plus loin possible dans la variante de traversée du désert.

Une mise en équation rigoureuse passe par l'introduction d'un ensemble de suites décrivant les états de la jeep et des dépôts de carburants après le i-ème voyage (avec des règles de transition donnant, par exemple, le nouveau contenu de chaque dépôt), mais cela ne sera pas nécessaire pour décrire la solution.

Dans le problème du chameau et des bananes, le marchant a une réserve (à sa base) de n paquets de bananes. Le chameau peut transporter 1 paquet au maximum, et doit consommer un paquet chaque fois qu'il parcourt une unité de distance ; le marché est à m unités de distance. Les règles de dépôt et de collecte sont les mêmes que dans le problème de la jeep ; la question est de maximiser la quantité de bananes apportées au marché.

Dans le problème du groupe de voyageurs, les réserves à la base sont illimitées, il y a m unités de distance à traverser, chaque voyageur transporte une unité de nourriture au maximum, et consomme une unité de nourriture par unité de distance ; il est impossible de faire des réserves, mais les voyageurs peuvent échanger de la nourriture entre eux. Un voyageur doit effecteur la traversée, et tous les autres doivent retourner à la base. Le problème demande le nombre minimum de voyageurs nécessaire pour une distance donnée (ou parfois la distance maximum traversable par un groupe de taille donnée).

Dans le problème de la flottille de véhicules, les contraintes sont les mêmes que pour le problème du groupe de voyageurs, mais une seule voiture doit parvenir à destination, les autres pouvant être abandonnées en route lorsque leurs réservoirs sont vides.

Une solution au problème de l'exploration du désert (optimale, à l'ordre des voyages près) est la suivante[7] :

• La jeep fait ${\displaystyle n}$ voyages, partant de la base à chaque fois en ayant fait le plein (une unité de carburant).
• Au premier voyage, la jeep crée un dépôt à une distance ${\displaystyle {\frac {1}{2n}}}$, y laisse ${\displaystyle {\frac {n-1}{n}}}$ unités de carburant et revient à la base (arrivant réservoir vide).
• Au second voyage , la jeep refait le plein au premier dépôt, avance de ${\displaystyle {\frac {1}{2n-2}}}$ unités et laisse ${\displaystyle {\frac {n-2}{n-1}}}$ unités à un second dépôt, ce qui lui laisse juste assez de carburant pour revenir au premier dépôt, y prendre ${\displaystyle {\frac {1}{2n}}}$ unités et retourner à la base.
• La stratégie est la même à chaque voyage : avancer jusqu'au dernier dépôt établi, en refaisant le plein à chaque dépôt, construire un nouveau dépôt, et revenir en reprenant dans chaque dépôt juste assez de carburant pour atteindre le dépôt précédent. Plus précisément, au ${\displaystyle k}$-ème voyage, le nouveau dépôt est établi à une distance ${\displaystyle {\frac {1}{2n-2k+2}}}$ du précédent, et la jeep y laisse ${\displaystyle {\frac {n-k}{n-k+1}}}$unités de carburant.

On vérifie facilement qu'à son dernier voyage, la jeep avance en prenant à chaque fois la moitié de ce qui reste dans chaque dépôt, refaisant le plein, atteint le dernier dépôt (où il y a ${\displaystyle {\frac {1}{2}}}$ unités de carburant) avec ${\displaystyle {\frac {3}{4}}}$ unités, refait le plein, puis avance de 1/2 et revient enfin en vidant chaque dépôt, ce qui lui permet tout juste d'atteindre la base, en ayant parcouru lors de ce dernier voyage le double de ${\displaystyle \mathrm {explore} (n)}$, la distance explorée maximum :

${\displaystyle 2\times \mathrm {explore} (n)=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{k=1}^{n}{\frac {1}{k}}=H_{n}}$, ${\displaystyle H_{n}}$ étant le ${\displaystyle n}$-ème nombre harmonique (on a ${\displaystyle \ln n<H_{n}<1+\ln n}$) .

Cet encadrement montre qu'il est possible de parcourir lors du dernier voyage une distance arbitraire, mais que cela nécessite une réserve initiale de carburant et un nombre de dépôts grandissant exponentiellement avec la distance parcourue.

La variante de traversée du désert utilise une stratégie analogue, mais il n'y a plus besoin de laisser du carburant pour le retour lors du dernier voyage. Aussi, lors du ${\displaystyle k}$-ème voyage, le nouveau dépôt est établi à une distance ${\displaystyle {\frac {1}{2n-2k+1}}}$ du précédent, et la jeep y laisse ${\displaystyle {\frac {2n-2k-1}{2n-2k+1}}}$ unités de carburant ; au cours des ${\displaystyle {n-k-1}}$ voyages suivants, elle prend dans ce dépôt ${\displaystyle {\frac {1}{2n-2k+1}}}$ unités de carburant à l'aller, et la même quantité au retour.

Au début du dernier voyage, ${\displaystyle n-1}$ dépôts ont été établis ; le dernier contient ${\displaystyle {\frac {1}{3}}}$ unités, le précédent ${\displaystyle {\frac {1}{5}}}$, et ainsi de suite, le dépôt le plus proche contenant ${\displaystyle {\frac {1}{2n-1}}}$ ; partant avec 1 unité de la base et refaisant le plein à chaque dépôt, la jeep parcourra finalement une distance de ${\displaystyle \mathrm {traverse} (n)=1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}=\sum _{k=1}^{n}{\frac {1}{2k-1}}=H_{2n-1}-{\frac {1}{2}}H_{n-1}}$; on voit facilement que ${\displaystyle \mathrm {traverse} (n)>\mathrm {explore} (n)}$, et donc comme précédemment, on peut traverser un désert arbitrairement large, mais le nombre de dépôts croit exponentiellement avec la distance[1] - [7].

Dans le problème du chameau et des bananes, la solution précédente est optimale si ${\displaystyle \mathrm {traverse} (n)-1\leq m\leq \mathrm {traverse} (n)}$, et le nombre maximum de paquets de bananes qui peuvent être transportées est ${\displaystyle \mathrm {traverse} (n)-m}$, nombre compris entre 0 et 1. Cependant, si ${\displaystyle \mathrm {traverse} (n)-\mathrm {traverse} (2)\leq m\leq \mathrm {traverse} (n)-1}$, alors la (n−1)-ème réserve est inutile, car elle serait au delà du marché. Dans ce cas, le nombre maximum de paquets transportables est ${\displaystyle 1+3[\mathrm {cross} (n)-1-m]}$, qui est entre 1 et 2. De même, si ${\displaystyle \mathrm {traverse} (n)-\mathrm {traverse} (3)\leq m\leq \mathrm {traverse} (n)-\mathrm {traverse} (2)}$, les (n−2)-èmes et (n−1)-èmes réserves sont inutiles, et on peut tranporter ${\displaystyle 2+5[\mathrm {traverse} (n)-\mathrm {traverse} (2)-m]}$, qui est entre 2 et 3, et ainsi de suite.

Dans le problème du groupe de voyageurs, les ${\displaystyle n}$ voyageurs partent de la base avec ${\displaystyle n}$ rations. Après ${\displaystyle {\frac {1}{n+1}}}$ unité de distance, ils ont consommé ${\displaystyle {\frac {n}{n+1}}}$ rations ; l'un des voyageurs retourne à la base avec ${\displaystyle {\frac {1}{n+1}}}$ration, ce qui laisse au groupe ${\displaystyle n-1}$ rations. Le groupe avance encore de ${\displaystyle {\frac {1}{n+1}}}$ unité de distance, consommant ${\displaystyle {\frac {n-1}{n+1}}}$ rations ; un autre voyageur retourne alors à la base avec ${\displaystyle {\frac {2}{n+1}}}$ rations, ce qui laisse le groupe avec ${\displaystyle n-2}$ rations. Continuant cette stratégie, le groupe avance de ${\displaystyle {\frac {n-1}{n+1}}}$ et il ne reste qu'un voyageur, qui franchit une unité de distance supplémentaire ; au total, il aura pu atteindre un point situé à ${\displaystyle {\frac {n-1}{n+1}}+1=2-{\frac {2}{n+1}}}$ ; pour traverser ${\displaystyle m<2}$ unités de distance, il faudra donc au moins ${\displaystyle n={\frac {m+1}{2-m}}}$ voyageurs.

La limitation précédente vient de la nécessité de la survie des voyageurs. Dans le problème de la flottille de véhicules, la possibilité de les sacrifier pour le bien commun permet d'atteindre une distance aussi grande que l'on veut : après ${\displaystyle {\frac {1}{n}}}$ unité de distance, le groupe a consommé 1 unité de carburant ; on refait le plein de ${\displaystyle {n-1}}$ véhicules et on en abandonne un, puis le groupe parcourt ${\displaystyle {\frac {1}{n-1}}}$ unité, et ainsi de suite ; finalement, un seul véhicule arrive à destination en ayant parcouru ${\displaystyle 1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=H_{n}}$, une distance qui peut être aussi grande que l'on veut, mais au prix d'une flottille de taille exponentielle.

Dans la solution du problème de la jeep, la position des dépôts ne peut être améliorée, ni même modifiée, mais l'ordre des voyages pour les approvisionner est libre. Par exemple (dans le version d'exploration du désert), la jeep pourrait commencer par faire n − 1 aller-retours entre la base et le premier dépôt, y laissant ${\displaystyle {\frac {n-1}{n}}}$ unités de carburant à chaque fois, faire encore un voyage vers le premier dépôt, où elle trouvera disponible un total de ${\displaystyle n-1+{\frac {1}{2n}}}$, et recommencer en faisant à partir du premier dépôt n − 2 aller-retours vers le seconde dépôt (les ${\displaystyle {\frac {1}{2n}}}$ étant laissés pour l'ultime retour vers la base) , etc.