Предложите алгоритм (график - возможно, NP-Complete)

Вы можете решить эту проблему напрямую, используя алгоритм Джикстры, если хотите увеличить размер графика. .

Предположим, ваш бензобак вмещает от 0 до 9 единиц бензина.

Идея состоит в том, чтобы разделить каждый город на 10 узлов, причем узел x для города t представляет собой город t с x единицами бензина в баке.

Затем вы можете построить рёбра с нулевой стоимостью на этом расширенном графике, чтобы представить путешествие между разными городами (используя в процессе бензин, так что вы перейдете от узла уровня 8 к узлу уровня 5, если расстояние было 3), и больше ребер к представляют собой заправку бака в каждом городе одной единицей бензина (стоимость зависит от города).

Тогда применение джикстры должно дать самый дешевый путь от начала до конца.

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

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

Я думаю, вы можете решить эту проблему с помощью динамического программирования. Для каждого узла вы сохраняете массив кортежей стоимости бензина и длину пути, по которому вы используете этот бензин, содержащий оптимальное решение. На каждом шаге вы проходите через все узлы, и если есть узел, к которому вы можете перейти, у которого уже есть решение, вы проходите через все узлы, к которым вы можете перейти с решением. Вы выбираете минимальную стоимость, но обратите внимание: вы должны учитывать стоимость бензина в текущем узле. Все затраты в массиве, которые выше, чем стоимость в текущем узле, вместо этого могут быть куплены в текущем узле. Обратите внимание, что узлы, для которых уже есть решение, следует пересчитать, поскольку узлы, к которым вы можете перейти оттуда, могут измениться. Вы начинаете с конечного узла, устанавливая в качестве решения пустой массив (или одну запись со стоимостью и длиной 0). Окончательное решение - взять решение в начале и просуммировать каждую стоимость * длину.

Я бы попробовал это:

1. Найдите кратчайший маршрут от начала до пункта назначения. Для этого подходит алгоритм Дейкстры.
2. Найдите минимальную стоимость бензина для проезда по этому маршруту. Я не знаю ни одного стандартного алгоритма для этого, но если на маршруте нет большого количества городов, даже исчерпывающий поиск не должен быть невозможным с вычислительной точки зрения.
3. Найдите следующий кратчайший маршрут ...

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

Итак, используйте 2 алгоритма, по одному для каждой части задачи.

Это можно оптимизировать подходящим образом с помощью генетического алгоритма. Генетические алгоритмы побеждают людей в решении некоторых сложных задач: http://en.wikipedia.org/wiki/Genetic_algorithm

Суть генетического алгоритма:

1. Придумайте функцию ранжирования для возможных решений
2. Придумайте набор уникальных возможных решений. Инициализируйте его с помощью некоторых случайно сгенерированных возможностей. Может, 10, 100 или 1000 ...
3. Скопируйте возможное решение из пула и измените его каким-либо образом - добавьте город, удалите город, добавьте два города и т. Д. Это может улучшить или ухудшить ситуацию - ваша функция ранжирования поможет вам в этом. Какой ты выберешь? Обычно вы выбираете лучшее, но время от времени вы намеренно выбираете тот, который не позволяет избежать застревания на локальном оптимуме.
4. Has the new solution already been ranked? If yes, junk it and go to
   1. If no, continue...
5. Добавить возмущенного кандидата обратно в пул под его вновь рассчитанным рангом.
6. Продолжайте так (повторите с пункта 3), пока не почувствуете, что делаете это достаточно долго.
7. Наконец, выберите ответ с лучшим рейтингом. Возможно, это не оптимально, но должно быть неплохо.

Вы также можете сформулировать это как проблему целочисленного линейного программирования (ILP). Преимущество состоит в том, что для этой задачи существует ряд готовых решателей, и сложность не будет расти так быстро, как в случае решения Петерса с размером резервуара.

Переменными в этой конкретной задаче будут количество бензина, купленного в каком-либо одном городе, количество бензина в баке в любом городе по пути и фактически пройденные дороги. Ограничения должны гарантировать, что автомобиль расходует необходимое топливо на каждой дороге и не имеет менее 0 или более MAX единиц топлива в любом городе, и что дороги составляют путь от A до B. общая стоимость закупленного топлива.

Все это может выглядеть чудовищно (как часто бывает в формулировках ПДОДИ), но это не значит, что эту проблему нельзя решить в разумные сроки.