Задача коммивояжера с несколькими внутренними точками: различия между версиями

Специальным случаем задачи коммивояжера является так называемая [[евклидова задача коммивояжера]], в которой города расположены на евклидовой плоскости, а расстояния представляют собой просто евклидовы расстояния. В свою очередь, специальным случаем евклидовой задачи коммивояжера является ''выпуклая евклидова задача коммивояжера'', в которой города образуют выпуклую конфигурацию. Евклидова задача коммивояжера является NP-полной [4, 17], но ее выпуклый вариант решить довольно просто: объезд по границе выпуклой оболочки представляет собой кратчайший путь. В свете этих двух фактов возникает естественный вопрос: как влияет количество внутренних точек на сложность задачи? Здесь под внутренней точкой конечного множества точек P понимается точка из P, лежащая во внутренней области выпуклой оболочки P. Интуитивно можно предположить, что чем меньше внутренних точек, тем проще решить задачу.