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

13

В 1962 году вы могли бы выиграть приз в размере 10 000 долларов (около 80 000 долларов в сегодняшних деньгах), если бы нашли решение евклидовой задачи коммивояжера, определенной в 33 городах.

http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html

Глядя на картинку, проблема кажется довольно простой. Однако я не смог найти более подробные ресурсы по этой проблеме.

Кто-нибудь знает некоторые подробности, такие как точные расстояния и оптимальное решение?

optimization traveling-salesman Мартин Дроздик
источник
2
Ах, 1960-е годы ... когда никто не сомневался в компаниях, рекламирующих свою продукцию, показывая полицейским, изводящим скудно одетых женщин.
Дэвид Ричерби

Ответы:

16

Полная информация содержится в «Роберте Л. Карге и Джеймсе Л. Томпсоне», «Эвристический подход к решению проблем коммивояжера» ( Management Science , 10 (2): 225–248, 1964). PDF доступен на сайтах JStor и Informs.org (оба платные). Это бумага, которая произвела оптимальный тур 10 861 миль. Он также включает таблицу полного расстояния, но я не буду воспроизводить это здесь, поскольку это слишком много печатать.

Решение также проиллюстрировано на странице 15 «Задачи коммивояжера » Дэвида Л. Эпплгейта, Роберта Э. Биксби, Васека Чватала и Уильяма Дж. Кука (издательство Принстонского университета, 2007). Вступление к этой книге, которое включает соответствующую страницу, свободно доступно от издателя .

Дэвид Ричерби
источник
«Более прямым подходом, конечно, было бы просто рассмотреть все возможные туры, но это число растет настолько быстро, что проверка их всех на наличие скромного экземпляра, скажем, 50 городов, выходит за рамки возможностей даже самых быстрых современных суперкомпьютеров. «. (от связанного Applegate, и др.)
Джейкоб Кралл