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

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
Постотпускной синдром Постотпускной синдром

Почему можно впасть в депрессию после отдыха и что с этим делать

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

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

РБК
Бить как все Бить как все

Почему важно не бояться получать по лицу и отвечать тем же

Men Today
Сухбат Афлатуни: «Катехон». Фрагмент из романа-головоломки Сухбат Афлатуни: «Катехон». Фрагмент из романа-головоломки

Глава из «Катехона» — истории любви и хроники жизни от Сухбата Афлатуни

СНОБ
Название для смерти Название для смерти

Какие слова и понятия возникли во время Первой мировой войны

Weekend
3 частые ситуации, в которых мы раним близких, сами того не желая 3 частые ситуации, в которых мы раним близких, сами того не желая

Будьте осторожны: подобное поведение действительно может убить отношения!

Psychologies
Вкус ностальгии: блюда, которые были в каждой советской школьной столовой Вкус ностальгии: блюда, которые были в каждой советской школьной столовой

Вспоминаем, какие блюда подавали в каждой школе СССР

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

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

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

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

Зеркало Мира
Подо льдами Подо льдами

Плавание подводных лодок подо льдами теперь стало обыденным явлением

Наука и техника
Жизнь на Земле была сложной уже 2 миллиарда лет назад Жизнь на Земле была сложной уже 2 миллиарда лет назад

Сложные организмы появились не позднее 2,1 миллиарда лет назад

ТехИнсайдер
Мнение эксперта: Фрейда «неправильно поняли»! Он не был одержим сексом, как принято считать Мнение эксперта: Фрейда «неправильно поняли»! Он не был одержим сексом, как принято считать

Зигмунд Фрейд не считал, что все фантазии во сне — это подавленная эротика

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

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

Psychologies
Как измерить силу своих чувств: шкала Клода Штайнера Как измерить силу своих чувств: шкала Клода Штайнера

Можете ли вы описать, что вы чувствуете прямо сейчас?

Psychologies
Наличники (или шоу «Окна») Наличники (или шоу «Окна»)

Почему резные наличники получили распространение именно в России?

КАНТРИ Русская азбука
Zventa Sventana: мы часто становимся жертвами плагиата Zventa Sventana: мы часто становимся жертвами плагиата

Разговор о современном фолке — интервью с Zventa Sventana

СНОБ
Федор Гамалея Федор Гамалея

Актер Федор Гамалея — праправнук гениального ученого, сделавший себя сам

Собака.ru
Ксения Таран: «Благодарна Касаткиной, Бурдонскому, Чурсиной за то, что преподали мне свои уроки!» Ксения Таран: «Благодарна Касаткиной, Бурдонскому, Чурсиной за то, что преподали мне свои уроки!»

Театр — это живой организм: как ты к нему относишься, так он и отвечает

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

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

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

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

РБК
Уголок школьника Уголок школьника

5 вещей и предметов мебели, которые нужно выбросить из детской комнаты

Лиза
Вино из Воронежа Вино из Воронежа

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

Bones
Думать — больно? Западные эксперты рассказали, как сознательно снизить уровень стресса Думать — больно? Западные эксперты рассказали, как сознательно снизить уровень стресса

Мышление может причинять боль? Вот как это объясняют специалисты!

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

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

Psychologies
Николай Горинович: изуродованный революционер, ставший праведником Николай Горинович: изуродованный революционер, ставший праведником

Николай Горинович был революционером, которого пытались убить его же соратники

СНОБ
Лоскутное одеяло: в стиле пэтчворк Лоскутное одеяло: в стиле пэтчворк

Как создать лоскутные украшения дома из обрезки старых тканей?

КАНТРИ Русская азбука
Встреча с нарциссом: 4 урока, за которые следует его поблагодарить Встреча с нарциссом: 4 урока, за которые следует его поблагодарить

Методы самообороны в общении с нарциссом

Psychologies
4 простых лайфхака, как вывести плесень с одежды 4 простых лайфхака, как вывести плесень с одежды

Как убрать плесень на одежде — ловите целых четыре способа

ТехИнсайдер
Коллекционер Антон Козлов: На картине можно изображать любую крамолу Коллекционер Антон Козлов: На картине можно изображать любую крамолу

Коллекционер Антон Козлов — про табу в современном искусстве и страхе перед ним

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