#graph #traveling-salesman
#График #коммивояжер
Вопрос:
Существует ли алгоритм полиномиального времени для задачи коммивояжера на полном ориентированном графе?
Ответ №1:
Маловероятно. Если бы он был, вы могли бы взять любой график и добавить все недостающие ребра с очень большим весом. Это позволило бы решить стандартную версию задачи, которая, как известно, является NP-сложной.