Известно, что гамильтонов цикл в графе можно найти методом динамического программирования за $%2^n$%, где $%n$% -- количество вершин в графе. Можно лы быстрее? И можно ли найти за $%2^n$%, но без использования экспоненицальной памяти?

задан 23 Ноя '11 20:00

изменен 29 Ноя '11 13:37

Expert's gravatar image


15719

@Sasha, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(20 Апр '14 17:41) Angry Bird
10|600 символов нужно символов осталось
2

Ну про алгоритмы за $%O(2^n)$% я не слышал, слышал только про $%O(n^22^n)$%. Википедия предлагает метод включений-исключений, с помощью которого можно немного ухудшить асимптотику, но улучшить объем используемой памяти. Но я не смог найти ни одной статьи, в которой это описывается и которая есть в свободном доступе.

ссылка

отвечен 24 Ноя '11 4:45

Да-да, я $%n^22^n$% и имел в виду (при изучении экспоненциальных по времени алгоритмов часто забывают про полиномиальные множители). С помощью формулы включений-исключений и умножения матриц можно обойтись и без экспоненциальной памяти, да. Чуть позже напишу детали.

(24 Ноя '11 22:00) Sasha
10|600 символов нужно символов осталось
0

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

ссылка

отвечен 23 Ноя '11 21:20

изменен 23 Ноя '11 21:48

Ну, гамильтонов цикл -- NP-полная задача, действительно, в то время как эйлер цикл -- задача из P. Поэтому прямо вот свести вряд ли получится.

(24 Ноя '11 21:58) Sasha

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

(24 Ноя '11 22:08) Lonelind
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×104
×6

задан
23 Ноя '11 20:00

показан
3006 раз

обновлен
20 Апр '14 17:41

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru