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

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

Темы

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

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

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

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

Аудитория

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

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

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

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

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

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

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

• Элленберг, Джордан (10 марта 2012 г.), «Нечеткий путь может быть кратчайшим (обзор книги« В погоне за странствующим продавцом » )» , The Wall Street Journal
• МакЛеми, Скотт (21 марта 2012 г.), «Алгоритм продавца (обзор книги« В погоне за странствующим продавцом » )» , Inside Higher Education