L'explorateur - Détails (1) Dépôts

L'explorateur effectue des aller-retour dans le désert pour placer des dépôts de nourriture et finallement atteindre sa destination.
Le même genre de problèmes avec juste d'autres mots (bananes, éléphant, camion etc...).
Soit a l'autonomie en jours de l'explorateur, D la distance à parcourir (en jours).
Q la quantité totale de nourriture emportée au départ (en jours) S la quantité totale restante à l'arrivée
On peut se poser diverses questions reliant ces valeurs, et des buts différents :

Stock initial Q minimum pour atteindre la destination D ? Durée totale du voyage ?
Même question pour livrer une quantité donnée S à l'arrivée
Distance maximum atteinte avec un stock Q au départ ?
Quantité maximum S livrée à distance D avec un stock Q au départ ?
Mêmes questions si les étapes sont d'un nombre entier de jours

Livraison

Il s'agit donc de livrer la quantité S à la distance D, ou simplement d'atteindre D avec S = 0.
Nous allons donner déja un script général pour cette question, les explications ensuite.

Raisonnons à partir de la fin du voyage.
Si S ≤ a, il part simplement du dernier dépôt avec l'autonomie a et atteint sa destination avec un reste S₀ = S = a - x₀.
Cette dernière étape sera donc de distance x₀ = a - S, partant du dernier dépôt qui était S₁ = a.
Si S > a il faut effectuer déjà plusieurs voyages et il est ramené au cas général :

De façon générale en numérotant les étapes à partir de la fin, si x_i est la distance de l'étape i, à l'issue de cette étape on veut constituer un stock S_i-1 pour l'étape suivante i-1. (S₀ = S).
Au départ de cette étape i on a le stock S_i et le bilan, en effectuant u_i allers et u_i - 1 retours, est S_i = S_i-1 + (2u_i - 1)x_i [1]
Bien entendu, on a l'encadrement (u_i - 1)a < S_i ≤ u_ia :
Inutile d'amasser plus qu'on ne pourra en emporter, et inutile de faire u_i allers alors que u_i - 1 suffiraient.
Soit (u_ia - S_i-1) - a < (2u_i - 1)x_i ≤ u_ia - S_i-1
Il faut aussi remarquer que si x_i ≥ a/2, on ne peut rien laisser en dépôt, a - 2x_i est donc > 0.
Bien entendu ce cas x_i ≥ a/2 est tout de même possible, pour la dernière étape, avec u₁ = 1 (aller simple) et S₀ ≤ a, x₁ = a - S₀.
Le cas général (a - 2x_i > 0) permet de résoudre en u, qui doit être un nombre entier : (S_i-1 - x_i)/(a - 2x_i-1) ≤ u_i < (S_i-1 - x_i)/(a - 2x_i-1) + a/(a - 2x_i-1)
Comme a/(a - 2x_i) > 1 pour 0 < x_i < a/2, il y a toujours au moins une valeur entière entre ces bornes.
On a bien entendu intérêt à choisir la plus petite valeur pour u_i :
u_i ≥ (S_i-1 - x_i)/(a - 2x_i-1) > S_i-1/a et donc u_i sera le plus petit entier > S_i-1/a.
Maintenant si x_i ≥ 1 (étapes entières), cette borne est remontée d'autant et u_i ≥ (S_i-1 - 1)/(a - 2)

On en déduit alors x_i comme la plus grande valeur (éventuellement entière) ≤ (u_ia - S_i-1)/(2u_i - 1).
Ce sera tout simplement cette valeur (u_ia - S_i-1)/(2u_i - 1) si pas de contrainte sur x_i, le plus grand entier ≤ si x_i est entier.

Cette valeur reportée dans l'équation [1] donne alors S_i et de proche en proche les étapes successives en partant de la fin.
Enfin la première étape est éventuellement raccourcie, car inutile de dépasser le point de départ !

