Евклидова задача коммивояжера: различия между версиями

Рассматриваются NP-полные задачи геометрической оптимизации – такие как евклидова [[задача коммивояжера]] и евклидова задача нахождения [[дерево Штейнера|дерева Штейнера]]. Эти задачи являются геометрическими вариантами стандартных задач [[оптимизация графа|оптимизации графа]]; ограничение входных экземпляров геометрическим или евклидовым случаем встречается во множестве приложений ([1, 2]). Далее будет в основном рассматриваться евклидова задача коммивояжера.