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

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

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

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

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

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

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

5 вопросов про Пасху 5 вопросов про Пасху

Объясняем странные традиции, связанные с главным христианским праздником

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

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

СНОБ
Несущая смерть Несущая смерть

Как Горгона обращала людей в камень и могло ли существовать подобное «биооружие»

Вокруг света
Крах по расписанию: продажи московских новостроек рухнули в июле Крах по расписанию: продажи московских новостроек рухнули в июле

В июле количество заключенных ДДУ в Москве снизилось на 40%

Forbes
Голь на выдумки хитра (часть 2) Голь на выдумки хитра (часть 2)

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

Лиза
Я всегда с собой беру... Я всегда с собой беру...

Несколько простых, но неочевидных средств, которые выручат в экстренной ситуации

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

Почему искусственный интеллект точнее и быстрее прогнозирует погоду?

ТехИнсайдер
Зерна циркона помогли определить возраст мощного удара по молодой Луне Зерна циркона помогли определить возраст мощного удара по молодой Луне

Планетологи с большой точностью датировали крупное импактное событие на Луне

N+1
Евгения Образцова: «Мама не раз мне говорила: «ты — борец, а это хорошее качество для балерины» Евгения Образцова: «Мама не раз мне говорила: «ты — борец, а это хорошее качество для балерины»

Выхожу на сцену и слышу за спиной: «О, пошла, пошла, смотрите-ка...»

Караван историй
Правила хранения джина, виски и водки Правила хранения джина, виски и водки

Почему водка иногда теряет свой вкус и откуда в виски появляются ноты резины?

СНОБ
И ты, Иван? И ты, Иван?

Почему гетман Иван Мазепа предал своего царя?

Дилетант
Солнце близко, но не греет: почему на вершинах гор часто лежит снег? Солнце близко, но не греет: почему на вершинах гор часто лежит снег?

Почему в горах всегда холоднее, чем внизу?

ТехИнсайдер
«Какая милота!»: 5 советов, как извлечь пользу из картинок с кошечками и собачками «Какая милота!»: 5 советов, как извлечь пользу из картинок с кошечками и собачками

Любоваться милыми щенками и котятами — не только нормально, но и полезно!

Psychologies
Завтрак на траве Завтрак на траве

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

Лиза
Один на один с собой: почему топ-менеджерам не хватает общения и как это исправить Один на один с собой: почему топ-менеджерам не хватает общения и как это исправить

65% опрошенных беспокоят вопросы выстраивания стратегии и партнерской работы

Inc.
Слава блогу: кто такие православные блогеры и почему они популярны Слава блогу: кто такие православные блогеры и почему они популярны

Кто и зачем учит вере в соцсетях?

Правила жизни
Мясо по-фрaнузки Мясо по-фрaнузки

Хотите озадачить гостя из Парижа – приготовьте ему свинину под сырной корочкой

КАНТРИ Русская азбука
Вышла на прогулку и покорила Аппалачскую тропу: история бабушки Эммы Гейтвуд Вышла на прогулку и покорила Аппалачскую тропу: история бабушки Эммы Гейтвуд

Эмма Гейтвуд: сказала родственникам, что выйдет прогуляться, и ушла на 146 дней

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

Зачем люди намеренно «ломали» древнеегипетским статуям носы?

ТехИнсайдер
На педали жали: краткий таймлайн велосипедной формы На педали жали: краткий таймлайн велосипедной формы

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

Правила жизни
Лыжи. Разрез. Девушка Лыжи. Разрез. Девушка

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

2Xplore
«Таких эмоций не найдешь в боулинге или кино» «Таких эмоций не найдешь в боулинге или кино»

Почему у баскетбола миллионы фанатов по всему миру? Отвечает Андрей Кириленко

VOICE
Часовое искусство Часовое искусство

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

RR Люкс.Личности.Бизнес.
«Железный купол»: логика работы и техническое воплощение «Железный купол»: логика работы и техническое воплощение

О принципах работы и основах устройства эффективного противоракетного комплекса

Наука
«Академикам-медикам не нашлось места в зале общего собрания» «Академикам-медикам не нашлось места в зале общего собрания»

Исполнилось 80 лет со дня основания медицинской академии наук СССР

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

Когда вода не приносит пользы, нужно ли ее выводить из организма?

РБК
Красненькая пошла Красненькая пошла

Как отвращение к насилию превратило Сэма Пекинпа в «кровавого Сэма»

Weekend
«Такую никто не возьмет»: как в традиционном обществе относятся к пережившим насилие «Такую никто не возьмет»: как в традиционном обществе относятся к пережившим насилие

Отрывок из романа, в котором героиня выступила против традиционного общества

Forbes
Идея: худеем! Идея: худеем!

3 полезные диеты для здоровья. Выбери свою!

Лиза
Мордвиновы Мордвиновы

Первый представитель рода Мордвиновых попал на Русь в статусе заложника

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