Какой алгоритм приближенного решения Задачи Комивояжера выбрать для регулярных точек?

Question

[roman_123456]

Нужно проложить кратчайший путь через точки. Точки расположены очень хорошо, по сетке, как на рисунке.
Т.е. человек сразу проложит кратчайший путь.
Алгоритм Литтла не очень прокладывает путь.
Есть ли лучший алгоритм для такого случая?

Answer 1

[Wataru]

Раз человек легко прокладывает путь, то его можно просто захардкодить.

Очевидно, что шаг от одной вершины к следующей будет не меньше 1, а значит кратчайший путь - тот, который ходит только горизонтально и вертикально. Если сетка не квадратная, то пусть ровно с 2m более длинных вертикаьных ребер будет мнимальным, потому что путь любую горизонтальнюу линию должен будет пересечь хотя бы в 2 точках.

Ну и нарисуйте на бумаге 4 случая - когда высота и ширина четные или нечетные.