Как найти число гамильтоновых циклов, в которых не используются "запрещенные" ребра?
Этот вопрос перефразирует этот вопрос. Проблема с застреванием кода заключается в следующем:
Вам дан полный ненаправленный граф с N узлами и K "запрещенными" ребрами. N <= 300, K <= 15. Найти число гамильтоновых циклов в графе, которые не используют ни одного из K "запрещенных" ребер.
Простой подход DP O(2^N*N^2) не работает для таких N. Похоже, что выигрышные решения O(2^K), Кто-нибудь знает, как решить эту проблему?
2 ответа
Давайте выясним для каждого подмножества S запрещенных ребер, сколько существует гамильтоновых циклов, которые используют все ребра S. Если мы решим эту подзадачу, то мы решим проблему с помощью формулы включения-исключения.
Теперь, как мы решаем подзадачу? Давайте нарисуем все ребра S. Если существует вершина степени больше 2, то, очевидно, мы не можем завершить цикл, и ответ равен 0. В противном случае граф делится на связные компоненты. Каждый компонент представляет собой единственную вершину, цикл или простой путь.
Если существует цикл, то он должен пройти через все вершины, иначе мы не сможем завершить гамильтонов цикл. Если это так, ответ равен 2. (Цикл может быть пройден в двух направлениях.) В противном случае ответ равен 0.
Оставшийся случай - когда есть c путей и k отдельных вершин. Чтобы завершить гамильтонов цикл, мы должны выбрать направление каждого пути (2 ^ c пути), а затем выбрать порядок компонентов. У нас есть компоненты c+k, поэтому их можно переставить в (c+k)! пути. Но нас интересуют циклы, поэтому мы не различаем упорядочения, которые превращаются друг в друга циклическими сдвигами. (Таким образом, (1,2,3), (2,3,1) и (3,1,2) одинаковы.) Это означает, что мы должны разделить ответ на количество смен, c+k. Таким образом, ответ (на подзадачу) 2^c (c+k-1)!,
Эта идея реализована в решении bmerry (кстати, очень чистый код).
Задача о гамильтоновом цикле является частным случаем задачи коммивояжера (получается путем задания расстояния между двумя городами конечной постоянной, если они смежны, и бесконечности в противном случае.)
Это задачи NP Complete, которые простыми словами означают, что их быстрое решение не известно.
Тривиальный эвристический алгоритм определения местоположения гамильтоновых путей состоит в том, чтобы построить путь abc... и расширить его до тех пор, пока он больше не станет возможным; когда путь abc... xyz больше не может быть расширен, поскольку все соседи z уже лежат на пути, каждый возвращается на один шаг назад, удаляя ребро yz и расширяя путь другим соседом y; если никакой выбор не приводит к гамильтонову пути, тогда делается следующий шаг назад, удаляя ребро xy и расширяя путь другим соседом x, и так далее. Этот алгоритм, безусловно, найдет гамильтонов путь (если он есть), но он работает за экспоненциальное время.
Для дополнительной проверки Н.П. Пройдите проблемную главу "Введение в Алгос" Кормена