Существует ли оптимальный алгоритм для приблизительного решения задачи коммивояжера при большом количестве городов?

Question

[Kalombyr]

Здравствуйте!
Подскажите, пожалуйста, сабж.

Под большим количеством понимается от 500 и больше.
Реализовываться будет а c++ с 128Гб оперативки, с попыткой распараллелить на 16 потоков.

Пока что пробовал метод ветвей и границ (да же 100 то с трудом), генетический (далеко не оптипально + непонятно как
подобрать параметры). Сейчас пытаюсь реализовать муравьиную колонию.

От алгоритма желательно как обычно - наименьшее время с наилучшим результатом. Возможные ресурсы выше указаны.

Пытался найти где-либо сравнения существующих алгоритмов на одном и том же наборе данных, но увы. Чувствую, что сил моих не хватит на написание (или портирование уже написанных) и прогон хотя бы сто тысяч раз для хоть какой-то статистики.

P.S. Наборы данных желательно с TSPLIB =)

Answer 1

[kova1ev]

на кэгле в новый год было соревнование по tsp на 198000 городов, вот оно ,только там доп.условие было, по возможности id каждого десятого города в пути должно быть простым числом.

посмотрите в кернелах и дискуссиях, там много инфы по разным решениям и реализации. Если вкратце - то решение сводится к прогонам 2-opt, 3-opt, 4-opt, 5-opt чем дольше, тем лучше, с постепенным улучшением результата. Плюс периодические рандомные изменения в пути, чтобы выбить из локального минимума (метод отжига).

Comments

[Kalombyr]

Спасибо! 2-opt кажется неплох.

[kova1ev]

Kalombyr ,вот еще хорошая статья