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

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

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

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

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

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

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

Селедка под шубой: история праздничного салата Селедка под шубой: история праздничного салата

Знакомимся с легендами происхождения селедки под шубой

Культура.РФ
Они такие классные. Интервью со Львом Зулькарнаевым и Денисом Прытковым Они такие классные. Интервью со Львом Зулькарнаевым и Денисом Прытковым

Актеры Лев Зулькарнаев и Денис Прытков — о съемках сериала «Она такая классная»

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

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

N+1
Кожа: вот что нужно знать о самом большом человеческом органе Кожа: вот что нужно знать о самом большом человеческом органе

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

ТехИнсайдер
Перегрелись: зачем останавливать глобальное потепление, если оно уже наступило Перегрелись: зачем останавливать глобальное потепление, если оно уже наступило

О том, как бороться с изменением климата, когда оно уже наступило

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

Отрывок из книги психиатра и нейробиолога Грегори Бернса «Иллюзия себя»

СНОБ
Лисички: почему самый хитрый гриб никогда не бывает червивым Лисички: почему самый хитрый гриб никогда не бывает червивым

Что такого опасного содержится в лисичках, что червяки отказываются их есть?

ТехИнсайдер
Новая жизнь Новая жизнь

Вилла в Сочи с интерьером вне времени

SALON-Interior
Урал, любовь моя Урал, любовь моя

5 абсолютно разных граней Большой уральской тропы

2Xplore
В чем секрет успеха спортсменов на Олимпиаде? Психолог олимпийской сборной Британии раскрыла секреты! В чем секрет успеха спортсменов на Олимпиаде? Психолог олимпийской сборной Британии раскрыла секреты!

Как спортсменов готовят к олимпиаде?

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

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

ТехИнсайдер
Почему для женщин наличие секса важнее, чем для мужчин: необычное исследование ученых Почему для женщин наличие секса важнее, чем для мужчин: необычное исследование ученых

Как секс влияет на здоровье женщин?

Psychologies
«Я шопоголик»: как перестать тратить деньги впустую «Я шопоголик»: как перестать тратить деньги впустую

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

Psychologies
Владимир и Рогнеда Владимир и Рогнеда

Картина Антона Лосенко: как Владимир ходил свататься к дочери полоцкого князя

Дилетант
Секретно, параллельно Секретно, параллельно

Открываем мир художника Андрея Ткаченко

Men Today
Вступить в БРИКС. Зачем? Вступить в БРИКС. Зачем?

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

ФедералПресс
Жостово: вaм букетик! Жостово: вaм букетик!

Жостовский расписной поднос — ровесник восстания декабристов

КАНТРИ Русская азбука
Обжиг: привет керамика! Обжиг: привет керамика!

Место, где не просто «горшки обжигают»

КАНТРИ Русская азбука
Как появилась любовь с точки зрения эволюции: мнение биолога Ирины Якутенко Как появилась любовь с точки зрения эволюции: мнение биолога Ирины Якутенко

Как природа помогает парам укреплять связь?

Psychologies
Пристрастие родителей к алкоголю может привести к ускоренному старению их детей Пристрастие родителей к алкоголю может привести к ускоренному старению их детей

Что сильнее влияет на способность бороться с болезнями — природа или воспитание?

ТехИнсайдер
«Включение в систему» «Включение в систему»

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

Дилетант
Точно в срок: 7 советов любителям опозданий Точно в срок: 7 советов любителям опозданий

Вы изо всех сил стараетесь приходить вовремя, но постоянно опаздываете?

Psychologies
6 ловушек, которые мешают нам проживать свою жизнь счастливо 6 ловушек, которые мешают нам проживать свою жизнь счастливо

Почему мы позволяем стереотипам мешать нам жить?

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

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

Psychologies
Неуловимые коты Сайлюгема Неуловимые коты Сайлюгема

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

Наука и жизнь
«Как я разденусь?»: 8 неочевидных причин, которые мешают достичь оргазма «Как я разденусь?»: 8 неочевидных причин, которые мешают достичь оргазма

Что мешает вам получать удовольствие от близости с любимым человеком?

Psychologies
Кто вы в треугольнике Карпмана? Кто вы в треугольнике Карпмана?

Тест: какая роль в треугольнике Карпмана свойственна вам?

Psychologies
Как США создали «город грехов» и мировую столицу азартных игр? Интересные факты о Лас-Вегасе! Как США создали «город грехов» и мировую столицу азартных игр? Интересные факты о Лас-Вегасе!

Как менее чем за сто лет Лас-Вегас превратился в «мировую столицу развлечений»?

ТехИнсайдер
Чистота душевная, любовь нелицемерная Чистота душевная, любовь нелицемерная

Сергий Радонежский – один из самых почитаемых православных святых

Зеркало Мира
Укрепление Сибири или совпадение: как объяснить масштабные кадровые перестановки Укрепление Сибири или совпадение: как объяснить масштабные кадровые перестановки

За неполные два года в трети сибирских регионов сменились руководители

ФедералПресс
Открыть в приложении