Вопросы с тегом «traveling-salesman»

31
Как я могу проверить решение проблемы коммивояжера за полиномиальное время?

Таким образом, TSP (задача коммивояжера) проблема решения является NP полной . Но я не понимаю, как я могу проверить, что данное решение TSP на самом деле является оптимальным за полиномиальное время, учитывая, что нет способа найти оптимальное решение за полиномиальное время (потому что проблема...

23
Если я могу решить судоку, могу ли я решить задачу коммивояжера (TSP)? Если так, то как?

Допустим, есть такая программа, которая, если вы дадите частично заполненную судоку любого размера, даст вам соответствующую заполненную судоку. Можете ли вы рассматривать эту программу как черный ящик и использовать это для решения TSP? Я имею в виду, есть ли способ представить проблему TSP как...

21
Как можно проверить задачу коммивояжера за полиномиальное время?

Так что я понимаю идею, что решение проблемы определяется как Есть ли путь P такой, что стоимость ниже, чем C? и вы можете легко проверить это, проверив полученный вами путь. Однако что, если нет пути, который соответствует этим критериям? Как бы вы проверили ответ «нет», не решив проблему TSP с...

13
Каково оптимальное решение конкурса TSP Procter и Gamble 1962 года?

В 1962 году вы могли бы выиграть приз в размере 10 000 долларов (около 80 000 долларов в сегодняшних деньгах), если бы нашли решение евклидовой задачи коммивояжера, определенной в 33 городах. http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html Глядя на картинку, проблема кажется довольно...

11
Предлагая уточнения типов

На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...

9
Почему TSP не требует повторения городов?

Мне кажется странным, что TSP отрицает возможность повторных городов. Цель этого коммивояжера - поехать как можно быстрее и посетить все города, верно? Так что, если быстрее путешествовать по городу, в котором вы уже...