NP

[che_shr_cat]

Собираетесь в Швецию? Не забудьте путеводитель:

Comments

[imil]

Ого. Не думал, что задачу коммивояжера такой сложности можно решить.

[che_shr_cat]

Ха! А вот это видел:

The largest solved instance of the traveling salesman problem consists of a tour through 85,900 cities in a VLSI application that arose in Bell Laboratories in the late 1980s. The computation with Concorde was carried out in 2005/06 and reported in the book The Traveling Salesman Problem: A Computational Study.

http://www.tsp.gatech.edu/pla85900/index.html

85900 против 24978.

[imil]

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

[che_shr_cat]

У меня ещё не было времени внимательно прочитать, как именно они это делали. При беглом взгляде сложилось впечатление, что они то ли как-то по-умному отсекали плохие ветви в дереве, то ли прикрутили генетические алгоритмы, то ли и то, и другое вместе. Но могу и ошибаться. И также интересно, как они доказали, что это решение лучшее. Опять же при беглом взгляде я этого не понял.