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

9

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

danmcardle
источник
2
Я уверен, что это произвольно. Только в редких случаях разрешить повторные города будет иметь какое-либо значение (никогда в метрической TSP). Так что проблемы вряд ли разные. Причина, вероятно, историческая.
Каролис Юоделе
8
Я слышал, что продавец продает действительно плохие продукты, и было бы неразумно встречать его старых покупателей :)
ssch

Ответы:

3

Неважно, как именно вы это определяете, потому что это просто способ моделирования реальной проблемы. В TSP у вас просто есть набор городов и стоимость проезда между каждой их парой. Это не исключает возможности того, что в реальной ситуации, которую вы моделируете, лучший маршрут между B и C может пройти через A. Если бы это было так, то да, маршрут, который смоделирован как ABCA в TSP, может очень хорошо, действительно нужно проехать A через дополнительное время на пути от B до C, но такие детали абстрагированы в модели TSP.

Дэвид Ричерби
источник
1
Правильный аргумент, но я хотел бы отметить, что TSP часто используется в реальных ситуациях. Прощается ли требование отсутствия повторения при реализации реальных приложений?
Danmcardle
@danmcardle Это зависит от приложения.
Том ван дер Занден
2

Я согласен, что ограничение выглядит странным, и для многих практических ситуаций оно не имеет значения. Как отметил Дэвид в своем ответе, если вы можете изменить моделирование самостоятельно, это не имеет большого значения. Но учитывая немодифицируемый экземпляр, это будет иметь значение, потому что общий TSP с этим ограничением не является аппроксимируемым в пределах любого постоянного фактора, в то время как ослабление ограничения на одно посещение, кажется, делает его аппроксимируемым в пределах фактора 2 (даже если это не метрика ). Если я ничего не пропустил, по стандартным аргументам, вы можете сначала построить минимальное связующее дерево (по стоимости, скажем, ), а затем посетить это дерево с техникой тура Эйлера. Очевидно, что общая стоимость вашего тура составляет 2 с (дважды за каждое преимущество). Противоречие, если существовал тур стоимостью менееc2c , тогда этот тур может быть использован для вывода MST стоимости меньше, чем c , что является противоречием.cc

Арно Кастейгтс
источник
1

Для любого тура с повторениями вы можете придумать более короткий тур, который не повторяет ни один город. Например, рассмотрим вида A X A Y , который посещает A дважды. Вы можете сделать ярлык во время второго посещения A , перейдя прямо от X к Y : A X Y .

AXAY,
AAИксY
AИксY,

ИксYAИксYAAAAA

Фактические алгоритмы для TSP могли бы иметь этот шаг «принятия ярлыков», например алгоритм Christofides. Смотрите, например, это описание или тот более короткий аккаунт .

Юваль Фильмус
источник
4
A,X1,,Xnd(A,Xi)=1d(xi,xj)=100i,jAX1AX2AAXnA2n+1AX1XnA100n98
Конечно, но (1) OP кажется заинтересованным в реальных приложениях TSP, которые являются метрическими, и (2) неметрические TSP не так интересны (так как это слишком сложно).
Юваль Фильмус
2
@YuvalFilmus TSP реального мира не являются необходимой метрикой. В некоторых случаях путешествие от А до Б займет больше времени, чем AC + CB, так как на дороге от А до Б. движение по дороге
Илья Газман
1
(A,В)AВAВ
0

Там нет общего ответа на это, кроме «люди не глупы». Они будут применять решение, которое соответствует их ситуации. Редко люди озабочены самой проблемой коммивояжера. В классическом случае Eveb, продавец из реальной жизни был бы более озабочен проблемой максимизации своего дохода в течение определенного периода времени в рамках определенного набора ограничений. В данном случае проблемы общее пройденное расстояние является лишь одним из множества различных факторов, влияющих на поиск оптимального ответа.

Х. Антонио Перес
источник
0

Если повторы разрешены, тогда вы просто исследуете все соединения X -> A -> Y, и если это короче, чем X -> Y, то вы заменяете длину X -> Y на длину X -> A -> Y, и решить полученную проблему с помощью стандартного алгоритма. Я думаю, что вы должны повторять процесс замены, пока не произойдет никаких изменений, потому что если вы найдете более короткое соединение X -> Y, это может означать, что теперь X -> Y -> Z короче, чем X -> Y.

Следите за тем, какие соединения вы изменили, пройдитесь по соединениям в решении, и если решение содержит X -> Y, тогда вы замените это на X -> A -> Y.

PS. Я думаю, что моя идея великолепна, но я не очень уверен, что она верна. Поскольку X -> A -> Y вместо X -> Y - это не просто ярлык, он также охватывает город A.

gnasher729
источник