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

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

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

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

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

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

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

Что такое «думскроллинг» и чем он опасен каждому россиянину Что такое «думскроллинг» и чем он опасен каждому россиянину

Хорошая новость для тех, кто любит плохие новости: думскроллинг лечится

Maxim
Вот где ответ Вот где ответ

Вероника Сидорова: как меняются отношения родителей и детей в современном мире

Grazia
Семь неожиданных фактов о Лавкрафте Семь неожиданных фактов о Лавкрафте

Неожиданные факты об «отце монстров» Говарде Лавкрафтов

Maxim
В поиске новых смыслов: почему на фоне мирового кризиса философия становится «модной» В поиске новых смыслов: почему на фоне мирового кризиса философия становится «модной»

Как философы могут предложить более глубокое понимание себя и мира

Forbes
Туристы хотят на Трансмонгольскую железную дорогу! И вот почему это интересно Туристы хотят на Трансмонгольскую железную дорогу! И вот почему это интересно

Чем примечательна Трансмонгольская железная дорога?

ТехИнсайдер
Психолог рассказал, как формируется и лечится ПТСР Психолог рассказал, как формируется и лечится ПТСР

Что такое ПТСР? Почему оно возникает? Можно ли его вылечить?

Psychologies
Шпана, гопники, хулиганы: как кинематограф работает с темой «пацанства» Шпана, гопники, хулиганы: как кинематограф работает с темой «пацанства»

Как с темой «пацанства» работает кинематограф и какие этапы эволюции она прошла

Правила жизни
Как культурно выпроводить загостившуюся свекровь: 3 совета невесткам Как культурно выпроводить загостившуюся свекровь: 3 совета невесткам

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

Psychologies
Инвазивные змеи на Гуаме не смогли проглотить половину убитых птиц Инвазивные змеи на Гуаме не смогли проглотить половину убитых птиц

Многие змеи регулярно охотятся на слишком крупную для проглатывания добычу

N+1
Медиатор: кто это и чем занимается Медиатор: кто это и чем занимается

В каких ситуациях медиатор незаменим и чем он отличается от психолога?

Psychologies
Фьюзинг: дедовский метод Фьюзинг: дедовский метод

Процесс создания красоты, «фьюзинг», — давняя и довольно традиционная технология

КАНТРИ Русская азбука
Летняя кухня. Идеи обустройства и практичные подсказки для дачников Летняя кухня. Идеи обустройства и практичные подсказки для дачников

Почему так важно позаботиться о правильном устройстве летней кухни

Лиза
Ловушки отношений без любви. Как выйти из неудачного брака Ловушки отношений без любви. Как выйти из неудачного брака

Катерина Мурашова: Как уйти от мужа, который не дает развод

СНОБ
Чувствовал себя лишним: Джинён из GOT7 едва не покинул группу на пике ее популярности Чувствовал себя лишним: Джинён из GOT7 едва не покинул группу на пике ее популярности

Пак Чинён, или Джинён, всерьез рассматривал вариант покинуть k-pop сцену

VOICE
Как формируется мнение человека о самом себе. Отрывок из книги психиатра Как формируется мнение человека о самом себе. Отрывок из книги психиатра

Отрывок из книги психиатра и нейробиолога Грегори Бернса «Иллюзия себя»

СНОБ
5 признаков, что ваш брак под угрозой 5 признаков, что ваш брак под угрозой

Как понять, какие перспективы у вашего союза?

Psychologies
Ингибирование гистондеацетилазы 3 улучшило реконсолидацию памяти у старых мышей Ингибирование гистондеацетилазы 3 улучшило реконсолидацию памяти у старых мышей

Фермент гистондеацетилаза 3 участвует в реконсолидации памяти

N+1
Запоздалый поклон шевалье де Ламарку Запоздалый поклон шевалье де Ламарку

Шевалье де Ламарк — одна из самых противоречивых фигур за всю историю биологии

Знание – сила
Что произойдет, если бросить пакет с мусором в вулкан? Что произойдет, если бросить пакет с мусором в вулкан?

Смогут ли вулканы «переварить» весь человеческий мусор?

ТехИнсайдер
Вавилонская башня: самые сложные и самые простые языки для изучения Вавилонская башня: самые сложные и самые простые языки для изучения

Почему одни языки легче выучить, чем другие?

ТехИнсайдер
Предметный разговор Предметный разговор

Искусствовед Софья Симакова рассказывает о феномене коллекционного дизайна

Правила жизни
Мамина диета Мамина диета

Ответы на самые популярные вопросы по питанию, которые волнуют будущих мамочек

Лиза
Танцуй, танцуй! Танцуй, танцуй!

Танцы — это не только красиво, но еще и полезно для здоровья

ЖАРА Magazine
Комариная охота: как выбрать фумигатор и облегчить себе жизнь? Комариная охота: как выбрать фумигатор и облегчить себе жизнь?

Что нужно учитывать при выборе фумигатора?

ТехИнсайдер
От модели до CEO: как Брук Шилдс основала собственный бьюти-бренд для зрелых женщин От модели до CEO: как Брук Шилдс основала собственный бьюти-бренд для зрелых женщин

Брук Шилдс о том, как она решилась начать новую карьеру — в бизнесе

Forbes
Отдел замученных поэтесс: самые популярные новые женские музыкальные альбомы Отдел замученных поэтесс: самые популярные новые женские музыкальные альбомы

Женские музыкальные альбомы, которые объединили все новые тренды в поп-музыке

Forbes
Чудеса системы Сатурна: два безумных океана Чудеса системы Сатурна: два безумных океана

Система Сатурна – настоящее собрание диковин и чудес

Наука и техника
Играть по правилам и без Играть по правилам и без

Где та грань в хитрости, которую не стоит переступать?

Psychologies
Никто не может трогать эту древнюю лестницу в храме Гроба Господня! Узнайте почему Никто не может трогать эту древнюю лестницу в храме Гроба Господня! Узнайте почему

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

ТехИнсайдер
9 фраз, которые лучше никогда не произносить вслух 9 фраз, которые лучше никогда не произносить вслух

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

Psychologies
Открыть в приложении