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

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

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

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

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

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

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

Записки солдата Первой мировой Записки солдата Первой мировой

Нас было 45 человек, лица всех закопчены дымом и в грязи

Знание – сила
Зажечь по-семейному: 3 основные причины снижения либидо в браке и рекомендации от сексологов Зажечь по-семейному: 3 основные причины снижения либидо в браке и рекомендации от сексологов

Как вернуть влечение, распознать за угасающей искрой яркое пламя страсти?

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

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

РБК
«Швабе» о человеческом капитале: «От нашей работы с людьми зависит успех компании» «Швабе» о человеческом капитале: «От нашей работы с людьми зависит успех компании»

О том, как с непростой ситуацией кадрового голода справляется холдинг «Швабе»

ФедералПресс
«Пульс и сердце, свет в зрачки, череп, руки, ноги, разрядики тока»: отрывок из романа Дании Жанси «Путешествия Лейлы» «Пульс и сердце, свет в зрачки, череп, руки, ноги, разрядики тока»: отрывок из романа Дании Жанси «Путешествия Лейлы»

«Путешествия Лейлы» — о самоопределении, памяти и гранях «нормальности»

Правила жизни
«Должны жить по нашим законам»: как изменится миграционная политика в РФ «Должны жить по нашим законам»: как изменится миграционная политика в РФ

Адаптация мигрантов к российским реалиям остается одним из ключевых вызовов

ФедералПресс
Про тех, кто вечно в шоке Про тех, кто вечно в шоке

Что такое аффектация простыми словами, рассказывает психолог Надежда Бримаер

Лиза
«Если ко мне не будут приставать, как я пойму, чего стою?»: почему женщины зависимы от (любого) мужского внимания «Если ко мне не будут приставать, как я пойму, чего стою?»: почему женщины зависимы от (любого) мужского внимания

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

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

Сколько спонсорских контрактов заключают девушки профессиональных теннисистов

Forbes
Повышаем обороты Повышаем обороты

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

Лиза
Танцуй, танцуй! Танцуй, танцуй!

Танцы — это не только красиво, но еще и полезно для здоровья

ЖАРА Magazine
Сергей Катырин: Проблема трансграничных платежей по-прежнему актуальна Сергей Катырин: Проблема трансграничных платежей по-прежнему актуальна

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

ФедералПресс
Двигатель Renault К4М: описание и характеристики Двигатель Renault К4М: описание и характеристики

Все о двигателе K4M: надежность, особенности, характеристики

РБК
Как выстроить доверие в отношениях: 14 правил, о которых мы часто забываем Как выстроить доверие в отношениях: 14 правил, о которых мы часто забываем

Правила, которые помогут построить крепкие отношения

Psychologies
Внимание, найден внутренний ребенок Внимание, найден внутренний ребенок

Что такое эго-состояния, можно ли «включать» их в нужный момент?

Grazia
Фьюзинг: дедовский метод Фьюзинг: дедовский метод

Процесс создания красоты, «фьюзинг», — давняя и довольно традиционная технология

КАНТРИ Русская азбука
Синхронное плавание Синхронное плавание

Владимир Кристовский и его жена Ольга о вдохновении для всех, кто его ищет

Psychologies
«Поводом к травле могло стать любое слово, жест, взгляд» «Поводом к травле могло стать любое слово, жест, взгляд»

История Катерины, которая много лет страдала от пробелов в памяти после травли

Psychologies
Математика в реальной жизни: как транспортные модели помогают избавляться от пробок и строить новые маршруты Математика в реальной жизни: как транспортные модели помогают избавляться от пробок и строить новые маршруты

О том, как создаются транспортные модели и как они работают

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

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

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

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

VOICE
10 вещей, которые лучше всего чистить спиртом: мнение профессиональных клинеров 10 вещей, которые лучше всего чистить спиртом: мнение профессиональных клинеров

Что можно чистить спиртом, а что — нет?

VOICE
По следам мореплавателя По следам мореплавателя

Остров Беринга не оставляет привычных критериев для оценки действительности

2Xplore
Что вытворяют тарантулы во время стресса и какой вид смертельно опасен для человека: 50 шокирующих фактов о пауках Что вытворяют тарантулы во время стресса и какой вид смертельно опасен для человека: 50 шокирующих фактов о пауках

Пауки не только устрашающе выглядят, но и полны загадок

ТехИнсайдер
Шеф-повар Роман Киселёв: Более осознанный, индивидуальный подход к питанию — это тренд Шеф-повар Роман Киселёв: Более осознанный, индивидуальный подход к питанию — это тренд

Шеф-повар Роман Киселёв — о здоровом питании и еде будущего

СНОБ
В древнем горшке из Китая нашли остатки пищи эпохи неолита В древнем горшке из Китая нашли остатки пищи эпохи неолита

Ученые проанализировали пищевую корку в керамическом горшке из памятника Хэмуду

N+1
Гжель: сине-бело-голубые Гжель: сине-бело-голубые

Особенности производства гжельской посуды

КАНТРИ Русская азбука
Секс — мощное оружие маркетинга: жесткая диктатура длинных ног и коротких половых связей Секс — мощное оружие маркетинга: жесткая диктатура длинных ног и коротких половых связей

Почему быть сексуальным и иметь половую жизнь — это показатель престижа?

Psychologies
Целительная сила «убойного» цветка Целительная сила «убойного» цветка

За какие целебные свойства ценят зверобой?

Наука и жизнь
Ангелы прилетели Ангелы прилетели

Мастер-класс по самодельным ангелам, дарящим ощущение праздника и чудес

КАНТРИ Русская азбука
Открыть в приложении