Алгоритм с полиномиальным временем для поиска гамильтонова блуждания в графе

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

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

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

Для меньшей сложности вы можете найти короткую прогулку, используя жадный алгоритм.

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

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

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

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

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

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

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

Павел

Мой запрос: покажите, что задача поиска RHAM для нахождения гамильтонова цикла в графе G является самовосстанавливающийся Задача поиска R является самовосстанавливающейся, если она сводится по Куку к проблеме принятия решения
SR = { x : R(x) ≠ ∅ }