Etapes entières : u_i ≥ (S_i-1 - 1)/(a - 2)
sinon u_i > S_i-1/a
x_i ≤ (u_ia - S_i-1)/(2u_i - 1), entier ou non
S_i = S_i-1 + (2u_i - 1)x_i

Le cas le plus simple est S = 0 (juste aller à distance D), et des étapes de durées quelconques.
On a alors simplement :
A une étape donnée, il part d'un dépôt contenant na, fait 2n-1 trajets x_n et un bilan de :
na-(2n-1)x_n = (n-1)a soit x_n = a/(2n-1). La distance totale est :

D = a(1 + 1/3 + 1/5 + 1/7 +...+ 1/(2N-1))

Cette série divergente permet d'atteindre une distance quelconque.
La durée totale est a + 3a/3 + 5a/5 + ... = Na, N (et donc Na) croît exponentiellement avec D/a.
et on est bien entendu limité par la quantité totale de nourriture présente sur Terre !

Avec D = 1.5 a, on obtient 1 + 1/3 + 1/5 = 1.5333 > D
La première étape est alors raccourcie à D - a(1 + 1/3) = a/6 = 3.33 jours de distance. (au lieu de a/5 = 4)
Il fera à cette distance un dépôt de 2a pour l'étape suivante (2 allers).
Il effectue la première étape en 3 allers et 2 retours et il consomme donc 5a/6
La quantité totale de nourriture à prévoir au départ est ainsi de 2a + 5a/6 = 17a/6 = 56.66 jours
Il peut répartir cette quantité à sa convenance entre les 3 voyages aller.
Et cette quantité étant intégralement consommée, c'est la durée totale de son voyage.

On peut se poser la question des quantités infimes que l'on obtient ainsi.
Avec D = 80 = 4a, il faut 419 étapes. La première étape est de 0.01 jours, qu'il faut effectuer 837 fois, pour déposer un stock de 8360×20 à la distance de 0.01 jours du départ. Quelle est la pertinence d'une telle procédure ?? (déplacer le stock, supposé ponctuel, de quelques dizaines de cm ??)
On peut ainsi imposer que la plus petite étape soit de 1 jour, et même que chaque étape soit d'un nombre entier de jours.
Si on accepte des étapes d'une demi- journée, d'une heure etc... il suffit de changer d'unité pour avoir la contrainte "étape entière".

Dans les mêmes conditions (juste atteindre la distance D), notre explorateur effectuera alors :
1ère étape de 4 jours, 3 allers et 2 retours partant avec Q = 58 pour effectuer un dépot de 2a = 38
2ème étape de 6 jours, 2 allers et un retour, pour effectuer un dépôt de 20 jours
(il a consommé en 3 trajets de 6 jours 18 jours de nourriture seulement)
Dernière étape de 20 jours, aller simple consommant ces 20 jours.

Lorsque D est trop loin (≥ 6a), le programme estime le nombre d'étapes par la formule

1 + 1/2 + 1/3 +...+ 1/N ≈ ln(N) + γ + 1/(2N)
Avec γ la constante d'Euler ≈ 0.57721566490153286...

et bien entendu, puisqu'on se limite ici à la seule somme des inverses des nombres impairs :
1 + 1/3 +... + 1/(2N+1) = 1 + 1/2 + 1/3 + ... + 1/(2N) + 1/(2N+1) - 1/2 (1 + 1/2 + 1/3 + .. + 1/N)

1 + 1/3 +...+ 1/(2N+1) ≈ ln(2N+1) - ln(N)/2 + γ/2 + 1/(4N+2) - 1/(4N)

En première approximation 1 + 1/3 +...+ 1/(2N+1) ≈ ln(2√N) + γ/2
Cette valeur étant alors reportée dans l'équation du dessus pour obtenir une meilleure approximation de ln((2N+1)/√N) et donc de N.

Si les étapes sont d'un nombre entier de jours, le nombre d'étapes est borné par D, et cette limitation n'a pas lieu, (mais la durée du voyage est tout aussi irréaliste).

