1 Ответ от Isaev

(3 ответов, оставленных в Algo)

cat_baxter пишет:

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

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

Перейти к разделу: Algo

2 Ответ от Isaev

(14 ответов, оставленных в News)

.chm выше не открывается ни в чём neutral

Перейти к разделу: News

3 Тема от Isaev

(3 ответов, оставленных в Algo)

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

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

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

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

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

Перейти к разделу: Algo