TSP optim tour

Question

Я написал бактериальный эволюционный алгоритм для решения задач TSP. Я выбрал экземпляр XQF131 (http://www.math.uwaterloo.ca/tsp/vlsi/index.html), чтобы проверить свой алгоритм. Эта проблема была решена Concorde, а оптимальный тур - 564. Но я вычислил длину оптимального тура, и это 567,2029. (http://www.math.uwaterloo.ca/tsp/vlsi/xqf131.tour.html) С моим алгоритмом я нашел лучшее решение 566,4142. Мой вопрос: как работает алгоритм Concorde? Он вычисляет оптимальное решение или приближение?

Спасибо за ответы!

Answer 1

Согласно странице wikipedia, this и формулировке на сайте, который вы опубликовали, предполагается, что вы должны быть оптимальным, а не приближением, и Concorde должен дать оптимальные решения.

Я бы проверял свои расчеты, чтобы убедиться, что они действительно ошибались, сообщая о длине. Если да, вы можете, вероятно, опубликовать это.

Даже если нет, ваш алгоритм, вероятно, только немного хуже. Если это быстрее, чем Concorde или, по крайней мере, лучше, чем другие эволюционные методы, вы, вероятно, все равно можете что-то публиковать.

Хорошая работа и удача!

Answer 2

Вы уверены, что вы правильно рассчитали расстояния? Кажется, вы должны получать целое расстояние. Действительно, с сайта, который вы цитируете: «В этих примерах стоимость поездки между городами определяется евклидовым расстоянием, округленным до ближайшего целого числа».

Надеюсь, ваш алгоритм все же обнаружил оптимальное решение ...