Чем важна в повседневной жизни задача коммивояжера

N+1Наука

«Это база: Зачем нужна математика в повседневной жизни»

Чем важна задача коммивояжера

3a798e86772cafd80ce3e16698acfa04.png

В основе современных технологий лежат проверенные временем математические концепции. К примеру, машинное обучение использует матрицы и графы, а компьютерная анимация — пространство форм. В книге «Это база: Зачем нужна математика в повседневной жизни» (издательство «Альпина нон-фикшн»), переведенной на русский язык Натальей Лисовой, популяризатор науки Иэн Стюарт рассказывает, как она применяется в политике, юриспруденции, медицине, информационной безопасности, киноиндустрии и других сферах. Предлагаем вам ознакомиться с фрагментом о попытках решить и практическом применении задачи коммивояжера.

Пусть голубь ведет автобус

Водителя автобуса может беспокоить, что голубь не способен безопасно вести автобус. Еще больше его может беспокоить то, что голубь не сумеет выбрать маршрут, позволяющий подобрать всех пассажиров на остановках города.

Бретт Гибсон, Мэттью Уилкинсон и Дебби Келли. Animal cognition

Мо Виллемс рисовал забавные картинки с трехлетнего возраста. Опасаясь, что взрослые могут хвалить его не от чистого сердца, он начал писать смешные истории. Ему казалось, что фальшивый смех легче распознать. В 1993 году он присоединился к команде сценаристов и мультипликаторов классической «Улицы Сезам», что принесло ему за 10 лет шесть премий «Эмми». Главным героем его детского мультсериала «Баран в большом городе» стал баран по имени Баран, чья идиллическая жизнь на ферме рушится, когда тайная военная организация начинает гоняться за ним и ловить для создания лучевой пушки на бараньей силе. Первым опытом Виллемса в жанре детской книги стала книжка «Не позволяйте голубю вести автобус!», продолжавшая тему животных. Мультфильм по этой книге принес автору медаль Карнеги, а сама книга — премию Калдекотта, которую получают те, кто попадает в шорт-лист претендентов на медаль Калдекотта. Главный герой книги — голубь — использует все возможное и невозможное, пытаясь убедить читателя, что ему можно доверить управление автобусом, когда обычному водителю внезапно приходится покинуть транспортное средство.

В 2012 году книга Виллемса получила неожиданное научное продолжение — солидную статью в уважаемом журнале Animal Cognition, авторами которой стали заслуживающие доверия исследователи Бретт Гибсон, Мэттью Уилкинсон и Дебби Келли. Они экспериментально доказали, что голуби способны находить решения, близкие к оптимальным, для простых случаев известной математической диковинки — задачи коммивояжера. Их статья называлась «Позвольте голубю вести автобус: голуби способны планировать маршруты в помещении».

И пусть никто не говорит, что у ученых нет чувства юмора. Или что остроумные заголовки не помогают добиться популярности.

Задача коммивояжера — не просто любопытная диковинка. Это хороший пример целого класса задач, имеющих громадное практическое значение и известных как задачи комбинаторной оптимизации. У математиков есть привычка формулировать глубокие и значительные вопросы тривиальным на первый взгляд языком. Американские конгрессмены осудили напрасное расходование бюджетных денег на теорию узлов, не понимая, что эта область математики принципиально важна для понимания топологии малых размерностей, которая используется в теории ДНК и квантовой теории. Основные методы топологии включают в себя теорему о причесывании ежика и теорему о бутерброде, так что, я полагаю, мы сами на это напросились, но дело не только в нас. Я не осуждаю тех, кто чего-то не знает, — с каждым случается, — но почему бы этим людям просто не спросить?

