Полиномиальный алгоритм времени для нахождения гамильтонова обхода в [закрытом] графике

Это - завершенный NP. Но если Вам действительно удается найти хороший метод, сообщите мне, и я покажу Вам, как разбогатеть.

Нахождение лучшего алгоритма для самого короткого маловероятно, поскольку это - NP трудно. Но существует некоторая эвристика, которую Вы могли попробовать, и возможно Вы могли бы хотеть консультироваться со своими примечаниями лекции для тех ;).

Для меньшей сложности Вы могли найти короткое (выход) обход с помощью жадного алгоритма.

В целом как (версия решения) гамильтонова проблема Пути полна NP, Вы не можете надеяться получить полиномиально-разовый алгоритм для нахождения гамильтоновых путей. Можно немного ускорить его с обычным N! прием ^{динамического программирования  N22N} (вычисляют hp [v] [w] [S] =, "является там путем, который имеет конечные точки v и w и чьи вершины являются подмножеством S" для каждого подмножества S и каждых двух вершин v и w в нем с помощью DP), но это все еще экспоненциально.

Однако существует много специальных видов графиков, для которых будут всегда существовать гамильтоновы пути, и они могут быть найдены легко (см. работу Posa, Dirac, Орегон, и т.д.),

Например, следующее верно: Если каждая вершина графика имеет градус, по крайней мере, n/2, то график имеет гамильтонов путь. Можно на самом деле найти один в O ⁽ⁿ²⁾, или IIRC даже O (n регистрируют n), если Вы делаете это более умно.
[Грубый эскиз: Во-первых, просто соедините все вершины в некотором "гамильтоновом" цикле, nevermind, если края находятся на самом деле в графике. Теперь для каждого края (v, w) Вашего цикла, который не находится на самом деле в графике, рассматривают остальную часть цикла: v... w. Как градус (v) +deg (w)> =n, там существуйте последовательный x, y в Вашем списке (в том порядке) таким образом, что w является соседом x, и v является соседом y. [Доказательство: Рассмотрите {группу всех соседей w} и {группа всех преемников в Вашем списке соседей v}; они должны пересечься.] Теперь изменяют Ваш цикл [v.. xy... wv] к [vy... wx... v] вместо этого, это имеет по крайней мере один меньше недопустимого края, таким образом, Вы должны будете при большинстве n повторений получить истинный гамильтонов цикл. Больше деталей здесь.]

BTW: если то, что Вы ищете, является просто обходом, который включает каждый край однажды, он назвал Эйлеров обход и для графиков, которые имеют его (количество вершин нечетного градуса 0 или 2), можно довольно легко быть найден в полиномиальное время (быстро).

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

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

Хммм .. это зависит от ваших определений. Гамильтонов путь заведомо NP-полон. Однако гамильтонова прогулка, которая может посещать ребра и вершины более одного раза (да, она все еще называется гамильтоновой, если вы добавляете бит ходьбы в конце), может быть вычислена в O (p ^ 2logp) или O (max (c ^ 2plogp , | E |)) до тех пор, пока ваш граф удовлетворяет определенному условию, которое Дирак впервые предположил, а Такамизава доказал. См. Takamizawa (1980) «Алгоритм поиска короткого замкнутого покрывающего блуждания в графе».

Пол