Алгоритм гамильтонова цикла
Я искал некоторые алгоритмы гамильтоновых циклов, но не могу найти ни одной реализации, даже ни одного псевдокода! Мне даже не нужно выводить цикл, просто проверьте, есть ли на графике. Входные данные представляют собой граф с V вершинами и E ребрами. Кроме того, я хотел бы иметь алгоритм, чтобы проверить, имеет ли граф путь гамильтониана. Мне не нужно выводить путь, просто проверьте, есть ли он. Оба должны быть в полиномиальном времени.
2 ответа
Проблема является одной из проблем NP-Complete.
Алгоритм перебора просто создает все перестановки и проверяет, является ли одно из них реальным решением.
Проверка возможности:
пусть текущая перестановка будет v1,v2,...,vn: если для каждого i есть преимущество v_i -> v_(i+1) в графе, а также v_n->v1 - тогда решение возможно.
Альтернативой является создание графика G'=(V,E',w) где новые края E' = VxV (все ребра) и весовая функция:
w(u,v) = 1 if there is an edge (u,v) in the original graph
infinity otherwise.
Теперь у вас есть задача коммивояжера, и вы можете решить ее с помощью динамического программирования в O(n^2*2^n)
Если P = NP, гамильтоничность не может быть определена для общих графов за полиномиальное время.
На сайте http://fhcp.edu.au/slhweb/ существует онлайновая эвристика HCP, где вы можете загрузить график и проверить его, но если вам нужна собственная функция, вам нужно будет либо написать ее самостоятельно, либо объединить в чужой функции., Андрей Чалатурник написал очень хороший алгоритм.