В поисках коммивояжера
 Первое издание | |
| Автор | Уильям Дж. Кук |
|---|---|
| Язык | Английский |
| Предмет | коммивояжера Задача |
| Издатель | Издательство Принстонского университета |
Дата публикации | 2011 |
| ISBN | 9781400839599 |
В погоне за коммивояжером: Математика в пределах вычислений — книга о задаче коммивояжера , Уильяма Дж. Кука опубликованная в 2011 году издательством Princeton University Press , с переизданием в мягкой обложке в 2014 году. Математическая ассоциация Америки предложила включить его в библиотеки по математике для студентов. [1]
Темы
[ редактировать ]требует Задача коммивояжера найти кратчайший циклический обход набора точек на плоскости или в более абстрактных математических пространствах.Поскольку проблема является NP-сложной , алгоритмы, требующие полиномиального времени , вряд ли гарантированно найдут ее оптимальное решение; [2] с другой стороны, методом грубой силы перебор всех перестановок всегда точно решит проблему, но займет слишком много времени, чтобы его можно было использовать для решения всех задач, кроме самых маленьких. [3] Нахождение золотой середины между слишком быстрым и слишком медленным временем выполнения и разработка практической системы, способной найти точное решение для более крупных задач, поднимает сложные вопросы разработки алгоритмов . [4] [2] которые вызвали развитие «многих концепций и методов комбинаторной оптимизации». [2]
Во вступительной главе книги исследуются пределы вычислений в этой задаче: от задач с 49 точками, решенных вручную в середине 1950-х годов Джорджем Данцигом , Д. Р. Фулкерсоном и Сельмером М. Джонсоном, до задачи с 85 900 точками, оптимально решенной в 2006 году. с помощью Concorde TSP Solver , в разработке которого участвовал Кук. Следующие главы посвящены ранней истории проблемы и связанных с ней проблем, включая Леонарда Эйлера работу о семи мостах Кенигсберга , Уильяма Роуэна Гамильтона икосианскую игру , [5] и Джулия Робинсон, впервые обозначившая проблему в 1949 году. [6] Другая глава описывает реальное применение этой проблемы. [5] начиная «от секвенирования генома и разработки компьютерных процессоров до аранжировки музыки и охоты на планеты». [7] Рецензент Брайан Хейс называет «самым очаровательным открытием» книги тот факт, что одним из этих реальных приложений было планирование маршрутов для реальных коммивояжеров в начале 20 века. [3]
Главы с четвертой по седьмую, «ядро книги», обсуждают методы решения проблемы, начиная от эвристики и метаэвристики , релаксации линейного программирования и методов сечения , вплоть до метода ветвей и границ , который сочетает в себе эти методы и используется Конкорд. Следующие две главы также охватывают технический материал, касающийся производительности компьютерных реализаций и теории вычислительной сложности проблемы. [5] [8]
Остальные главы более ориентированы на человека и охватывают стратегии решения проблем людей и животных, а также включение решений TSP в произведения Джулиана Летбриджа , Роберта А. Боша и других. [5] [9] В краткой заключительной главе предлагаются возможные будущие направления, включая возможность прогресса в решении проблемы P и NP . [5] [10]
Аудитория
[ редактировать ]Книга предназначена для неспециализированной аудитории, избегает технических подробностей. [2] [4] [11] и написано «простым для понимания стилем». [12] Он включает в себя множество исторических отступлений, примеров, приложений, биографических сведений и фотографий ключевых игроков этой истории, что делает его доступным для читателей без математического образования. [9] [11]
Хотя «В погоне за коммивояжером» не является учебником, рецензент Кристофер Томпсон предполагает, что некоторые из его материалов по использованию линейного программирования и приложениям этой проблемы «хорошо подходят для использования в классе», ссылаясь, в частности, на то, как они связывает несколько областей, включая численный анализ , теорию графов , алгоритмов разработку , логику и статистику . [13]
Рецензент Стэн Вагон пишет, что «любой читатель, интересующийся комбинаторными алгоритмами, найдет в этой книге много ценного». [4] Ян Карел Ленстра и Дэвид Шмойс пишут: «Написано непринужденно и занимательно, презентация отличная. Нам очень понравилось читать». [2] А рецензент Харис Азиз заключает: «Эта книга настоятельно рекомендуется всем, кто проявляет математическое любопытство и интерес кразвитие идей». [9]
Связанные работы
[ редактировать ]Более подробную информацию о работе Кука с «Конкордом», подходящую для более серьезных исследователей проблемы и смежных тем, можно найти в более ранней книге Кука с Дэвидом Эпплгейтом , Робертом Э. Биксби. и Вацлав Хватал , Проблема коммивояжера: вычислительное исследование (2007). [1] [3] [9] Другие книги по проблеме коммивояжера, также более технические, чем « В погоне за коммивояжером» , включают «Проблема коммивояжера: экскурсия по комбинаторной оптимизации» (Лоулер, Ленстра, Риннуй Кан и Шмойс, 1985) и «Задача коммивояжера». и его вариации (Гутин и Пуннен, 2006). [9]
Ссылки
[ редактировать ]- ^ Jump up to: а б Гиттлман, Арт (февраль 2012 г.), «Обзор книги « В погоне за коммивояжером » , MAA Reviews , Математическая ассоциация Америки
- ^ Jump up to: а б с д и Ленстра, Ян Карел ; Шмойс, Дэвид (2016), «Обзор книги « В погоне за коммивояжером », Уведомления Американского математического общества , 63 (6): 635–638, doi : 10.1090/noti1397 , MR 3495222
- ^ Jump up to: а б с Хейс, Брайан (май – июнь 2012 г.), «Математические путешествия (обзор книги «В погоне за коммивояжером »)», American Scientist , 100 (3): 252–254, JSTOR 23223051
- ^ Jump up to: а б с Вагон, Стэн (2012), «Обзор книги « В поисках коммивояжера »», American Mathematical Monthly , 119 (9): 808–811, doi : 10.4169/amer.math.monthly.119.09.808 , JSTOR 10.4169/amer. math.monthly.119.09.808 , MR 3013985
- ^ Jump up to: а б с д и Вернер, Франк (2012), «Обзор книги « В погоне за коммивояжером », Mathematical Reviews , MR 2866515
- ^ Шюсслер, Дженнифер (15 марта 2012 г.), «Вилли Ломан, где ты? (Рецензия на книгу « В погоне за коммивояжером »)» , The New York Times
- ^ Бенкер, Ганс, «Рецензия на книгу « В погоне за коммивояжером », zbMATH , Zbl 1236.00007
- ^ Бальдаччи, Роберто (июль – август 2013 г.), «Обзор книги « В погоне за коммивояжером », Interfaces , 43 (4): 391, JSTOR 23481217
- ^ Jump up to: а б с д и Азиз, Харис (август 2012 г.), «Обзор книги « В погоне за коммивояжером », ACM SIGACT News , 43 (3): 51, doi : 10.1145/2421096.2421108
- ^ МакГонигал, Фрэнсис (январь 2012 г.), «Обзор книги «В погоне за коммивояжером » , Рецензии на книги IMA , Институт математики и ее приложений
- ^ Jump up to: а б Тирадо Домингес, Грегорио (ноябрь 2012 г.), «Обзор книги « В погоне за коммивояжером » , EMS Reviews , Европейское математическое общество
- ^ Шефер, Роберт (январь 2012 г.), «Обзор книги « В погоне за коммивояжером » , New York Journal of Books
- ^ Томпсон, Кристофер (февраль 2012 г.), «Обзор книги « В погоне за коммивояжером », Convergence , Математическая ассоциация Америки , doi : 10.4169/loci003821
Дальнейшее чтение
[ редактировать ]- Элленберг, Джордан (10 марта 2012 г.), «Нечеткий путь может быть кратчайшим (рецензия на книгу « В погоне за коммивояжером »)» , The Wall Street Journal
- МакЛеми, Скотт (21 марта 2012 г.), «Алгоритм продавца (рецензия на книгу « В погоне за коммивояжером »)» , Inside Higher Education