Как бы то ни было, та показательная чепуха, которая вдохновила меня на эту главу, берет свое начало в одной полезной книге для — как вы, наверное, уже догадались — коммивояжеров. Тех, что обходили дома и предлагали свой товар. Я еще помню их, даже если вы не помните. Они часто продавали пылесосы. Как любые разумные деловые люди, немецкие коммивояжеры в 1832 году (а в те времена все они, конечно, были мужчинами) очень трепетно относились к эффективности использования своего времени и снижению расходов. К счастью, помощь всегда была под рукой в виде руководства: «Коммивояжер. Каким ему следует быть и что ему следует делать, чтобы получать заказы и быть уверенным в успехе своего дела. Советы старого коммивояжера» (Der Handlungsreisende — wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiss zu sein — von einem alten Commis-Voyageur). Этот пожилой странствующий торговец указывал, что:

Бизнес приводит коммивояжера сегодня сюда, завтра туда, и ни про какие маршруты невозможно точно сказать, что они годятся для всех случаев. Однако иногда рациональная организация маршрута позволяет сэкономить столько времени, что полезно познакомиться с правилами его определения... Главная цель всегда состоит в том, чтобы посетить как можно больше мест, не возвращаясь в них второй раз.

Руководство не предлагало математических принципов решения этой задачи, а приводило примеры пяти предположительно оптимальных маршрутов по Германии (один из них проходил через территорию Швейцарии). Большинство маршрутов содержали подциклы, предусматривавшие посещение одних и тех же мест дважды, что вполне естественно, если вы останавливаетесь на ночь в гостинице, а днем объезжаете окрестности. Но в одном из маршрутов не было повторных визитов. Современное решение этой задачи показывает, что предложенный руководством ответ достаточно хорош, как видно на рисунке.

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

1993 год 1993 год

«Шоковая терапия» – так принято называть реформы, идущие весь 1993 год

Esquire
10 признаков того, что вы недостаточно заботитесь о себе 10 признаков того, что вы недостаточно заботитесь о себе

Сигналы, которыми организм дает понять, что он на грани истощения

Psychologies
Восемь мифов о правильной еде Восемь мифов о правильной еде

Давно опровергнутые, но устоявшиеся представления о правильной еде

Здоровье
Жаркая погода может убить вас: как этого избежать Жаркая погода может убить вас: как этого избежать

Перегрев может вызвать серьезные проблемы со здоровьем: как его избежать?

ТехИнсайдер
Идти ли к психологу? 6 поводов для сомнений Идти ли к психологу? 6 поводов для сомнений

Какие страхи и предубеждения мешают обратиться к психологу?

Psychologies
Рационализаторское предложение или изобретение: что регистрировать? Рационализаторское предложение или изобретение: что регистрировать?

Основные преимущества осуществления рационализаторской деятельности

Наука и техника
Сколько можно пить за рулем в разных странах Сколько можно пить за рулем в разных странах

Где вообще нельзя, а где можно немного выпить за рулем?

Maxim
Она — легенда: как Сьюзен Войджицки стала ролевой моделью для многих женщин в бизнесе Она — легенда: как Сьюзен Войджицки стала ролевой моделью для многих женщин в бизнесе

Почему Войджицки была не просто легендой в технологической индустрии

Forbes
Мария Орлова: «Чтение – это в первую очередь удовольствие» Мария Орлова: «Чтение – это в первую очередь удовольствие»

Как привить ребенку любовь к чтению – не обязательно расти на классике

Grazia
Вперед и вверх: как начать заниматься скалолазанием и куда пойти Вперед и вверх: как начать заниматься скалолазанием и куда пойти

Быстрый гид по скалолазанию для начинающих

Правила жизни
«Включение в систему» «Включение в систему»

Как немецкий народ приобщали к обязательной для всех нацистской идеологии

Дилетант
Какой смысл мы вкладываем в слово «душнила»: 4 объяснения Какой смысл мы вкладываем в слово «душнила»: 4 объяснения

Зачем нужен термин «душнила»? Почему мы его используем?

Psychologies
Целительная сила «убойного» цветка Целительная сила «убойного» цветка

