Задача коммивояжера: обходим 750 точек за 5 сек

[gybson_63]

Назвать Дейкстру или A* для поиска пути заменой GA для решения задачи коммивояжёра это очень смело. А в такой постановке задача должна решать за одно действие буквально, даже в уме и имеет множество оптимальных решений.

[wataru]

ГА обрабатывает этот случай за 517 секунд. С ошибкой 24,7% (так себе точность мягко говоря).

Кстати, откуда ошибка взята? Оптимальное решение для теста уже известно? Как долго и чем оно искалось, интересно?

А собственно по алгориму: Это жадный алгоритм с очень простой эвристикой: добавляем точки по одной в список на позицию, минимизирующую длину пути. Такой простой алгоритм ожидаемо будет работать очень быстро. Но вот с оптимальностью ответа у него большие проблемы.

Во-первых, это известная эвристика с 1974 года: https://www2.isye.gatech.edu/~mgoetsch/cali/VEHICLE/TSP/TSP011__.HTM

При чем есть более сильная версия, где перебирается не только, куда воткнуть вершину, а и какую из них добавлять. Каждый раз выбирается локально лучший вариант. И это даже гарантирует точность 50% (максимум 2 раза длинее чем в оптимальном пути).

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

Edit: В литературе это называется cheapest insertion heuristic.