Крупным застряли на задаче графа

Question

У вас есть граф K порты и N городов, есть М отгружается в каждом порта, несущие блоки нагрузки X каждого (все из них полностью загружены в начале и может» t reload в любое время, и все они несут такое же количество груза). Каждый город нуждается в некотором количестве груза (может нужна такая же сумма, не может - зависит от ввода), а судно может только выгружать груз в городе, если оно отвечает целым потребностям города (т. Е. Если город нуждается в 10 единиц груза, вы не можете выгрузить 7 из одного судна , а 3 из другого - либо поставляет все 10 единиц, либо не останавливается там).

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

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

C1 <--11km--> P1 <--10km--> C2 <--10km--> P2 
where P are ports and C are cities 
(There should also be direct edges from C1 to C2 or P1 to P2 for example 
but I omitted them for clarity - let's just assume here all the verices 
lie on the same line and so we could ignore them) 

причиной судна от P1 перейдет к C2, тем самым сделав маршрут до C1 более длинным, в то время как оптимальное решение будет состоять в том, чтобы он переместился в C1, который лежит дальше, и пусть корабль от P2 ручки C2. Каков правильный способ решения этого? Или, может быть, это NP-полный, и нет? Например, я пытался думать об этом с точки зрения TSP, но это не слишком похоже на то, что вы не смотрите на гамильтоновские циклы здесь.

Answer 1

Ваша проблема NP-hard, как видно из следующего. Представьте, что у вас есть два порта, в которых у вас есть два корабля на одном порту и столько же кораблей, сколько вы хотите на другом порту, а стоимость поездки из первого порта в любой город в основном равна нулю, а стоимость поездки со второго порта до любой город очень большой. Также представьте, что стоимость путешествия из любого города в другой очень мала. Предположим, что каждый корабль имеет грузоподъемность М, а общий спрос на грузы в городах составляет 2 * М. Затем вы хотите разделить города на два набора, где общий спрос на каждый набор городов равен M, так что вы можете использовать два корабля с пропускной способностью M, которые имеют дешевые транспортные расходы из первого порта. В противном случае вы также должны использовать другие корабли из другого порта и нести очень большие транспортные расходы. Однако найти разбиение набора чисел на два непересекающихся множества, имеющих одну и ту же сумму, является NP-полной задачей. Таким образом, ваша проблема NP-hard.

Таким образом, эвристика или грубая сила, вероятно, являются вашим лучшим способом.

Answer 2

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

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

State node: 
    List of ships 
    List of cities 

Ship: 
    Cargo Capacity 
    Current Location 

City: 
    Cargo Delivered 

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

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

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

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

Тогда вам понадобится функция Expand(Node n), которая дает вам все возможные состояния преемника на основе всех возможных действий, которые вы могли бы предпринять.

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

Затем вы просто запускаете его через стандартный поиск A *! Вот страница Википедии, если вы не знакомы с ней. Я уверен, что есть много других хороших ресурсов для изучения этого. Дайте мне знать, если вы хотите получить более подробное объяснение части алгоритма A * проблемы. http://en.wikipedia.org/wiki/A*_search_algorithm

У вас есть все строительные блоки, как только вы закрываете вещи я уже упоминал: представление состояния, справочной информации эвристической функция может получить доступ, эвристическая функция, которая также проверяет состояние цели, и функция расширения, которая получает состояния преемника, основанные на возможных действиях, которые вычисляют весовые коэффициенты с использованием фоновых данных. Теперь вы просто используете те немногие строительные блоки в своей реализации алгоритма поиска A *, и bam, у вас есть хорошее решение. Имейте в виду, что это не может быть оптимальным решением, и не может быть гарантировано найти решение. Я считаю, что свойства вашей эвристической функции (допустимы и/или согласованы?) Будут определять, гарантировано ли решение или оптимальное решение.