Мне кажется странным, что TSP отрицает возможность повторных городов. Цель этого коммивояжера - поехать как можно быстрее и посетить все города, верно? Так что, если быстрее путешествовать по городу, в котором вы уже были?
terminology
traveling-salesman
danmcardle
источник
источник
Ответы:
Неважно, как именно вы это определяете, потому что это просто способ моделирования реальной проблемы. В TSP у вас просто есть набор городов и стоимость проезда между каждой их парой. Это не исключает возможности того, что в реальной ситуации, которую вы моделируете, лучший маршрут между B и C может пройти через A. Если бы это было так, то да, маршрут, который смоделирован как ABCA в TSP, может очень хорошо, действительно нужно проехать A через дополнительное время на пути от B до C, но такие детали абстрагированы в модели TSP.
источник
Я согласен, что ограничение выглядит странным, и для многих практических ситуаций оно не имеет значения. Как отметил Дэвид в своем ответе, если вы можете изменить моделирование самостоятельно, это не имеет большого значения. Но учитывая немодифицируемый экземпляр, это будет иметь значение, потому что общий TSP с этим ограничением не является аппроксимируемым в пределах любого постоянного фактора, в то время как ослабление ограничения на одно посещение, кажется, делает его аппроксимируемым в пределах фактора 2 (даже если это не метрика ). Если я ничего не пропустил, по стандартным аргументам, вы можете сначала построить минимальное связующее дерево (по стоимости, скажем, ), а затем посетить это дерево с техникой тура Эйлера. Очевидно, что общая стоимость вашего тура составляет 2 с (дважды за каждое преимущество). Противоречие, если существовал тур стоимостью менееc 2c , тогда этот тур может быть использован для вывода MST стоимости меньше, чем c , что является противоречием.c c
источник
Для любого тура с повторениями вы можете придумать более короткий тур, который не повторяет ни один город. Например, рассмотрим вида ⋯ → A → ⋯ → X → A → Y → ⋯ , который посещает A дважды. Вы можете сделать ярлык во время второго посещения A , перейдя прямо от X к Y : ⋯ → A → ⋯ → X → Y → ⋯ .
Фактические алгоритмы для TSP могли бы иметь этот шаг «принятия ярлыков», например алгоритм Christofides. Смотрите, например, это описание или тот более короткий аккаунт .
источник
Там нет общего ответа на это, кроме «люди не глупы». Они будут применять решение, которое соответствует их ситуации. Редко люди озабочены самой проблемой коммивояжера. В классическом случае Eveb, продавец из реальной жизни был бы более озабочен проблемой максимизации своего дохода в течение определенного периода времени в рамках определенного набора ограничений. В данном случае проблемы общее пройденное расстояние является лишь одним из множества различных факторов, влияющих на поиск оптимального ответа.
источник
Если повторы разрешены, тогда вы просто исследуете все соединения 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.
источник