Самый длинный круг на графиках

Question

Я хочу решить следующую проблему:

У меня есть DAG, которая содержит города и задания между ними, которые необходимо выполнить. Задания предназначены для грузовых автомобилей, которые могут загружать определенный лимит. Чем больше загружен грузовик, тем лучше будет тур. Некоторые задания предназначены для загрузки чего-либо, а некоторые - для загрузки определенных вещей. Вы всегда можете ехать из города a в b, даже если между ними нет работы. Последнее ограничение заключается в том, что мне всегда нужно начинать с города а и возвращаться к нему, потому что там находится дом грузовиков:)

Сначала я подумал о алгоритме кратчайшего пути Дейкстры. Я мог бы легко превратить это в вычисление самого длинного пути. Моя проблема сейчас в том, что все эти алгоритмы предназначены для вычисления кратчайшего или самого длинного пути от вершины a до b, но мне нужно это от возврата к a - по кругу.

Есть ли у меня какие-нибудь пинки для разума?

Спасибо за ваш отзыв!

Marco

Answer 1

Эта безумная комбинация рюкзака и коммивояжера несомненно NP-хард .

Практически везде, когда вы хотите загрузить свой агент с оптимальным расписанием работы, или когда вы хотите построить маршрут через все вершины в графике, или когда вы чувствуете, что вам нужно найти " самый длинный путь * ", вы, скорее всего, столкнетесь с проблемой NP-complete или NP-hard .

Это означает, что не существует известного быстрого и точного решения проблемы, то есть того, которое выполняется за полиномиальное время.

Таким образом, вы должны создавать аппроксимации и реализовывать неоптимальные алгоритмы на основе ваших определенных условий. Какая потеря времени приемлема? Есть ли дополнительные модели, на которых грузовики могут ездить? Знаете ли вы больше о графике (например, разделена ли область на отдаленные плотные области)? Ответьте на эти вопросы, и вы найдете нестрогую эвристику, которая удовлетворит ваших клиентов.

---

* да, поиск самых длинных путей не так прост, как вы думаете. Задача с самым длинным путем является NP-полной, учитывая, что ваш график не ацикличен.

Answer 2

Вы пытаетесь найти наименьший возможный способ сделать все? Это напоминает мне о проблеме максимального потока / минимального сокращения. Вы можете приблизить лучший ответ по:

• Подключите все терминальные узлы к конечному end узлу.
• Запустите один из различных алгоритмов максимальный поток , чтобы найти максимальный поток между a и end.
• Возвращение в город a. Обновите график, чтобы отразить то, что вы только что сделали. Повторяйте, пока все работы не будут выполнены.

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

Примечание: Это работает только потому, что у вас есть DAG. Командующий коммивояжером также не будет NP-Complete для DAG, и, вероятно, будет невозможно даже поразить все узлы на графике. Перечитывая вашу проблему, кажется, что у вас нет DAG, так как вы можете вернуться в город a - это правда?

Answer 3

Разве это не проблема транспортировки ?

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

Я бы также спросил об ограничениях для грузовиков:

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

Answer 4

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

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

И, как упоминал Павел, эта проблема, безусловно, NP-сложная. У вас есть верхние границы для количества городов или максимального количества объектов, которые можно загрузить в грузовик?

PS: Вы хотите ЛУЧШЕЕ решение (максимальная прибыль - может быть нереалистичным с точки зрения времени обработки) или вы принимаете какое-то приближение?