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

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

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

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

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

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

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

Вселенная Marvel: в каком порядке смотреть все фильмы франшизы Вселенная Marvel: в каком порядке смотреть все фильмы франшизы

В каком порядке нужно смотреть фильмы Marvel?

Cosmopolitan
Что такое дроссельная заслонка, за что она отвечает и как работает Что такое дроссельная заслонка, за что она отвечает и как работает

Дроссельный узел – один из важнейших элементов управления двигателя

РБК
5 странных приложений для знакомств 5 странных приложений для знакомств

Сервисы для знакомств, способные удивить

GQ
Кружево: сплетено на коклюшках Кружево: сплетено на коклюшках

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

КАНТРИ Русская азбука
Папоротники: 14 удивительных фактов, доказывающих уникальность и необычность этих растений Папоротники: 14 удивительных фактов, доказывающих уникальность и необычность этих растений

Многие просто не замечают папоротник, однако он крайне необычен

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

Чего не стоит говорить людям, чтобы не сделать им хуже?

Psychologies
Женщина из Китая хотела собаку, — а вырастила медведя! Смешная история Женщина из Китая хотела собаку, — а вырастила медведя! Смешная история

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

ТехИнсайдер
Первые спутники СССР и США: почему они такие разные Первые спутники СССР и США: почему они такие разные

Чем отличались наш и зарубежный первые космические спутники?

ТехИнсайдер
Мёд всему голова Мёд всему голова

Как ухаживают за пчелами и качают мед в усадьбе пасечников

КАНТРИ Русская азбука
Как себе помочь, если нет денег на психолога? Как себе помочь, если нет денег на психолога?

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

VOICE
Плати и учись Плати и учись

Что нужно знать, подписывая договор о платном образовании

Лиза
Безопасно ли есть горячую еду, которую привезли холодной? Объясняют эксперты Безопасно ли есть горячую еду, которую привезли холодной? Объясняют эксперты

Остывшие готовые блюда могут быть действительно опасны для здоровья

VOICE
Он терял кожу от любого удара, а теперь жмет от груди 150 кг! История редкой болезни «детей-бабочек» Он терял кожу от любого удара, а теперь жмет от груди 150 кг! История редкой болезни «детей-бабочек»

Дин Клиффорд бросил вызов смерти и ведет активный образ жизни!

ТехИнсайдер
Дождевые черви не смогут прокормить человечество в случае ядерной войны Дождевые черви не смогут прокормить человечество в случае ядерной войны

Сбор дождевых червей для пропитания оказался слишком трудоемким

N+1
Искусство вокруг руин: «Воскресенский завод» в Башкортостане Искусство вокруг руин: «Воскресенский завод» в Башкортостане

Арт-центр «Воскресенский завод» — неожиданный проект концепции сохранения руин

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

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

Forbes
10 фактов, которые нужно знать мужчинам о женщинам 10 фактов, которые нужно знать мужчинам о женщинам

Семейный психотерапевт напоминает о нескольких особенностях женской психики

Psychologies
Рост заболеваемости раком легких в России объяснили распространением методов диагностики Рост заболеваемости раком легких в России объяснили распространением методов диагностики

К концу 2010-х годов в России наблюдался рост заболеваемости раком легких

N+1
Белый спирт из Китая, покоривший мир Белый спирт из Китая, покоривший мир

В Китае свои алкогольные традиции

Зеркало Мира
10 способов натренировать «мускулы храбрости» 10 способов натренировать «мускулы храбрости»

Храбрость — не врожденное качество, а навык, который можно натренировать

Psychologies
Грифонаж, страпонтен, глабелла, нёрдл: необычные названия привычных вещей Грифонаж, страпонтен, глабелла, нёрдл: необычные названия привычных вещей

Грифонаж, страпонтен, петрикор: вы точно знаете эти вещи

ТехИнсайдер
«Дашь сиську потрогать?»: таксист снимал на видео, как домогался к клиенткам «Дашь сиську потрогать?»: таксист снимал на видео, как домогался к клиенткам

Что можно сделать в ситуации, если вас домогаются?

Psychologies
Трон во крови: истории таинственных исчезновений наследников престола Трон во крови: истории таинственных исчезновений наследников престола

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

ТехИнсайдер
Куда вложить деньги, чтобы они работали в 2024 году? Куда вложить деньги, чтобы они работали в 2024 году?

Вопрос вложения свободных денежных средств беспокоит многих

Наука и техника
Жилища обтекаемой формы: зачем в СССР строили дома в виде бочек Жилища обтекаемой формы: зачем в СССР строили дома в виде бочек

Дома-бочки в СССР: для кого строили эти дома и почему они были такой формы?

ТехИнсайдер
«В Орду! В Орду!» «В Орду! В Орду!»

Россия зачиналась в скопидомном сундуке Ивана Калиты

Дилетант
Проблемы военной безопасности и стабильности в регионе Ближнего и Среднего Востока Проблемы военной безопасности и стабильности в регионе Ближнего и Среднего Востока

Ближний и Средний Восток по ряду причин изобилуют нюансами политики

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

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

СНОБ
Заметая инфобез под ковер: как крупные сервисы проявляют безразличие к уязвимостям Заметая инфобез под ковер: как крупные сервисы проявляют безразличие к уязвимостям

Почему бизнес настолько халатно относится к информационной безопасности?

Forbes
3 факта об истребителе F-16 3 факта об истребителе F-16

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

Maxim
Открыть в приложении