TSP для полного ориентированного графа
Существует ли алгоритм полиномиального времени для задачи коммивояжера на полном ориентированном графе?
1 ответ
Решение
Навряд ли. Если бы он был, вы могли бы взять любой график и добавить все недостающие ребра с очень большим весом. Это позволило бы решить стандартную версию задачи, которая, как известно, является NP-трудной.