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

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 комиксов и графических романов, которые понравятся всем

5 комиксов о природе, смыслах и самопознании

Правила жизни
Цена ошибки — сорняк: зачем в СССР сажали борщевик и что из этого получилось Цена ошибки — сорняк: зачем в СССР сажали борщевик и что из этого получилось

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

ТехИнсайдер
LADA Niva Legend. Между прошлым и будущим LADA Niva Legend. Между прошлым и будущим

Классическая «Нива» по-прежнему в строю

4x4 Club
Худеем по науке Худеем по науке

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

Лиза
Версия для печати: скоро ли 3D-принтеры соберут человека по частям Версия для печати: скоро ли 3D-принтеры соберут человека по частям

Первые пациенты с 3D-имплантатами уже живут среди нас

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

«Большой скачок»: зачем Китай решил истребить воробьев?

ТехИнсайдер
Смерть самурая Смерть самурая

Лучший фильм, чтобы проститься с Аленом Делоном

Weekend
Весь в отца: существуют ли гены лишнего веса и что с ними делать? Весь в отца: существуют ли гены лишнего веса и что с ними делать?

Спросили у эксперта все, что вы хотели знать о генах лишнего веса

Правила жизни
Опытным путем Опытным путем

20 советов, которые помогут изменить жизнь к лучшему

Men Today
Денег нет, но я держусь: как психологически справиться с финансовым кризисом Денег нет, но я держусь: как психологически справиться с финансовым кризисом

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

VOICE
Мёд всему голова Мёд всему голова

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

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

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

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

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

Караван историй
Ряженка: не путать с кефиром! Ряженка: не путать с кефиром!

Ряженка — продукт, которого больше нигде нет — ни на Востоке, ни на Западе

КАНТРИ Русская азбука
Зеленая скульптура Зеленая скульптура

Учимся создавать топиари с помощью фигурной стрижки растений

Лиза
Хайям Аминов: «Наша задача — изучить всю Енисейскую Сибирь» Хайям Аминов: «Наша задача — изучить всю Енисейскую Сибирь»

Хайям Аминов о карьере, бизнесе, сибирских продуктах и душе

Bones
365 дней свеклы 365 дней свеклы

Мы с командой часто смеемся, называя сибирских поваров «амбассадорами свеклы»

Bones
«Никто не идеален»: 5 шагов, чтобы избавиться от недостатков «Никто не идеален»: 5 шагов, чтобы избавиться от недостатков

Признание своих недостатков — первый шаг к изменениям

Psychologies
Легендарная вещь времен СССР: почему у граненого стакана было именно 16 граней Легендарная вещь времен СССР: почему у граненого стакана было именно 16 граней

Как и когда в СССР появился граненый стакан

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

Несколько денежных типов личности, которые определяют подход людей к деньгам

ТехИнсайдер
Ингибирование гистондеацетилазы 3 улучшило реконсолидацию памяти у старых мышей Ингибирование гистондеацетилазы 3 улучшило реконсолидацию памяти у старых мышей

Фермент гистондеацетилаза 3 участвует в реконсолидации памяти

N+1
Почему нам нравится сериал «Эмили в Париже» и чего ожидать от выхода 4-го сезона Почему нам нравится сериал «Эмили в Париже» и чего ожидать от выхода 4-го сезона

Как «Эмили в Париже» приковывает нас к экрану?

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

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

Forbes
На средневековых предметах и росписях из Китая нашли желтые краски из растений На средневековых предметах и росписях из Китая нашли желтые краски из растений

В средневековом Китае использовали краски из гарцинии и китайского бархата

N+1
Правила взаимности: при каких условиях деловые знакомства превращаются в бизнес-связи Правила взаимности: при каких условиях деловые знакомства превращаются в бизнес-связи

Как нетворкинг-туры помогают договариваться о выгодных контрактах и партнерствах

Forbes
Чужбина больше не интересует: как менялось мнение россиян об эмиграции Чужбина больше не интересует: как менялось мнение россиян об эмиграции

В России рекордно снизилось число граждан, желающих попытать счастье за рубежом

ФедералПресс
У пиренейского кроманьонца выявили инвагинацию зуба У пиренейского кроманьонца выявили инвагинацию зуба

Ученые исследовали 17 зубов, которые археологи нашли в слоях верхнего палеолита

N+1
11 книг, которые надо прочитать всем, кто хочет быть богатым (и кто уже богатый — тоже) 11 книг, которые надо прочитать всем, кто хочет быть богатым (и кто уже богатый — тоже)

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

Inc.
«Пойми меня, если сможешь»: как работает эмпатия и чем может помочь искусственный интеллект «Пойми меня, если сможешь»: как работает эмпатия и чем может помочь искусственный интеллект

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

Psychologies
От детей-сирот до мажоров. Как эволюционировала школьная форма в разных странах От детей-сирот до мажоров. Как эволюционировала школьная форма в разных странах

Как и где появилась школьная форма и какая она была в России

СНОБ
Открыть в приложении