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

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

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

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

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

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

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

Как доказать ребенку, что Земля круглая Как доказать ребенку, что Земля круглая

Запаситесь терпением: объяснить ребенку, что Земля круглая, не так уж просто

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

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

Psychologies
Всё, что нужно знать об «обмелении» — технике, позволяющей получить самые яркие оргазмы от проникновения Всё, что нужно знать об «обмелении» — технике, позволяющей получить самые яркие оргазмы от проникновения

Об обмелении — одном из секс-трендов года

VOICE
«Джеймс Уэбб» рассмотрел параллельные джеты у двойной протозвезды в кратной системе «Джеймс Уэбб» рассмотрел параллельные джеты у двойной протозвезды в кратной системе

Одна из протозвезд в системе WL20 на самом деле является парой протозвезд

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

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

Правила жизни
Ксения Лучанинова: «На Дальнем Востоке частная медицина конкурирует с государственной за кадры» Ксения Лучанинова: «На Дальнем Востоке частная медицина конкурирует с государственной за кадры»

Дальний Восток — регион, в который устремлены все планы государства

ФедералПресс
10 способов ментальной самообороны 10 способов ментальной самообороны

Хотите инструкцию, какие конкретно принять меры против манипуляций?

Psychologies
Редкое животное и первые кадры! Фермер из Боливии сумел заснять амазонскую ласку: видео Редкое животное и первые кадры! Фермер из Боливии сумел заснять амазонскую ласку: видео

Об удивительном существе из густых лесов Амазонки известно не так много

ТехИнсайдер
Полярные сияния будут возникать не только на крайнем севере! Вот как вспышки на Солнце влияют на Землю Полярные сияния будут возникать не только на крайнем севере! Вот как вспышки на Солнце влияют на Землю

Как солнечная активность влияет на Землю и вызывает полярные сияния

ТехИнсайдер
Желание превыше всего: 5 лучших эротических драм Желание превыше всего: 5 лучших эротических драм

Фильмы, которые изучают запретную любовь с точки зрения женщины

Psychologies
Жизнь моя — шарманка Жизнь моя — шарманка

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

Weekend
10 вредных советов, которые помогут не дожить до старости 10 вредных советов, которые помогут не дожить до старости

Халатное отношение к собственному здоровью способно сильно укоротить вашу жизнь

Psychologies
Фартук, косы, кружева Фартук, косы, кружева

Какой была школьная форма в СССР

Лиза
Скажи мне, кто твой друг Скажи мне, кто твой друг

Национальные парки, экофермы, питомники с редкими животными: топ-12 таких мест

2Xplore
Троян-шпион у пользователей Android: этичный хакер Песковский рассказал, как обезопасить смартфон от вирусов Троян-шпион у пользователей Android: этичный хакер Песковский рассказал, как обезопасить смартфон от вирусов

Как защитить свой телефон от любых вирусов

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

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

ТехИнсайдер
Цветы: цветики-цветочки Цветы: цветики-цветочки

Цветки всех мастей, скроенные вручную из самых разных материалов

КАНТРИ Русская азбука
В древнем горшке из Китая нашли остатки пищи эпохи неолита В древнем горшке из Китая нашли остатки пищи эпохи неолита

Ученые проанализировали пищевую корку в керамическом горшке из памятника Хэмуду

N+1
«Изменилось только название» «Изменилось только название»

Андрей Пантюхов о том, чего стоило компании расставание с бывшим владельцем

РБК
Два «кукурузника»: у нашего родного биплана По-2 нашелся американский брат-близнец Два «кукурузника»: у нашего родного биплана По-2 нашелся американский брат-близнец

Зачем Boeing разрабатывала «кукурузники»?

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

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

ФедералПресс
Как табачные компании приучили женщин курить через идеи феминизма Как табачные компании приучили женщин курить через идеи феминизма

Как капитализм благими намерениями приучил женщин курить

Maxim
Ощущение вкуса Ощущение вкуса

На что мы смотрим, когда выбираем блюдо или напиток?

Bones
Имел несчастие быть немцем… Имел несчастие быть немцем…

Кто такой был Эрнст Иоганн Бирон и как он был связан с Анной Иоанновной?

Дилетант
5 отличных романов, где море — главный герой 5 отличных романов, где море — главный герой

Произведения, в которых море — не просто красивый фон, а важный элемент истории

СНОБ
Ярчайшая Ярчайшая

О самой яркой звезде ночного неба — Сириусе

Наука и жизнь
Юридические тексты сравнили с магическими заклинаниями Юридические тексты сравнили с магическими заклинаниями

Зачем авторы официальных текстов используют такие сложные конструкции?

N+1
Как на Дальнем Востоке решают  проблемы кадрового дефицита Как на Дальнем Востоке решают  проблемы кадрового дефицита

Российская экономика активизировалась на азиатском рынке

РБК
Про тех, кто вечно в шоке Про тех, кто вечно в шоке

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

Лиза
Новая смена Новая смена

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

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