Библиотека коммивояжера, использующая алгоритм приближения

Question

В настоящее время я делаю проект, который требует быстрого решения TSP (около 50-100 узлов за 2 секунды).Существует множество алгоритмов аппроксимации, но у меня нет ни времени, ни желания анализировать их и кодировать их самостоятельно.

Существуют ли свободные библиотеки, которые могут решить проблему TSP (аппроксимация тоже подойдет)?Что-то вроде sortedNodes = solveTspPrettyPlease(nodes, 2sec) было бы просто замечательно.

Заранее спасибо.

Answer 1

• http://code.google.com/p/java-traveling-salesman/ - решение генетического алгоритма
• http://www.adaptivebox.net/CILib/code/tspcodes_link.html - ссылки на множество решений, не все из которых (если есть?) Являются библиотеками

Answer 2

Что касается ссылки http://code.google.com/p/java-traveling-salesman/, вам необходимо получить CVS-версию jgap с 1 апреля 2006 года. Вам также потребуется немного взломать код tsp.Измените JGapGreedyCrossoverEngine.java с защищенной двойной оценки (хромосома a_subject) на защищенную двойную оценку (IChromosome a_subject)