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

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

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

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

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

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

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

Самые забавные конфузы Бузовой, Орбакайте и других звезд у Ивана Урганта Самые забавные конфузы Бузовой, Орбакайте и других звезд у Ивана Урганта

Забавные конфузы в студии шоу «Вечерний Ургант»

Cosmopolitan
Новая смена Новая смена

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

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

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

N+1
Замечали лицемерие? Посмотрите на 7 видов улыбок и узнайте их значение! Замечали лицемерие? Посмотрите на 7 видов улыбок и узнайте их значение!

Что улыбка может рассказать о человеке?

ТехИнсайдер
«Всюду одно растление и разврат» «Всюду одно растление и разврат»

Андрей Платонов о том, как он не стал советским писателем

Weekend
Милая агрессия и боязнь счастья: 5 необычных психологических явлений Милая агрессия и боязнь счастья: 5 необычных психологических явлений

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

ТехИнсайдер
«Смерч 2»: блокбастер о девушке-метеорологе, которая бросила вызов торнадо «Смерч 2»: блокбастер о девушке-метеорологе, которая бросила вызов торнадо

«Смерч 2»: больше, чем захватывающий фильм-катастрофа

Forbes
Без оглядки на маму: почему незавершенная сепарация вызывает чувство вины Без оглядки на маму: почему незавершенная сепарация вызывает чувство вины

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

Forbes
Как готовят будущих «айтишников» в столичных школах Как готовят будущих «айтишников» в столичных школах

Как помочь будущему айтишнику найти свое призвание

Наука и техника
Сколько зарабатывает дальнобойщик и как им стать Сколько зарабатывает дальнобойщик и как им стать

Как стать дальнобойщиком и сколько он зарабатывает, выяснил Autonews.ru

РБК
Эта кукла напугала американцев! Узнайте историю игрушки «с паранормальными способностями» Эта кукла напугала американцев! Узнайте историю игрушки «с паранормальными способностями»

Почему людям страшно находиться рядом с этой куклой?

ТехИнсайдер
Ярких летучих мышей из Азии начали истреблять ради изготовления украшений Ярких летучих мышей из Азии начали истреблять ради изготовления украшений

На онлайн-площадках в большом количестве торгуют украшенными гладконосами

N+1
Как поймать северное сияние и сфотографировать его: по этим 4 шагам даже школьник сделает классные снимки Как поймать северное сияние и сфотографировать его: по этим 4 шагам даже школьник сделает классные снимки

Как, наконец, увидеть это злосчастное сияние?!

ТехИнсайдер
Портал в прошлое Портал в прошлое

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

Вокруг света
Стоматолог Блюмкин рассказал, какие гаджеты для зубов нужно приобрести каждому Стоматолог Блюмкин рассказал, какие гаджеты для зубов нужно приобрести каждому

Актуальные гаджеты для гигиены полости рта — советует стоматолог

ТехИнсайдер
Ученый Горелов рассказал, как найти утечки тепла в доме Ученый Горелов рассказал, как найти утечки тепла в доме

Есть ли польза от бесконтактного термометра, где искать «мостики холода»?

ТехИнсайдер
6 форматов дружбы между мужчиной и женщиной: мнения сторон 6 форматов дружбы между мужчиной и женщиной: мнения сторон

Дружба между мужчиной и женщиной: не фасад ли это для подтекстов?

Psychologies
Однажды работник Кока-колы хотел продать секрет напитка! Но представители Пепси позвали ФБР Однажды работник Кока-колы хотел продать секрет напитка! Но представители Пепси позвали ФБР

Как сотрудник Coca-Cola попытался продать коммерческие секреты Pepsi

ТехИнсайдер
Клоп — топ Клоп — топ

Никита Кологривый: между восторгом и порицанием

Men Today
Как выбрать подушку? Как выбрать подушку?

Как выбрать комфортную подушку и из чего она должна быть сделана

Maxim
Исследование: женщины должны начинать ежегодную маммографию в возрасте 40 лет Исследование: женщины должны начинать ежегодную маммографию в возрасте 40 лет

Когда женщинам следует начинать делать маммографию? Ответ есть!

ТехИнсайдер
Эксперт рассказал, как меньше пьянеть! Факты о толерантности к алкоголю Эксперт рассказал, как меньше пьянеть! Факты о толерантности к алкоголю

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

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

Короткое, но важное соприкосновение отельера с искусственным интеллектом

Правила жизни
Умножение делением Умножение делением

Безусловный базовый доход: почему он не станет билетом в безбедную жизнь

РБК
Зловещие пятна на теле планеты Зловещие пятна на теле планеты

16 июля 1945 года человечество, само еще не подозревая, вступило в атомную эру

Наука и техника
Не те герои Не те герои

Минфин планирует активно выводить на рынок акций национализированные компании

Монокль
Дмитрий Ливанов: «В XXI веке само понятие специальности становится устаревшим» Дмитрий Ливанов: «В XXI веке само понятие специальности становится устаревшим»

Дмитрий Ливанов о прошлом, настоящем и будущем российского образования

РБК
Вино из Воронежа Вино из Воронежа

В мир вина я попал очень просто — мама была большой ценительницей

Bones
Ресторан-перформанс Ресторан-перформанс

Об иммерсивном пространстве, существующем на стыке гастрономии и перформанса

Bones
4 признака, что отправляться в совместное путешествие с человеком не стоит 4 признака, что отправляться в совместное путешествие с человеком не стоит

Иногда стили отдыха даже самых близких людей не совпадают, и это нормально

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