Нахождение гамильтонова пути в ориентированном циклическом графе

Question

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

Спасибо

Answer 1

Эта проблема является частным случаем задачи оптимальной схемы Эйлера, где все граничные веса равны 1;исходная задача является NP-полной.Более того, эта задача может быть использована для решения задачи о гамильтоновом графе (гамильтонов цикл существует тогда и только тогда, когда оптимальная схема пересекает все узлы), поэтому он остается NP-полным даже с ограничением в особом случае.Любое точное решение потребует (если P = NP) экспоненциального времени.Вы можете найти этот документ полезным;он описывает алгоритм аппроксимации за полиномиальное время для этой задачи, а также алгоритм за полиномиальное время для случаев, когда граф имеет максимум 4:

Qiao, Yu.« Оптимальная схема Эйлера с максимальной непрерывной стоимостью .»IEICE Trans.Основы E90-A, нет.1 (2007): 274-280.

Answer 2

Хорошее приближение дает кривую Гильберта.