За какие целебные свойства ценят зверобой?

Наука и жизнь
Снижение самооценки и панические атаки: чем опасно позитивное мышление Снижение самооценки и панические атаки: чем опасно позитивное мышление

Стоит ли придерживаться позитивного мышления? Отвечает гештальт-терапевт

Psychologies
«В чем подвох?»: почему мы ищем скрытый смысл там, где его нет «В чем подвох?»: почему мы ищем скрытый смысл там, где его нет

Почему мы ищем подвох там, где он даже не предполагался?

Psychologies
Заедки, то есть вкусняшки Заедки, то есть вкусняшки

Где рассказывают о русских сладостях — заедках, или верхосытках?

КАНТРИ Русская азбука
Энтузиазм и отвага Энтузиазм и отвага

Секрет петербургского ресторанного феномена — это энтузиазм его создателей

Монокль
Куркума и зеленый чай — одни из самых полезных пищевых добавок, из-за которых люди попадают в больницы Куркума и зеленый чай — одни из самых полезных пищевых добавок, из-за которых люди попадают в больницы

Насколько вреден прием популярных растительных добавок, помогающих похудеть?

ТехИнсайдер
Спорт — наш: как сериал Евгения Стычкина «Игры» рассказывает об Олимпиаде-80 Спорт — наш: как сериал Евгения Стычкина «Игры» рассказывает об Олимпиаде-80

Сериал «Игры»: амбивалентная история об Олимпиаде-80

Forbes
Синхронное плавание Синхронное плавание

Владимир Кристовский и его жена Ольга о вдохновении для всех, кто его ищет

Psychologies
Эксперты выявили семь странных форм поведения, связанных с высоким IQ Эксперты выявили семь странных форм поведения, связанных с высоким IQ

Привычки и стиль жизни, которые связывают с гениальностью

ТехИнсайдер
10 вредных советов, которые помогут не дожить до старости 10 вредных советов, которые помогут не дожить до старости

Халатное отношение к собственному здоровью способно сильно укоротить вашу жизнь

Psychologies
Жизнь без слез! Что делать, если постоянно хочется плакать: 10 советов психолога Жизнь без слез! Что делать, если постоянно хочется плакать: 10 советов психолога

Разбираемся в ситуации постоянных слез без причины вместе с психологом

Лиза
Автоэксперт Пономарев рассказал, как проверить наличие фреона в автокондиционере Автоэксперт Пономарев рассказал, как проверить наличие фреона в автокондиционере

Как правильно обращаться с кондиционером, чтобы продлить его ресурс?

ТехИнсайдер
Остерегаться в лесу: ученый назвал самые опасные дикие растения России Остерегаться в лесу: ученый назвал самые опасные дикие растения России

Что нужно учитывать при заготовке травяных сборов

ТехИнсайдер
Андрей Себрант: «В карьере нет заранее известной конечной точки» Андрей Себрант: «В карьере нет заранее известной конечной точки»

Как технологии повлияли на карьерное развитие в IT и где искать предсказуемость

РБК
США запутались в ключах от Белого дома США запутались в ключах от Белого дома

Замена кандидата в президенты оживила предвыборную борьбу в США

Монокль
Ангелы прилетели Ангелы прилетели

Мастер-класс по самодельным ангелам, дарящим ощущение праздника и чудес

КАНТРИ Русская азбука
Рычит, но не испепеляет: каким получился второй сезон «Дома Дракона»? Рычит, но не испепеляет: каким получился второй сезон «Дома Дракона»?

Второй сезон «Дома Дракона»: каким он получился и как обманул ожидания фанатов

Правила жизни
Екатерина Гусева: «Чем больше отдаю душевных сил, тем больше получаю солнечной энергии!» Екатерина Гусева: «Чем больше отдаю душевных сил, тем больше получаю солнечной энергии!»

Я чувствую, что наполнена зрительской благодарностью и любовью

Караван историй
Открыть в приложении