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

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). Этот пожилой странствующий торговец указывал, что:

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

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

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

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

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

На бурятской траве. Как россияне сделали джин, получивший награду на конкурсе в Европе На бурятской траве. Как россияне сделали джин, получивший награду на конкурсе в Европе

Как бизнесмен и чайный мастер сделали джин Gintl

СНОБ
Ощущение вкуса Ощущение вкуса

На что мы смотрим, когда выбираем блюдо или напиток?

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

Как мысленная уловка поможет избавиться от проблем и достичь целей

РБК
Главный экспонат Главный экспонат

Автомобили, на которых люди станут ездить (и даже летать) в ближайшее время

ТехИнсайдер
Придумал ценники, скидки и супермаркеты: история «короля шоппинга» Фрэнка Вулворта Придумал ценники, скидки и супермаркеты: история «короля шоппинга» Фрэнка Вулворта

История человека, который подарил миру удобный и выгодный шоппинг

ТехИнсайдер
Россия по-итальянски Россия по-итальянски

Все подробности жизни и «невероятных приключений итальянца в России»

2Xplore
Наш человек! Наш человек!

11 звезд Голливуда с русскими корнями

Лиза
Что сделать, чтобы мужчина был с вами счастлив и дорожил отношениями Что сделать, чтобы мужчина был с вами счастлив и дорожил отношениями

Глава из книги Виктора Богомолова «Чего хотят мужчины»

Psychologies
«В кадровой политике мы применяем системный подход» «В кадровой политике мы применяем системный подход»

Как в Сахалинской области решается вопрос кадрового дефицита

РБК
5 способов «застраховаться» от развода 5 способов «застраховаться» от развода

Что необходимо делать супругам, чтобы гарантированно укрепить свой брак?

Psychologies
«Никто не идеален»: 5 шагов, чтобы избавиться от недостатков «Никто не идеален»: 5 шагов, чтобы избавиться от недостатков

Признание своих недостатков — первый шаг к изменениям

Psychologies
Полярные сияния будут возникать не только на крайнем севере! Вот как вспышки на Солнце влияют на Землю Полярные сияния будут возникать не только на крайнем севере! Вот как вспышки на Солнце влияют на Землю

Как солнечная активность влияет на Землю и вызывает полярные сияния

ТехИнсайдер
Что делать, чтобы на одежде перестали образовываться катышки: эти трюки должен знать каждый Что делать, чтобы на одежде перестали образовываться катышки: эти трюки должен знать каждый

Правильный уход за вещами поможет предотвратить появление катышек

ТехИнсайдер
Обстрелы, дроны, теракты: как поддержать себя, когда близкие в опасности? Советует кризисный психолог Обстрелы, дроны, теракты: как поддержать себя, когда близкие в опасности? Советует кризисный психолог

Как справиться с тревогой и беспокойством?

Psychologies
«Болячки прикладывали прямо к экрану»: псевдоцелители и «натуропаты» в новейшей истории России «Болячки прикладывали прямо к экрану»: псевдоцелители и «натуропаты» в новейшей истории России

«Целители», которые обещали людям из СССР лекарство от всех болезней

Правила жизни
Кто предупрежден, тот вооружен Кто предупрежден, тот вооружен

Что делать, если родители или друзья пытаются давить на нас в своих интересах?

Psychologies
Дело сдвинулось: новый общественный электротранспорт Калининграда Дело сдвинулось: новый общественный электротранспорт Калининграда

Любопытно, какие именно троллейбусы приедут в Калининград?

ФедералПресс
8 фраз, которые вредно говорить детям 8 фраз, которые вредно говорить детям

Фразы, которые не оказывают воспитательного эффекта и портят отношения с детьми

Psychologies
Лисички: почему самый хитрый гриб никогда не бывает червивым Лисички: почему самый хитрый гриб никогда не бывает червивым

Что такого опасного содержится в лисичках, что червяки отказываются их есть?

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

У нового робота FIgure  кисти рук с шестнадцатью степенями свободы

N+1
Эксперт рассказал, как меньше пьянеть! Факты о толерантности к алкоголю Эксперт рассказал, как меньше пьянеть! Факты о толерантности к алкоголю

Почему одни люди могут выпить больше других?

ТехИнсайдер
Живейшее из искусств Живейшее из искусств

«Комната 999»: кинорежиссеры рассуждают о судьбе кино

Weekend
Жостово: вaм букетик! Жостово: вaм букетик!

Жостовский расписной поднос — ровесник восстания декабристов

КАНТРИ Русская азбука
«Завышенная цена стала рыночной»: почему дорожает аренда элитной недвижимости «Завышенная цена стала рыночной»: почему дорожает аренда элитной недвижимости

С чем связан рост арендных ставок на элитное жилье в Москве

СНОБ
Просто добавь воды Просто добавь воды

Как восполнить недостаток влаги в коже

Лиза
Секс, стена и Достоевский Секс, стена и Достоевский

Что может сделать русская литература со стремительно взрослеющей девушкой

Weekend
«Не терпя лукавыя бесовские крамолы» «Не терпя лукавыя бесовские крамолы»

«И пришел из Орды, и сел на великокняжеском престоле»

Дилетант
Избавиться от травмы: как, зачем и что будет после? Избавиться от травмы: как, зачем и что будет после?

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

Psychologies
Приписываемые епископу Теодомиро останки действительно принадлежали средневековому мужчине Приписываемые епископу Теодомиро останки действительно принадлежали средневековому мужчине

Ученые исследовали останки, которые могли принадлежать епископу Теодомиро

N+1
Чужбина больше не интересует: как менялось мнение россиян об эмиграции Чужбина больше не интересует: как менялось мнение россиян об эмиграции

В России рекордно снизилось число граждан, желающих попытать счастье за рубежом

ФедералПресс
Открыть в приложении