Цикл максимального веса в графе

Question

Учитывая взвешенный граф (направленный или непрашенный), мне нужно найти цикл графа с максимальным весом.

Вес цикла - сумма веса краев графа.

Это может быть любой цикл, а не просто базовый цикл, для которого мы можем

• Найти все базовый цикл (см. Алгоритмы идентификации всех баз цикла в неопрященном графике )
• вычислить вес каждого базового цикла и найдите максимум

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

Есть ли у вас есть идея найти максимальный вес веса без перечисления всех циклов?

Если вам нужна гипотеза на графике (например, положительные веса), пожалуйста, указывает их.

Answer 1

Это NP-трудно.

Гамильтоновая проблема цикла может быть сведена к этому.

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

Теперь запустите свой алгоритм, чтобы получить максимальный цикл веса. Если вес находится <n, то исходный график не имеет гамильтонового цикла, иначе он делает.

Answer 2

Если вы можете найти минимальный взвешенный путь в вашем конкретном случае, просто обратитесь за знаки всех весов и примените свой алгоритм. Конечно, вы делаете некоторые неустановленные предположения, потому что аргумент Moron является правильным (без каламбура). Предположения, которые вы делаете, могут быть положительными весами или без отрицательных циклов веса. Я думаю, что вы должны приложить усилия, чтобы указать их вместо того, чтобы позволить людям поискать в бесконечном пространстве возможных предположений. Что касается жесткости результатов, это также трудно приблизиться несколькими способами, проверить Эта бумага. Отказ Та же бумага содержит несколько положительных результатов для важных типов графиков, но оно касается самого длиннее невзвешенных путей, поэтому я предполагаю, что большинство алгоритмов в статье не будут напрямую помочь в вашем случае. Если вы ищете «тяжелые циклы», вы найдете ряд интересных бумаг, но они более математические в характере. Если ваши веса являются небольшими целыми числами (до многочлена в размере графика), вы можете попытаться заменить каждый край с невзвешенным путем, чтобы уменьшить свою проблему в невывесшевленный случай. Я надеюсь, что это поможет некоторой степени, но у вас может быть открытая проблема исследований в ваших руках.