Jakie jest optymalne rozwiązanie konkursu TSP Procter and Gamble z 1962 roku?

13

W 1962 r. Możesz wygrać nagrodę w wysokości 10 000 USD (około 80 000 USD w dzisiejszych pieniądzach), jeśli znajdziesz rozwiązanie problemu euklidesowego sprzedawcy podróżującego zdefiniowanego w 33 miastach.

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

Patrząc na zdjęcie, problem wydaje się dość łatwy. Nie udało mi się jednak znaleźć bardziej szczegółowych zasobów na temat problemu.

Czy ktoś wie więcej szczegółów, takich jak dokładne odległości i optymalne rozwiązanie?

optimization traveling-salesman Martin Drozdik
źródło
2
Ach, lata sześćdziesiąte ... kiedy nikt nie mrugnął powiekami do firm reklamujących swoje produkty, pokazując policjantów nękających skąpo odzianych kobiet.
David Richerby

Odpowiedzi:

16

Pełne szczegóły znajdują się w Robert L. Karg i James L. Thompson, Heurystyczne podejście do rozwiązywania problemów podróżujących sprzedawców ( Management Science , 10 (2): 225–248, 1964). Plik PDF jest dostępny w JStor i Informs.org (oba paywalled). To jest papier, który wyprodukował optymalną trasę 10861 mil. Zawiera także tabelę pełnego dystansu, ale nie będę jej tutaj kopiować, ponieważ jest to zbyt dużo pisania.

Rozwiązanie zostało również zilustrowane na stronie 15 Problemu podróżującego sprzedawcy David L. Applegate, Robert E. Bixby, Vasek Chvátal i William J. Cook (Princeton University Press, 2007). Wprowadzenie do tej książki, która zawiera odpowiednią stronę, jest bezpłatnie dostępne u wydawcy .

David Richerby
źródło
„Bardziej bezpośrednim podejściem byłoby oczywiście rozważenie wszystkich możliwych tras, ale liczba ta rośnie tak szybko, że sprawdzenie ich wszystkich w przypadku skromnych rozmiarów, powiedzmy 50 miast, znacznie przekracza możliwości nawet najszybszych współczesnych superkomputerów . ” (z połączonego Applegate i in.)
Jacob Krall