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

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
«Книги, кофе и другие измерения»: уникальный магазин в Верхней Пышме «Книги, кофе и другие измерения»: уникальный магазин в Верхней Пышме

Книжный магазин, аналогов которому в Свердловской области нет

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

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

РБК
Александра Зайцева: «Где дом и дым глубин и алый». Фрагмент из книги о домашнем насилии Александра Зайцева: «Где дом и дым глубин и алый». Фрагмент из книги о домашнем насилии

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

СНОБ
Душа над тарелкой Душа над тарелкой

Почему, когда мы слышим хруст хлеба, у нас пробуждается аппетит?

Bones
От Билибина до «Кандинского»: заменит ли нейросеть художников-иллюстраторов От Билибина до «Кандинского»: заменит ли нейросеть художников-иллюстраторов

Что такое вирусная обложка и стоит ли отдавать работу художника нейросети?

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

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

ТехИнсайдер
Посмотрите на «устрицу-монстра»! Эксперты: это не самая большая устрица, но она поражает Посмотрите на «устрицу-монстра»! Эксперты: это не самая большая устрица, но она поражает

Устрицы могут достигать колоссальных размеров

ТехИнсайдер
Охотник за бактериями: как Роберт Кох обнаружил возбудителей сибирской язвы, туберкулеза и холеры Охотник за бактериями: как Роберт Кох обнаружил возбудителей сибирской язвы, туберкулеза и холеры

Роберт Кох первым обнаружил, что виной холере были маленькие бактерии...

ТехИнсайдер
Тенденции следующего поколения субмарин Тенденции следующего поколения субмарин

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

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

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

VOICE
Глава холдинга АО «Росхим»: «Стране нужна сильная химическая промышленность» Глава холдинга АО «Росхим»: «Стране нужна сильная химическая промышленность»

Российская промышленность стремится освоить новые импортозамещающие механизмы

ФедералПресс
В зоне комфорта В зоне комфорта

Comfort food в России всегда была неразрывна с деревней

Bones
Эти рыбы должны создать красивые круги из песка, чтобы привлечь самок! Интересные факты Эти рыбы должны создать красивые круги из песка, чтобы привлечь самок! Интересные факты

Самцы японской рыбы-фугу принимают необычный вызов в брачный период

ТехИнсайдер
Руководитель Форума креативного бизнеса Елена Маринина: Резко вырос спрос на специалистов в креативной сфере Руководитель Форума креативного бизнеса Елена Маринина: Резко вырос спрос на специалистов в креативной сфере

Почему игрокам креативных индустрий важно объединяться, а не конкурировать

СНОБ
Кожа: вот что нужно знать о самом большом человеческом органе Кожа: вот что нужно знать о самом большом человеческом органе

Кожа — не только самый большой, но и самый удивительный орган

ТехИнсайдер
Гжель: сине-бело-голубые Гжель: сине-бело-голубые

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

КАНТРИ Русская азбука
«Кукушка»: боди-хоррор о репродуктивном насилии на альпийском курорте «Кукушка»: боди-хоррор о репродуктивном насилии на альпийском курорте

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

Forbes
«Пульс и сердце, свет в зрачки, череп, руки, ноги, разрядики тока»: отрывок из романа Дании Жанси «Путешествия Лейлы» «Пульс и сердце, свет в зрачки, череп, руки, ноги, разрядики тока»: отрывок из романа Дании Жанси «Путешествия Лейлы»

«Путешествия Лейлы» — о самоопределении, памяти и гранях «нормальности»

Правила жизни
Баклуши бить Баклуши бить

Кто из нас не мечтал хоть разок побить баклуши?

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

Борьба за власть — вечный сюжет из школьных учебников истории

ТехИнсайдер
«Быт разрушает наши отношения»: что делать в таком случае — 9 советов психолога «Быт разрушает наши отношения»: что делать в таком случае — 9 советов психолога

Быт в отношениях — страшный зверь, которого можно приручить

Psychologies
Все фильмы Гаспара Ноэ — от лучшего к худшему Все фильмы Гаспара Ноэ — от лучшего к худшему

9 фильмов загадочного французского режиссера, которые шокируют всех зрителей

Maxim
Из гречки и кокоса! Узнайте о самых полезных для здоровья видах муки Из гречки и кокоса! Узнайте о самых полезных для здоровья видах муки

Стоит ли заменить цельнозерновую муку на гречневую или миндальную?

ТехИнсайдер
Чужбина больше не интересует: как менялось мнение россиян об эмиграции Чужбина больше не интересует: как менялось мнение россиян об эмиграции

В России рекордно снизилось число граждан, желающих попытать счастье за рубежом

ФедералПресс
«Нимб и крест: как читать русские иконы» «Нимб и крест: как читать русские иконы»

Как хорошо средневековый человек ориентировался в иконографии

N+1
Губернатор Забайкалья — о перспективах края в сотрудничестве с Китаем Губернатор Забайкалья — о перспективах края в сотрудничестве с Китаем

За последние пять лет ВРП Забайкалья, по данным Росстата, увеличился в 1,7 раза

РБК
Господин хороший: 10 главных ошибок мягкого руководителя Господин хороший: 10 главных ошибок мягкого руководителя

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

Forbes
«Подделка»: сериал о том, как женщины сталкиваются с аферистами в дейтинге «Подделка»: сериал о том, как женщины сталкиваются с аферистами в дейтинге

«Подделка»: сериале и о реальной истории обмана, которая легла в его основу

Forbes
Лучшие годы Nissan Pathfinder Лучшие годы Nissan Pathfinder

Nissan Pathfinder: выдающиеся модели и те, о которых лучше не вспоминать

4x4 Club
Открыть в приложении