Interested Article - Задача о джипе

Задача о джипе ( англ. Jeep problem, desert crossing problem, exploration problem) — математическая задача, целью которой является максимизация пути, который можно преодолеть на автомобиле с полным баком топлива в отсутствие инфраструктуры, к примеру, в пустыне.

Постановка задачи

Суммарная ёмкость канистр и бензобака джипа равна 100 литров, расход топлива равен постоянному числу, к примеру, на 1 участок тратится 1 литр. Количество топлива на базе не ограничено. Можно выполнять ещё два действия: сливать некоторую часть топлива в любой точке пустыни (в любой точке пустыни может находиться топливная бочка, в которой можно оставить неограниченную часть топлива на неограниченное время), а также забирать некоторую часть топлива из бочки, в которой уже находилось некоторое количество топлива. У этой задачи есть две разновидности: задача исследования пустыни и задача пересечения пустыни. В первом случае ставится цель вернуться на базу (в начальное положение), во втором нужно просто преодолеть участок, больший, чем это позволяет запас топлива.

Решение

Как уже отмечалось выше Задача о джипе имеет две разновидности: задача исследования и задача пересечения пустыни. Рассмотрим каждую из них.

Задача исследования

Стратегия, которая помогает увеличить расстояние, которое может проехать джип в задаче исследования пустыни:

Джип делает $n$ $n$ поездок, в начале каждой поездки он имеет полный запас топлива. Полный бак обозначим как 100 % или 1, соответствующую дистанцию — 1.
При первой поездке джип едет на расстояние ${\frac {1}{2n}}$ ${\frac {1}{2n}}$ и оставляет там ${\frac {n-1}{n}}$ ${\frac {n-1}{n}}$ часть топлива, после этого запас топлива станет равным ${\frac {1}{2n}}$ ${\frac {1}{2n}}$ , чего достаточно для возвращения на базу.
При каждой следующей поездке джип, доехав до первой остановки, израсходует ${\frac {1}{2n}}$ ${\frac {1}{2n}}$ часть топлива и забирает ${\frac {1}{2n}}$ ${\frac {1}{2n}}$ из бочки, таким образом, доехав до первой остановки, джип имеет полный запас топлива, вследствие чего он может продолжать исследование. На обратном пути джип опять забирает ${\frac {1}{2n}}$ ${\frac {1}{2n}}$ из бочки, чего достаточно для возвращения на базу.
Во время второй поездки джип едет к первой остановке и дозаправляется, после чего едет на расстояние 1/(2 n − 2) и оставляет на второй остановке (n-2)/(n-1) топлива, после чего запас топлива равен ${\frac {1}{2n-2}}$ ${\frac {1}{2n-2}}$ , чего достаточно, чтобы вернутся к первой стоянке, дозаправиться и вернуться на базу.
При каждой следующей поездке джип дозаправляется ${\frac {1}{2n-2}}$ ${\frac {1}{2n-2}}$ на прямом пути и таким же количеством на обратном, по аналогии с первой остановкой.
Джип продолжает исследование, при каждой k -й поездке он создает новую остановку с бочкой топлива на расстоянии ${\frac {1}{2n-2k+2}}$ ${\frac {1}{2n-2k+2}}$ от предыдущей остановки и оставляет там ${\frac {n-k}{n-k+1}}$ ${\frac {n-k}{n-k+1}}$ количество топлива. Для каждой с n — k поездок джип дозаправляется на ${\frac {1}{2n-2k+2}}$ ${\frac {1}{2n-2k+2}}$ количество топлива от k -й бочки на прямом пути и таким же количеством на обратном пути, чего достаточно, чтобы доехать до стоянки k − 1 и вернуться на базу.

Когда джип едет последний раз, имеется n − 1 бочек с топливом. Последняя бочка имеет 1/2 количества топлива, предпоследняя — 1/3 и так далее до первой бочки, в которой 1/ n количества топлива. Имея в виду, что на выезде из базы джип имеет полный запас топлива, в сумме он может преодолеть расстояние

1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{k=1}^{n}{\frac {1}{k}}

1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{{k=1}}^{n}{\frac {1}{k}}

Задача пересечения

Расстояние, пройденное джипом в последней поездке это n -е гармоническое число — H _n . Так как гармоническое число может расти бесконечно, то и длина пути, которую может пройти джип, также может быть бесконечной при условии наличия достаточного количества топлива на базе, но при этом количество бочек для дозаправки будет расти экспоненциально.

Решение задачи пересечения пустыни аналогично решению задачи исследования пустыни, за исключением того, что при последней поездке нет необходимости дозаправляться на обратном пути. На k -й поездке джип оставляет k -ю бочку на дистанции 1/(2 n − 2 k + 1) от предыдущей остановки и оставляет (2 n − 2 k − 1)/(2 n − 2 k + 1) количества топлива. При каждой из последующих n − k − 1 поездок джип дозаправляется 1/(2 n − 2 k + 1) количеством топлива на k -й остановке на прямом и обратном пути.

Когда джип едет в последний раз, имеется n − 1 бочек с топливом. Последняя имеет 1/3 часть топлива, предпоследняя — 1/5 и так далее, ближайшая имеет 1/(2 n − 1) количества топлива. В этом случае джип может проехать

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}

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}}

Отметим, что

\sum _{k=1}^{n}{\frac {1}{2k-1}}>\sum _{k=1}^{n}{\frac {1}{2k}}={\frac {1}{2}}H_{n}

\sum _{{k=1}}^{n}{\frac {1}{2k-1}}>\sum _{{k=1}}^{n}{\frac {1}{2k}}={\frac {1}{2}}H_{{n}}

то есть теоретически возможно преодолеть пустыню любого размера, имея достаточно топлива на базе. Как и в предыдущей задаче, требуемое для этого количество топлива растет экспоненциально.