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

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

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

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

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

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

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

Думай сам: когда человечество создаст сильный ИИ и как это отразится на обществе Думай сам: когда человечество создаст сильный ИИ и как это отразится на обществе

Смогут ли системы функционировать без прямого вмешательства человека?

Forbes
История одной вещи: консервная банка, запрошенная Наполеоном и воспетая Уорхолом История одной вещи: консервная банка, запрошенная Наполеоном и воспетая Уорхолом

Какую трансформацию консервная банка потерпела с конца XVIII века

Правила жизни
«Разные: мужское и женское глазами приматолога» «Разные: мужское и женское глазами приматолога»

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

N+1
Итальянский бродяга и французская гордость: герои Парижа, которых обсуждал весь мир Итальянский бродяга и французская гордость: герои Парижа, которых обсуждал весь мир

В Париже-2024 есть спортсмены, которых награждают совсем не медалями

Forbes
Он терял кожу от любого удара, а теперь жмет от груди 150 кг! История редкой болезни «детей-бабочек» Он терял кожу от любого удара, а теперь жмет от груди 150 кг! История редкой болезни «детей-бабочек»

Дин Клиффорд бросил вызов смерти и ведет активный образ жизни!

ТехИнсайдер
Японский бот тебе товарищ Японский бот тебе товарищ

«Санни»: сериал-инструкция по мирному сосуществованию с роботами

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

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

ТехИнсайдер
Сталкер, топор и подземные боги: Игорь Яковенкo выпустил языческий альбом «Пантеон» Сталкер, топор и подземные боги: Игорь Яковенкo выпустил языческий альбом «Пантеон»

Композитор Игорь Яковенко и барабанщик Петр Ившин выпускают альбом «Пантеон»

СНОБ
Осторожно, очень горячо! Что делать, если телефон перегрелся Осторожно, очень горячо! Что делать, если телефон перегрелся

Как реанимировать смартфон после перегрева?

ТехИнсайдер
Деньги за идею: как и зачем технологические компании выходят на pre-IPO Деньги за идею: как и зачем технологические компании выходят на pre-IPO

Сколько технологическим компаниям удается зарабатывать на pre-IPO

Forbes
Поможет не только на кухне: 6 неожиданных способов, как использовать кукурузный крахмал в быту Поможет не только на кухне: 6 неожиданных способов, как использовать кукурузный крахмал в быту

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

ТехИнсайдер
Защита краснокнижных растений и животных: один из национальных приоритетов Защита краснокнижных растений и животных: один из национальных приоритетов

Как в России за последнее время усилились меры защиты животных

ФедералПресс
История успеха Макдоналдса! Вот как менялся логотип именитой фастфуд-франшизы История успеха Макдоналдса! Вот как менялся логотип именитой фастфуд-франшизы

Логотип McDonald's — один из самых узнаваемых, а его история полна изменений

ТехИнсайдер
Снижение кислотности пищи замедлило поражение почек при артериальной гипертензии Снижение кислотности пищи замедлило поражение почек при артериальной гипертензии

Ощелачивающие фрукты и овощи снизили кардиологические риски

N+1
Сербская литиевая драма Сербская литиевая драма

Руководство Сербии дало добро на разработку крупного месторождения лития

Монокль
Как устроить ролевую игру, если ты не знаешь, с чего начать: 8 полезных советов Как устроить ролевую игру, если ты не знаешь, с чего начать: 8 полезных советов

Итак, вы решили попробовать ролевые игры — с чего начать?

VOICE
Финслерова геометрия как теория четырехмерности мира Финслерова геометрия как теория четырехмерности мира

О геометрии Вселенной, сверхсветовых скоростях и египетских пирамидах

Зеркало Мира
Безмолвные слезы вещей: роман о расследовании судеб погибших в концлагерях Безмолвные слезы вещей: роман о расследовании судеб погибших в концлагерях

Отрывок из романа Гаэль Ноан «Бюро расследования судеб»

Forbes
Маленькие трагедии Маленькие трагедии

Что определяет детскую моду? В первую очередь то, кем взрослые видят детей

Grazia
Моменты внезапных прозрений позволят «заглянуть» в сознание Моменты внезапных прозрений позволят «заглянуть» в сознание

В моменты «скачков» обучения сознание выражается наиболее полно и глубоко

ТехИнсайдер
Не морем единым Не морем единым

Мы предлагаем разнообразить досуг интересными экскурсиями в Краснодарском крае

Лиза
Глава компании «Полипласт Северо-запад» — о высоких технологиях и импортозамещении Глава компании «Полипласт Северо-запад» — о высоких технологиях и импортозамещении

О важности следовать принципам бережливого производства и ESG-повестке

РБК
Бэнкси завершил серию граффити с животными на улицах Лондона Бэнкси завершил серию граффити с животными на улицах Лондона

Девятая и финальная работа Бэнкси появилась на роль-ставнях Лондонского зоопарка

Forbes
Вопрос психологу: как стресс влияет на принятие решений? Вопрос психологу: как стресс влияет на принятие решений?

Какое влияние стресс оказывает на мышление и поведение?

Правила жизни
«Насилие, алкоголь и порно не делают вас мужчиной»: что на самом деле значит «быть мужественным» «Насилие, алкоголь и порно не делают вас мужчиной»: что на самом деле значит «быть мужественным»

Что заставляет мужчин развиваться и добиваться успеха?

Psychologies
В дружеских объятиях дракона: принесет ли Китай пользу российской отрасли видеоигр В дружеских объятиях дракона: принесет ли Китай пользу российской отрасли видеоигр

Какими перспективами может обернуться сотрудничество в отрасли видеоигр РФ и КНР

Forbes
Версия для печати: скоро ли 3D-принтеры соберут человека по частям Версия для печати: скоро ли 3D-принтеры соберут человека по частям

Первые пациенты с 3D-имплантатами уже живут среди нас

Forbes
Сшить себе свободу: как швейная машина помогала женщинам бороться за свои права Сшить себе свободу: как швейная машина помогала женщинам бороться за свои права

Как в истории швейной машины отражается история женской эмансипации

Forbes
Магия волос Магия волос

Традиции, ритуалы и суеверия, связанные с волосами

Лиза
Точно в срок: 7 советов любителям опозданий Точно в срок: 7 советов любителям опозданий

Вы изо всех сил стараетесь приходить вовремя, но постоянно опаздываете?

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