Об одной эвристике для задачи коммивояжера на плоскости

Задача коммивояжера — это задача дискретной оптимизации, в которой необходимо определить кратчайший путь обхода всех вершин, посещая каждый только один раз. В общем случае, эта задача является NP-трудной и не имеет полиномиального алгоритма. Однако существуют специальные случаи, для которых можно найти оптимальное решение за полиномиальное время. В работе рассматривается специальный случай, когда все вершины расположены на евклидовой плоскости и образуют границу выпуклого многоугольника. На его основе разработана эвристика для задачи коммивояжера на плоскости, изучены границы ее применения. На основе полученной эвристики исследована возможность предсказания решения для случайного набора точек на плоскости.