1 Тема от Isaev

  • Isaev
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-10-01
  • Сообщений: 3

Тема: Алгоритм поиска Гамильтонова пути на неориентированом графе

Всем доброго дня!
Нужно реализацию алгоритма поиска Гамильтонова пути на неориентированом графе за полиноминальное время из заданного узла. По-умолчанию в данном графе из данного узла Гамильтонов путь возможно построить, потому проверка возможности построения не требуется.
Информации вроде гуглится много, но конкретики никакой.
Есть человек (как бы не единственный), который утверждает, что ему удалось реализовать данный алгоритм за полиноминальное время, но исходников он не открывает.

Вот его описание теории: http://www.iaeng.org/publication/IMECS2 … 92-294.pdf
И сам бинарник: http://blog.sciencenet.cn/home.php?mod= … ;id=315228

Эта задача, на сколько я понимаю всегда относилась всегда к NP-полной, если её удалось перевести в полиноминальные, то это прорыв в области математики! Но пока он никому ничего не доказал.
Хотя его бинарник решает на порядки быстрее найденных мною реализаций...
Это явно не из-за оптимизации алго, а из-за абсолютно другого подхода к решению проблемы.
Хотя, кто знает.
Обидно, что всегда китайцы нас дрючат :) неужели мы не можем?

Может кто занимался подобной проблемой и/или есть наработки в этой области?

Заранее благодарен.

2 Ответ от cat_baxter

  • Зарегистрирован: 2011-10-08
  • Сообщений: 7

Re: Алгоритм поиска Гамильтонова пути на неориентированом графе

http://www.dharwadker.org/hamilton/ это не то же?

3 Ответ от Isaev

  • Isaev
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-10-01
  • Сообщений: 3

Re: Алгоритм поиска Гамильтонова пути на неориентированом графе

cat_baxter пишет:

http://www.dharwadker.org/hamilton/ это не то же?

Да, оно... Надо только потестить по скорости, на сколько он не уступает
Я их уже много находил, но все не тянут при количествах узлов от 10.000

4 Ответ от fuxx

  • fuxx
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-10-26
  • Сообщений: 1

Re: Алгоритм поиска Гамильтонова пути на неориентированом графе

Существуют графы, в которых этот алгоритм  не находит путь. Т.е. предположительно он страдает false negative.

Не знаю как приаттачить пример сюда. У меня 1849 вершин. Справедливости ради нужно сказать что условиям Дирака и Оре он не удовлетворяет, но это ещё ничего не доказывает. Другие построенные мною для данной проблемы графы имели решение и я ожидаю что "по построению" решение должно быть.