В погоне за коммивояжером - In Pursuit of the Traveling Salesman

В поисках коммивояжера: математика на грани вычислений это книга о задача коммивояжера, к Уильям Дж. Кук, опубликованный в 2012 г. Princeton University Press, с переизданием в мягкой обложке в 2014 году.[1] Комитет по списку основных библиотек Математическая ассоциация Америки предложил включить его в библиотеки математики бакалавриата.[2]

Темы

В задача коммивояжера просит найти кратчайший циклический обход набора точек на плоскости или в более абстрактных математических пространствах, потому что проблема заключается в NP-жесткий, алгоритмы, которые принимают полиномиальное время вряд ли гарантированно найдут его оптимальное решение;[3] с другой стороны перебор из всех перестановки всегда точно решает проблему, но занимает слишком много времени, чтобы ее можно было использовать для всех, кроме самых мелких проблем.[4] Поиск компромисса между слишком быстрым и слишком медленным временем работы и разработка практической системы, которая может найти точное решение для больших экземпляров, поднимает сложные вопросы разработка алгоритмов,[5][3] которые привели к развитию «многих концепций и методов комбинаторной оптимизации».[3]

Вводная глава книги исследует пределы вычислений по этой задаче на основе задач из 49 пунктов, решенных вручную в середине 1950-х гг. Джордж Данциг, Д. Р. Фулкерсон, и Селмер М. Джонсон задаче с 85 900 баллами, оптимально решенной в 2006 г. Concorde TSP Solver, который Кук помог разработать. В следующих главах рассматривается ранняя история проблемы и связанных с ней проблем, включая Леонард Эйлер работает над Семь мостов Кенигсберга, Уильям Роуэн Гамильтон с Икозианская игра,[6] и Джулия Робинсон Впервые назвав проблему в 1949 году.[7] В другой главе описываются реальные приложения проблемы.[6] «от секвенирования генома и проектирования компьютерных процессоров до аранжировки музыки и охоты за планетами».[8] Рецензент Брайан Хейс цитирует "самое очаровательное открытие" книги как факт, что одним из тех реальных приложений было планирование маршрута для реального путешествия продавцы в начале 20 века.[4]

В главах с четвертой по седьмую, «суть книги», обсуждаются методы решения проблемы, исходя из эвристика и метаэвристика, релаксация линейного программирования, и режущие методы, вверх к ветвь и переплет метод, сочетающий эти методы и используемый Concorde. Следующие две главы также охватывают технические материалы, производительность компьютерных реализаций и Теория вычислительной сложности проблемы.[6][9]

Остальные главы больше ориентированы на человека и охватывают стратегии решения проблем людей и животных, а также включение решений TSP в произведения искусства. Джулиан Летбридж, Роберт Бош и другие.[6][10] В краткой заключительной итоговой главе предлагаются возможные будущие направления, включая возможность прогресса в P против проблемы NP.[6][11]

Аудитория

Книга предназначена для неспециализированной аудитории, избегает технических подробностей.[3][5][12] и написано «простым для понимания стилем».[13] Он включает в себя множество исторических отрывков, примеров, приложений, биографической информации и фотографий ключевых участников рассказа, что делает его доступным для читателей без математического образования.[10][12]

Несмотря на то что В погоне за коммивояжером не является учебником, рецензент Кристофер Томпсон предполагает, что некоторые из его материалов об использовании линейного программирования и о приложениях задачи «хорошо подходят для использования в классе», ссылаясь, в частности, на то, как он связывает несколько областей, включая числовой анализ, теория графов, алгоритм дизайн, логика, и статистика.[14]

Рецензент Стандартный вагон пишет, что «любой читатель, интересующийся комбинаторными алгоритмами, найдет в этой книге много ценного».[5] Ян Карел Ленстра и Давид Шмойс напишите, что «письмо расслабленное и интересное; презентация отличная. Нам очень понравилось это читать».[3] Рецензент Харис Азиз заключает: «Книга настоятельно рекомендуется всем, у кого математическое любопытство и интерес к развитию идей».[10]

Сопутствующие работы

Более подробную информацию о работе Кука с Concorde, подходящую для более серьезных исследователей проблемы и смежных тем, можно найти в более ранней книге Кука с Дэвид Эпплгейт, Роберт Э. Биксби и Вацлав Хваталь, Задача коммивояжера: вычислительное исследование (2007).[2][4][10]Другие книги по проблеме коммивояжера, также более технические, чем В погоне за коммивояжером, включают Задача коммивояжера: обзор комбинаторной оптимизации (Лоулер, Ленстра, Риннуи Кан и Шмойс, 1985) и Задача коммивояжера и ее варианты (Гутин и Пуннен, 2006).[10]

Рекомендации

  1. ^ Zbl  1301.00021
  2. ^ а б Гиттлман, Искусство (февраль 2012 г.), "Обзор В погоне за коммивояжером", Обзоры MAA, Математическая ассоциация Америки
  3. ^ а б c d е Ленстра, Ян Карел; Шмойс Давид (2016), «Обзор В погоне за коммивояжером", Уведомления Американского математического общества, 63 (6): 635–638, Дои:10.1090 / noti1397, МИСТЕР  3495222
  4. ^ а б c Хейс, Брайан (Май – июнь 2012 г.), «Математические путешествия» (обзор В погоне за коммивояжером)", Американский ученый, 100 (3): 252–254, JSTOR  23223051
  5. ^ а б c Вагон, Стан (2012), «Обзор В погоне за коммивояжером", Американский математический ежемесячный журнал, 119 (9): 808–811, Дои:10.4169 / amer.math.monthly.119.09.808, JSTOR  10.4169 / amer.math.monthly.119.09.808, МИСТЕР  3013985
  6. ^ а б c d е Вернер, Франк (2012), «Обзор В погоне за коммивояжером", Математические обзоры, МИСТЕР  2866515
  7. ^ Шуесслер, Дженнифер (15 марта 2012 г.), «Вилли Ломан, где ты?» (Обзор В погоне за коммивояжером)", Нью-Йорк Таймс
  8. ^ Бенкер, Ганс, "Обзор В погоне за коммивояжером", zbMATH, Zbl  1236.00007
  9. ^ Бальдаччи, Роберто (июль – август 2013 г.), "Обзор В погоне за коммивояжером", Интерфейсы, 43 (4): 391, JSTOR  23481217
  10. ^ а б c d е Азиз, Харис (август 2012 г.), "Обзор В погоне за коммивояжером", Новости ACM SIGACT, 43 (3): 51, Дои:10.1145/2421096.2421108
  11. ^ МакГонигал, Фрэнсис (январь 2012 г.), "Обзор В погоне за коммивояжером", IMA Book Reviews, Институт математики и ее приложений
  12. ^ а б Тирадо Домингес, Грегорио (ноябрь 2012 г.), "Обзор В погоне за коммивояжером", Обзоры EMS, Европейское математическое общество
  13. ^ Шефер, Роберт (январь 2012 г.), "Обзор В погоне за коммивояжером", Нью-Йоркский книжный журнал
  14. ^ Томпсон, Кристофер (февраль 2012 г.), "Обзор В погоне за коммивояжером", Конвергенция, Математическая ассоциация Америки, Дои:10.4169 / loci003821

дальнейшее чтение