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

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
Нанимать мигрантов станут по-новому: как изменится рынок труда в России Нанимать мигрантов станут по-новому: как изменится рынок труда в России

Процедура найма мигрантов может измениться в сторону ужесточения

ФедералПресс
«Разные: мужское и женское глазами приматолога» «Разные: мужское и женское глазами приматолога»

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

N+1
Русская альтернатива Русская альтернатива

Почему Запад против нас ополчился и как его победить

Монокль
Польза стручковой фасоли для организма: советы врача и рецепты Польза стручковой фасоли для организма: советы врача и рецепты

Стручковая фасоль не только разнообразит рацион, но и поддерживает здоровье

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

Правда ли, что результат от блефаропластики не сохраняется навсегда?

Лиза
5 самых ожидаемых фильмов ужасов 5 самых ожидаемых фильмов ужасов

Поклонники фильмов ужасов пополняют свои вотч-листы интригующими новинками

Maxim
«Хороших девочек не убивают»: легкий детектив о юной сыщице с Эммой Майерс «Хороших девочек не убивают»: легкий детектив о юной сыщице с Эммой Майерс

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

Forbes
Почему мы ненавидим в других то, что не принимаем в себе? Почему мы ненавидим в других то, что не принимаем в себе?

Что такое проекция и почему нас раздражает то, что мы не принимаем в себе

Psychologies
Ивановичи Ивановичи

Обоим сыновьям Ивана Калиты совсем не повезло с местом в истории

Дилетант
Не до шуток: почему умирает жанр ситкомов и какой будет комедия положений будущего Не до шуток: почему умирает жанр ситкомов и какой будет комедия положений будущего

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

Forbes
Инновационные решения ЦНИРТИ армии и флоту к 120-летию РЭБ Инновационные решения ЦНИРТИ армии и флоту к 120-летию РЭБ

Основные направления деятельности ЦНИРТИ сегодня

Обозрение армии и флота
Скрытые жиры Скрытые жиры

Ограничивая себя в животных жирах, мы забываем о растительных

Лиза
Высокие амбиции Высокие амбиции

Современный интерьер с элементами шинуазри и азиатской тематики

SALON-Interior
Экшен и искрометный юмор: 16 лучших комедийных боевиков Экшен и искрометный юмор: 16 лучших комедийных боевиков

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

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

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

РБК
Праздник урожая. Как выбирать продукты для консервирования: фрукты, ягоды, овощи, грибы Праздник урожая. Как выбирать продукты для консервирования: фрукты, ягоды, овощи, грибы

Консервируем овощи и фрукты – быстро, качественно и без лишних затрат

Лиза
Биохакинг на экспорт: как запустить медицинский бизнес на постсоветском пространстве Биохакинг на экспорт: как запустить медицинский бизнес на постсоветском пространстве

Как сеть клиник биохакинга Biorise запустила франшизу в Казахстане и Армении

Forbes
Медиатор: кто это и чем занимается Медиатор: кто это и чем занимается

В каких ситуациях медиатор незаменим и чем он отличается от психолога?

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

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

Psychologies
Триколор и Булочка: 39 текстов про тело в одной книге Триколор и Булочка: 39 текстов про тело в одной книге

Тема телесности раскрывается в тридцати девяти текстах «Тело: у каждого свое»

СНОБ
Дизайн ИИ: как устроен виртуальный ассистент и кто его создает Дизайн ИИ: как устроен виртуальный ассистент и кто его создает

С какими неочевидными вызовами сталкиваются создатели ИИ-помощников в России

Правила жизни
«Бесконечная смоляная мгла»: роман об алкогольной зависимости посреди полярной ночи «Бесконечная смоляная мгла»: роман об алкогольной зависимости посреди полярной ночи

Отрывок из романа Ксении Буржской «Литораль»

Forbes
Жестокость, доказавшая потребность в любви: неэтичный эксперимент XX века о детской привязанности Жестокость, доказавшая потребность в любви: неэтичный эксперимент XX века о детской привязанности

Как Гарри Харлоу доказал значимость эмоциональной связи ребенка с родителями

ТехИнсайдер
В диалоге с цветами В диалоге с цветами

Формы и стили, которые подчеркивают и по-новому показывают красоту цветка

Наука и жизнь
Мысли вслух Мысли вслух

Антон Лапенко: из социальных сетей в большое кино

Men Today
Из гречки и кокоса! Узнайте о самых полезных для здоровья видах муки Из гречки и кокоса! Узнайте о самых полезных для здоровья видах муки

Стоит ли заменить цельнозерновую муку на гречневую или миндальную?

ТехИнсайдер
Топ самых опасных для здоровья поз за рулем Топ самых опасных для здоровья поз за рулем

Самые опасные положения водителя в длительном путешествии на автомобиле

Maxim
Рычит, но не испепеляет: каким получился второй сезон «Дома Дракона»? Рычит, но не испепеляет: каким получился второй сезон «Дома Дракона»?

Второй сезон «Дома Дракона»: каким он получился и как обманул ожидания фанатов

Правила жизни
Фабрика-кухня: филиал Третьяковки в Самаре Фабрика-кухня: филиал Третьяковки в Самаре

Памятник советского конструктивизма обрел новую жизнь в виде филиала Третьяковки

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