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

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

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

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

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

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

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

Мухи вредные и полезные Мухи вредные и полезные

Насекомые — это как бы параллельный мир, окружающий нас повсюду

Наука и жизнь
Как все успевать без спешки: китайский рецепт Как все успевать без спешки: китайский рецепт

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

Psychologies
Несущая смерть Несущая смерть

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

Вокруг света
Женский взгляд: 10 красных флагов в дейтинг-приложениях Женский взгляд: 10 красных флагов в дейтинг-приложениях

Десять стоп-сигналов, которые говорят женщинам: «Не стоит ему отвечать»

Psychologies
Как Николо Макиавелли рассуждал о природе власти Как Николо Макиавелли рассуждал о природе власти

Отрывок из книги «Никколо Макиавелли. Стяжать власть, не стяжать славу»

СНОБ
Что будет, если молния попадет в автомобиль? Что будет, если молния попадет в автомобиль?

Чем грозит разряд электричества небесной канцелярии машине и водителю.

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

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

ТехИнсайдер
Светятся в темноте и разрушают сперматозоиды! Вот какие бывают презервативы: интересные факты Светятся в темноте и разрушают сперматозоиды! Вот какие бывают презервативы: интересные факты

Существует множество видов презерватива, у каждого типа есть свои плюсы и минусы

ТехИнсайдер
Сталкер, топор и подземные боги: Игорь Яковенкo выпустил языческий альбом «Пантеон» Сталкер, топор и подземные боги: Игорь Яковенкo выпустил языческий альбом «Пантеон»

Композитор Игорь Яковенко и барабанщик Петр Ившин выпускают альбом «Пантеон»

СНОБ
Будем жить Будем жить

Города, каких не видывал мир

Men Today
Фридрих великий Фридрих великий

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

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

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

Лиза
Уйти в айти Уйти в айти

7 востребованных IT-профессий, которые можно освоить, даже если ты гуманитарий

Лиза
ММОМА: новый формат музея ММОМА: новый формат музея

Как музей ММОМА меняет подход к современным музеям?

Psychologies
Отдел замученных поэтесс: самые популярные новые женские музыкальные альбомы Отдел замученных поэтесс: самые популярные новые женские музыкальные альбомы

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

Forbes
Термоэрозия мерзлоты помешает Северному ледовитому океану поглощать углекислый газ Термоэрозия мерзлоты помешает Северному ледовитому океану поглощать углекислый газ

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

N+1
10 признаков того, что вы недостаточно заботитесь о себе 10 признаков того, что вы недостаточно заботитесь о себе

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

Psychologies
Владимир Грамматиков: «Меня всегда узнавали по маленькой роли в «Осеннем марафоне» Владимир Грамматиков: «Меня всегда узнавали по маленькой роли в «Осеннем марафоне»

Я не делаю ничего против собственного желания, причем уже давно

Караван историй
Урал, любовь моя Урал, любовь моя

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

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

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

Psychologies
Почему принято пить коровье молоко? Вот что нужно знать о любимом напитке! Почему принято пить коровье молоко? Вот что нужно знать о любимом напитке!

Почему люди выбрали именно коровье молоко около 9000 лет назад?

ТехИнсайдер
Жизнь на Земле была сложной уже 2 миллиарда лет назад Жизнь на Земле была сложной уже 2 миллиарда лет назад

Сложные организмы появились не позднее 2,1 миллиарда лет назад

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

Ученые составили карту нижней стороны шельфового ледника Дотсон в Антарктиде

ТехИнсайдер
Вопрос века Вопрос века

Как правильно ухаживать за кожей вокруг глаз, чтобы не было «вековых» проблем?

Лиза
С чистого листа С чистого листа

Основные возрастные кризисы, которые случаются в жизни почти каждой женщины

Лиза
Прочистить чакру и обновить ауру: почему мы верим в сомнительные методы помощи Прочистить чакру и обновить ауру: почему мы верим в сомнительные методы помощи

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

Psychologies
Что делать, чтобы на одежде перестали образовываться катышки: эти трюки должен знать каждый Что делать, чтобы на одежде перестали образовываться катышки: эти трюки должен знать каждый

Правильный уход за вещами поможет предотвратить появление катышек

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

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

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

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

ТехИнсайдер
Как быстро отмыть терку: пять проверенных временем методов Как быстро отмыть терку: пять проверенных временем методов

Бытовые хитрости: как быстро отмыть терку и не повредить губку?

ТехИнсайдер
Открыть в приложении