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

Question

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

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

Answer 1

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

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