Цикл максимального веса на графике
Учитывая взвешенный график (направленный или ненаправленный), мне нужно найти цикл графика с максимальным весом.
Вес цикла является суммой веса ребер графа.
Это может быть любой цикл, а не только базовый цикл, для которого мы можем
- найти весь базовый цикл (см. Алгоритмы для идентификации всех баз циклов в неориентированном графе)
- рассчитать вес каждого базового цикла и найти максимальный
Я мог бы попытаться перечислить все циклы графа и затем вычислить максимум, но общее количество циклов может быть действительно большим (если граф завершен, то любая последовательность вершин, где первый и последний совпадают, является циклом).
Есть ли у вас идея найти этот максимальный весовой цикл без перечисления всех циклов?
Если вам нужна гипотеза на графике (например, положительные веса), укажите их.
2 ответа
Это NP-Hard.
Задача гамильтонова цикла может быть сведена к этому.
Учитывая график, для которого нам нужно проверить, существует ли гамильтонов цикл или нет, присвойте вес 1 каждому ребру.
Теперь запустите ваш алгоритм, чтобы получить максимальный весовой цикл. Если вес
Если вы можете найти минимальный взвешенный путь в вашем конкретном случае, просто поменяйте местами знаки всех весов и примените свой алгоритм. Конечно, вы делаете некоторые неустановленные предположения, потому что аргумент Морон является правильным (не каламбур). Допущения, которые вы делаете, могут быть положительными весами или не иметь отрицательных весовых циклов. Я думаю, что вы должны приложить усилия, чтобы сформулировать их, вместо того, чтобы позволить людям искать в бесконечном пространстве возможных предположений. Что касается результатов по твердости, то это также трудно приблизить несколькими способами, посмотрите эту статью. Эта же статья содержит несколько положительных результатов для важных типов графиков, но она касается длинных невзвешенных путей, поэтому я предполагаю, что большинство алгоритмов в статье не помогут напрямую в вашем случае. Если вы ищете "Тяжелые циклы", вы найдете много интересных статей, но они более математичны. Если ваши веса - маленькие целые числа (вплоть до многочлена по размеру графика), вы можете попробовать заменить каждое ребро невзвешенным путем, чтобы свести вашу проблему к невзвешенному случаю. Я надеюсь, что это в некоторой степени поможет, но у вас может быть проблема с открытыми исследованиями.