|
Известно, что гамильтонов цикл в графе можно найти методом динамического программирования за $%2^n$%, где $%n$% -- количество вершин в графе. Можно лы быстрее? И можно ли найти за $%2^n$%, но без использования экспоненицальной памяти? задан 23 Ноя '11 20:00 
Sasha |
|
Ну про алгоритмы за $%O(2^n)$% я не слышал, слышал только про $%O(n^22^n)$%. Википедия предлагает метод включений-исключений, с помощью которого можно немного ухудшить асимптотику, но улучшить объем используемой памяти. Но я не смог найти ни одной статьи, в которой это описывается и которая есть в свободном доступе. отвечен 24 Ноя '11 4:45 
freopen Да-да, я $%n^22^n$% и имел в виду (при изучении экспоненциальных по времени алгоритмов часто забывают про полиномиальные множители). С помощью формулы включений-исключений и умножения матриц можно обойтись и без экспоненциальной памяти, да. Чуть позже напишу детали.
(24 Ноя '11 22:00)
Sasha
|
|
Задача поиска Гамильтонова цикла является NP-полной. Поэтому появление экспоненциальных времени и памяти вполне ожидаемо. Хотя можно свести гамильтонов цикл к эйлерову, поменяв местами вершины и ребра, соединяя две вершины, если в исходном графе соответствующие ребра имеют общую вершину. отвечен 23 Ноя '11 21:20 
Lonelind Ну, гамильтонов цикл -- NP-полная задача, действительно, в то время как эйлер цикл -- задача из P. Поэтому прямо вот свести вряд ли получится.
(24 Ноя '11 21:58)
Sasha
Есть теорема (не помню, чья), доказывающая, что любой граф с гамильтоновым циклом можно свести к графу, описывающему соответствующий эйлеров цикл.
(24 Ноя '11 22:08)
Lonelind
|
@Sasha, Если вы получили исчерпывающий ответ, отметьте его как принятый.