4551
правка
Задача коммивояжера с несколькими внутренними точками: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача коммивояжера с несколькими внутренними точками (посмотреть исходный код)
Версия от 10:40, 25 мая 2018
, 25 мая 2018→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Задача коммивояжера; поиск гамильтонова контура минимал…») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Специальным случаем задачи коммивояжера является так называемая евклидова задача коммивояжера, в которой города расположены на евклидовой плоскости, а расстояния представляют собой просто евклидовы расстояния. В свою очередь, специальным случаем евклидовой задачи коммивояжера является выпуклая евклидова задача коммивояжера, в которой города образуют выпуклую конфигурацию. Евклидова задача коммивояжера является NP-полной [4, 17], но ее выпуклый вариант решить довольно просто: объезд по границе выпуклой оболочки представляет собой кратчайший путь. В свете этих двух фактов возникает естественный вопрос: как влияет количество внутренних точек на сложность задачи? Здесь под внутренней точкой конечного множества точек P понимается точка из P, лежащая во внутренней области выпуклой оболочки P. Интуитивно можно предположить, что чем меньше внутренних точек, тем проще решить задачу. | Специальным случаем задачи коммивояжера является так называемая [[евклидова задача коммивояжера]], в которой города расположены на евклидовой плоскости, а расстояния представляют собой просто евклидовы расстояния. В свою очередь, специальным случаем евклидовой задачи коммивояжера является ''выпуклая евклидова задача коммивояжера'', в которой города образуют выпуклую конфигурацию. Евклидова задача коммивояжера является NP-полной [4, 17], но ее выпуклый вариант решить довольно просто: объезд по границе выпуклой оболочки представляет собой кратчайший путь. В свете этих двух фактов возникает естественный вопрос: как влияет количество внутренних точек на сложность задачи? Здесь под внутренней точкой конечного множества точек P понимается точка из P, лежащая во внутренней области выпуклой оболочки P. Интуитивно можно предположить, что чем меньше внутренних точек, тем проще решить задачу. | ||