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

Существует сеть городов, связанных дорогами различной цельной длины.

Путешественник хочет путешествовать в своей машине из одного города в другой. Однако он не хочет минимизировать пройденное расстояние; вместо этого он хочет свести к минимуму стоимость бензина в пути. Бензин можно купить в любом городе, однако каждый город поставляет бензин по разным (целочисленным) ценам (следовательно, самый короткий маршрут не обязательно самый дешевый). 1 единица бензина позволяет ему двигаться на 1 единицу расстояния. Его машина может содержать столько бензина в баке, и он может выбрать, сколько единиц бензина купить в каждом городе, в котором он путешествует. Найдите минимальную стоимость бензина.

Кто-нибудь знает эффективный алгоритм, который можно было бы использовать для решения этой проблемы? Даже название этого типа проблемы было бы полезно, чтобы я мог сам это исследовать! Очевидно, это не совсем так же, как проблема с коротким путем. Любые другие советы оценены!

РЕДАКТИРОВАТЬ - актуальная проблема, о которой я заявляю, что будет < 1000 городов; & 10000 дорог; и емкость бензобака будет где-то между 1 и 100.

Ответ 1

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

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

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

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

Затем использование Djikstra должно дать путь с наименьшей стоимостью от начала до конца.

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

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

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

Ответ 5

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

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

Придумайте функцию ранжирования для решений-кандидатов
Придумайте пул уникальных решений для кандидатов. Инициализировать его с некоторыми случайными способами. Может быть, 10 или 100 или 1000...
Скопируйте решение кандидата из пула и перепутайте его каким-то образом - добавить город, удалить город, добавить два города и т.д. Это может улучшить или ухудшить ситуацию - ваша рейтинговая функция поможет вам рассказать. Который один вы выбираете? Обычно вы выбираете лучшее, но время от времени, вы намеренно выбираете тот, который не должен застревать локальный оптимум.
Было ли уже оценено новое решение? Если да, напишите и перейдите к
- Если нет, продолжайте...
Добавьте возмущенного кандидата обратно в пул под его недавно вычисленным рангом
Продолжайте движение (повторите с № 3), пока не почувствуете, что сделали это достаточно долго.
Наконец, выберите ответ с лучшим рангом. А может и не быть оптимальным, но это должно быть очень хорошо.

Ответ 6

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

Переменные в этой конкретной проблеме будут представлять собой количество бензина, купленного в любом городе, сумму в цистернах автомобилей в любом городе по дороге и фактические пройденные дороги. Ограничения должны гарантировать, что автомобиль тратит необходимое топливо на каждую дорогу и не имеет меньше, чем 0 или более МАКС-единиц топлива в любом городе, и что дороги составляют путь от А до Б. Целью будет общая стоимость закупленного топлива.

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