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

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
Семейный совет Семейный совет

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

Собака.ru
25 вещей, которые на самом деле ненавидят женщины 25 вещей, которые на самом деле ненавидят женщины

Эта статья поможет тебе прожить чуть более счастливую и долгую жизнь

Maxim
Неуправляемый хаос: 7 лучших (и не самых очевидных) книг Владимира Сорокина Неуправляемый хаос: 7 лучших (и не самых очевидных) книг Владимира Сорокина

На примере 7 книг рассказываем, как Владимир Сорокин играет с текстом

Правила жизни
Автоэксперт Пономарев рассказал, как проверить наличие фреона в автокондиционере Автоэксперт Пономарев рассказал, как проверить наличие фреона в автокондиционере

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

ТехИнсайдер
Вступить в БРИКС. Зачем? Вступить в БРИКС. Зачем?

Что такое БРИКС и какое значение имеет блок в современном мире

ФедералПресс
Дарья и Александра Соломины: «Чем старше он становился, тем чаще возвращался к своему читинскому детству» Дарья и Александра Соломины: «Чем старше он становился, тем чаще возвращался к своему читинскому детству»

Юрий Мефодьевич никогда не вел себя как звезда

Караван историй
Сад против времени. В поисках рая для всех Сад против времени. В поисках рая для всех

Глава из сборника Оливии Лэнг «Сад против времени. В поисках рая для всех»

Правила жизни
8 способов увеличить автономность смартфона на Android 8 способов увеличить автономность смартфона на Android

Cпособы увеличения времени автономной работы смартфона Android

CHIP
9 последствий парентификации, которые неминуемо отражаются на женской психике 9 последствий парентификации, которые неминуемо отражаются на женской психике

Как меняется поведение дочерей, ставших жертвами парентификации?

Psychologies
Борьба за ярлык Борьба за ярлык

Как Калита начал собирать русские земли вокруг Москвы?

Дилетант
Хочу так же! Хочу так же!

6 фильмов с красивыми интерьерами

Лиза
«Всюду одно растление и разврат» «Всюду одно растление и разврат»

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

Weekend
«Регион получает специалиста, выпускник — современную программу обучения» «Регион получает специалиста, выпускник — современную программу обучения»

Чему учат на Дальнем Востоке и как работают в макрорегионе федеральные программы

РБК
3 факта об истребителе F-16 3 факта об истребителе F-16

Странное название и наследие подводных лодок: что надо знать про самолет F-16.

Maxim
Иди и дружи! Иди и дружи!

Как быть, если в книжках дружба есть, а в жизни ребенка – совсем наоборот?

Лиза
Не подходи ко мне! Не подходи ко мне!

Если муж раздражает: почему так происходит и что с этим делать

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

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

Forbes
«Месье поправляет пенсне» «Месье поправляет пенсне»

История очков, настоящий исторический детектив

Зеркало Мира
Нейробиологи рассказали, как в мозге возникает память о страхе Нейробиологи рассказали, как в мозге возникает память о страхе

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

ТехИнсайдер
Про тех, кто вечно в шоке Про тех, кто вечно в шоке

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

Лиза
10 лучших фильмов Дастина Хоффмана 10 лучших фильмов Дастина Хоффмана

Лучшие картины с участием Дастина Хоффмана

Правила жизни
Роботы и инвесторы Роботы и инвесторы

Минпромторг предлагает новый вид специальных инвестиционных контрактов

Монокль
Юла: кручу-верчу Юла: кручу-верчу

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

КАНТРИ Русская азбука
Не морем единым Не морем единым

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

Лиза
Старость – не данность Старость – не данность

Можно ли на самом деле хотя бы замедлить старение?

Вокруг света
Что такое джиу-джитсу: виды, приемы, советы мастера с черным поясом Что такое джиу-джитсу: виды, приемы, советы мастера с черным поясом

Джиу-джитсу: шахматы в мире единоборств

РБК
«Пойми меня, если сможешь»: как работает эмпатия и чем может помочь искусственный интеллект «Пойми меня, если сможешь»: как работает эмпатия и чем может помочь искусственный интеллект

Насколько ограничены мы в понимании друг друга? И что это вообще значит?

Psychologies
Золотой завтрак: как хлопья стали символом успеха для олимпийских чемпионов Золотой завтрак: как хлопья стали символом успеха для олимпийских чемпионов

Почему попасть на коробку хлопьев Wheaties — мечта многих спортсменов

Forbes
Чем съемка Игр в Париже отличалась от съемки Олимпиады в Сочи — рассказывает Андрей Болтенко Чем съемка Игр в Париже отличалась от съемки Олимпиады в Сочи — рассказывает Андрей Болтенко

Почему парижское открытие Игр и революционное, и «жульническое» одновременно

СНОБ
Открыть в приложении