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

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

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

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

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

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

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

Александр Чулок: «Мы не стараемся угадать будущее, мы хотим его создать» Александр Чулок: «Мы не стараемся угадать будущее, мы хотим его создать»

Прогнозист Александр Чулок — о том, чем станет ИИ для общества в будущем

РБК
Люди из будущего Люди из будущего

Время не имеет над тайцами силы, ведь каждый продолжается в вечности

Вокруг света
10 самых продаваемых Jeep за всю историю существования 10 самых продаваемых Jeep за всю историю существования

Культовые модели Jeep

4x4 Club
Глава минпромторга Красноярского края: «Инвестиции растут на 25% в год» Глава минпромторга Красноярского края: «Инвестиции растут на 25% в год»

Красноярский край реализует инвестпроекты на триллионы рублей

ФедералПресс
Правильный гардероб: писательница Вера Богданова — о стиле Бритни Спирс, фраке Мармеладова и своей любви к «леопарду» Правильный гардероб: писательница Вера Богданова — о стиле Бритни Спирс, фраке Мармеладова и своей любви к «леопарду»

Писательница Вера Богданова — о любви к казакам и пижамам

Правила жизни
Семейный совет Семейный совет

Что входит в чек-лист фертильности, высоки ли шансы преодолеть мужское бесплодие

Собака.ru
Обжиг: привет керамика! Обжиг: привет керамика!

Место, где не просто «горшки обжигают»

КАНТРИ Русская азбука
Почему лениться полезно Почему лениться полезно

5 неожиданных фактов о лени от врача

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

Из-за чего молодые люди полюбили игрушки и как бизнес этим пользуется

Forbes
Скажем истерике «нет» Скажем истерике «нет»

Как реагировать на детскую истерику?

Лиза
Набрать, сбросить, повторить: как актеры вынуждены менять свою внешность ради карьеры Набрать, сбросить, повторить: как актеры вынуждены менять свою внешность ради карьеры

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

Forbes
Труба пучка Большого адронного коллайдера помогла установить новый предел на магнитные монополи Труба пучка Большого адронного коллайдера помогла установить новый предел на магнитные монополи

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

N+1
«Гуслица»: творческая усадьба на территории мануфактуры «Гуслица»: творческая усадьба на территории мануфактуры

Вдали мегаполиса энтузиасты развивают на историческом месте новую арт-резиденцию

Psychologies
Старик и Ворон Старик и Ворон

Билл Скарсгорд в новой адаптации культового комикса

Weekend
В ногу со временем В ногу со временем

70 лет «Минскому заводу колесных тягачей»

Обозрение армии и флота
Кто вы в треугольнике Карпмана? Кто вы в треугольнике Карпмана?

Тест: какая роль в треугольнике Карпмана свойственна вам?

Psychologies
Семейный подряд: как Коэны, Вачовски и другие братья и сестры вместе снимают кино Семейный подряд: как Коэны, Вачовски и другие братья и сестры вместе снимают кино

Восемь творческих команд, которые вместе создают кино

Forbes
Про тех, кто вечно в шоке Про тех, кто вечно в шоке

Что такое аффектация простыми словами, рассказывает психолог Надежда Бримаер

Лиза
Как выстроить доверие в отношениях: 14 правил, о которых мы часто забываем Как выстроить доверие в отношениях: 14 правил, о которых мы часто забываем

Правила, которые помогут построить крепкие отношения

Psychologies
Гжель: сине-бело-голубые Гжель: сине-бело-голубые

Особенности производства гжельской посуды

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

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

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

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

Psychologies
Прочистить чакру и обновить ауру: почему мы верим в сомнительные методы помощи Прочистить чакру и обновить ауру: почему мы верим в сомнительные методы помощи

Почему люди доверяют чакрологам и прочим «специалистам»?

Psychologies
5 секретов для достижения любой цели 5 секретов для достижения любой цели

Успех начинания, каким бы оно ни было, зависит от пяти элементов благополучия

Psychologies
Юла: кручу-верчу Юла: кручу-верчу

Яркая и шумная юла уже много веков веселит малышню в российских домах

КАНТРИ Русская азбука
Жизнь моя — шарманка Жизнь моя — шарманка

«Планета Джанет»: образцовая мелодрама A24

Weekend
Инвестиции в импортозамещение: их эффект для развития российской промышленности Инвестиции в импортозамещение: их эффект для развития российской промышленности

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

ФедералПресс
Повышаем обороты Повышаем обороты

Как разогнать метаболизм без спортзала и диет?

Лиза
Урал, любовь моя Урал, любовь моя

5 абсолютно разных граней Большой уральской тропы

2Xplore
Если бы в школе был урок биографии Если бы в школе был урок биографии

Почему в школе не изучают биографию?

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