Stock limité

Il s'agit ici d'utiliser "au mieux" le stock initial Q. Soit pour aller le plus loin possible, soit pour livrer la plus grande quantité S à la distance D.

La première étape consiste donc à partir avec des aller-retours à chargement plein (= a)
on fera alors Q/a allers (et un retour de moins) pour constituer le premier dépôt
Puis itérativement à partir de ce premier dépôt jusqu'à atteindre la distance D, ou l'inanition...
Le calcul est ici plus simple puisqu'il se fait "en avant" (dans le sens de la marche) et non plus en partant de la dernière étape.
Nous allons ainsi numéroter les étapes dans le sens de la marche.
La suite est triviale, de proche en proche.

Le problème devient plus intéressant si Q/a n'est pas un nombre entier... que faire du reste de la division de Q par a ?
C'est à dire Q = na + r, 0 ≤ r < a
Il y a deux stratégies possibles pour effectuer un dépôt de (n-1)a pour les étapes suivantes.
Soit on effectue n+1 allers et n retours pour effectuer un premier dépôt de na, puis à partir de ce dépôt les n allers et n-1 retours
distance du dépôt de (n-1)a : r/(2n+1) + a/(2n-1) (ceci montre d'ailleurs qu'il est toujours rentable d'utiliser le reste)
Soit on effectue les n+1 allers et n retours pour effectuer directement le dépôt de (n-1)a. à la distance (a+r)/(2n+1) = r/(2n+1) + a/(2n+1)
Comme il est évident que a/(2n-1) > a/(2n+1), la première stratégie est meilleure

S₀ = Q = an + r, 0 < r < a
u₀ = n+1, x₀ = r/(2n + 1)
S₁ = an

Les étapes suivantes entrent dans le cas général où Q est un multiple de a :

u_n+1 = u_n - 1, et le trajet est x_n+1 = a/(2u_n - 1)

On s'arrête quand Σx_i ≥ D
La dernière étape est alors différente (si > D), car tout n'est pas consommé :
l'étape est raccourcie et on transfère plus que u_N+1a à la destination (considérée comme dépôt pour une étape N+1).

Si le but est d'aller le plus loin possible, il suffit de mettre un D très grand (et impossible à atteindre) dans le script.

Si les étapes sont en nombre entier de jours, le reste n'est plus nul aux étapes ultérieures.
D'ailleurs le critère sur le reste n'est plus valable.
Il peut être plus rentable de ne pas consommer tout le reste, et de faire une étape plus courte pour déposer plus, quitte à en laisser au dépôt suivant. Ou au contraire d'allonger l'étape, quitte à partir avec un déficit à l'étape suivante.

Soit donc S_n = na + r le stock disponible au départ de l'étape n, r ≠0.
Le nombre de trajets au départ de cette étape étant u_n = n+1, soit en tout 2n+1 trajets de longueur x_n.
Posons x = [r/(2n+1)], plus grand entier ≤ r/(2n+1) Il reste à choisir si x_n = x ou x+1.

Si x = 0
il faut prendre x = 1, ou laisser le reste et partir avec n allers et n-1 retours.
On consomme alors 2n+1 ou 2n-1 et il reste na + r - (2n+1) ou na - (2n-1)
Si r > 2, il vaut mieux utiliser le reste et partir n+1 fois
x ≠ 0
Si x_n = x, on ne consomme pas tout r et il reste > na au départ de l'étape suivante.
Elle ne comporte que n allers, on ne partira donc qu'en emportant na de cette étape.
Après les 2n-1 trajets sur le 1er jour de cette étape il restera na - (2n - 1)
Si par contre x_n = x + 1, au même point il restera na + r - (x + 1)(2n + 1)
Il faut donc allonger l'étape si r > (2n + 1)x + 2

Enfin si r = 0, (ou si on laisse tomber le reste) u_n = n, x_n = ceil(a/(2n - 1)), plus petit entier ≥ a/(2n - 1)