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

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

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

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

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

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

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

Что такое Песах, чем он отличается от Пасхи и при чем тут маца и кровь? Что такое Песах, чем он отличается от Пасхи и при чем тут маца и кровь?

Что там у иудеев с Песахом? Сейчас расскажем.

Maxim
Уголок школьника Уголок школьника

5 вещей и предметов мебели, которые нужно выбросить из детской комнаты

Лиза
История разводов в России История разводов в России

Как в Древней Руси избавлялись от неверных мужей и жен?

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

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

Лиза
Из кожуры арбуза сделали ион-селективные мембраны Из кожуры арбуза сделали ион-селективные мембраны

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

N+1
Как думает ChatGPT: эмбеддинг, токены и другая невидимая «начинка» нейросети Как думает ChatGPT: эмбеддинг, токены и другая невидимая «начинка» нейросети

Как на самом деле ИИ понимает человека и что помогает ему формулировать мысли

ТехИнсайдер
Нейросеть меняет профессию Нейросеть меняет профессию

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

РБК
Живейшее из искусств Живейшее из искусств

«Комната 999»: кинорежиссеры рассуждают о судьбе кино

Weekend
Как выбрать аккумуляторную цепную пилу для дачи: практичные советы Как выбрать аккумуляторную цепную пилу для дачи: практичные советы

Что учитывать, выбирая цепную пилу?

CHIP
От Билибина до «Кандинского»: заменит ли нейросеть художников-иллюстраторов От Билибина до «Кандинского»: заменит ли нейросеть художников-иллюстраторов

Что такое вирусная обложка и стоит ли отдавать работу художника нейросети?

СНОБ
Будущее из розетки: чего ждать от электромобилей Будущее из розетки: чего ждать от электромобилей

В каком направлении развивается электротранспорт?

ТехИнсайдер
Весь в отца: существуют ли гены лишнего веса и что с ними делать? Весь в отца: существуют ли гены лишнего веса и что с ними делать?

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

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

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

Inc.
Эксперт рассказал, как меньше пьянеть! Факты о толерантности к алкоголю Эксперт рассказал, как меньше пьянеть! Факты о толерантности к алкоголю

Почему одни люди могут выпить больше других?

ТехИнсайдер
Как убедиться, что фотографии действительно удалены с телефона Как убедиться, что фотографии действительно удалены с телефона

Как сделать так, чтобы личные фотографии не вернулись из цифровой могилы

ТехИнсайдер
Как растет взаимодействие с Китаем Как растет взаимодействие с Китаем

Китай и Россия на фоне западных санкций стали друг для друга выгодными

РБК
Юла: кручу-верчу Юла: кручу-верчу

Яркая и шумная юла уже много веков веселит малышню в российских домах

КАНТРИ Русская азбука
Нейтроны нарушили неравенство Леггетта — Гарга Нейтроны нарушили неравенство Леггетта — Гарга

Нейтроны подтвердили свою квантовую природу

N+1
Как измерить силу своих чувств: шкала Клода Штайнера Как измерить силу своих чувств: шкала Клода Штайнера

Можете ли вы описать, что вы чувствуете прямо сейчас?

Psychologies
Дофамин и его предшественник леводопа усилили деградацию бета-амилоида в префронтальной коре мышей Дофамин и его предшественник леводопа усилили деградацию бета-амилоида в префронтальной коре мышей

Дофамин и леводопа индуцируют деградацию бета-амилоида в мозге мышей

N+1
«Познавая боль: история ощущений, эмоций и опыта» «Познавая боль: история ощущений, эмоций и опыта»

Как ученые пытались измерить боль

N+1
Скажем истерике «нет» Скажем истерике «нет»

Как реагировать на детскую истерику?

Лиза
Вот почему это самая умная собака в мире! Интересные факты о дрессировке Вот почему это самая умная собака в мире! Интересные факты о дрессировке

Бордер-колли по кличке Чейзер стала известной как «самая умная собака в мире»

ТехИнсайдер
Как появилась любовь с точки зрения эволюции: мнение биолога Ирины Якутенко Как появилась любовь с точки зрения эволюции: мнение биолога Ирины Якутенко

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

Psychologies
15 модных словечек и фраз, которые стоит позаимствовать из словаря зумеров 15 модных словечек и фраз, которые стоит позаимствовать из словаря зумеров

Разбираем зумерский сленг, чтобы найти с ними общий язык

Psychologies
Солнечный коллектор vs солнечная панель: как определить, что выгоднее для дома Солнечный коллектор vs солнечная панель: как определить, что выгоднее для дома

Что из них выгоднее и чем отличаются: солнечный коллектор или солнечная панель?

ТехИнсайдер
Грипповой эксперимент Грипповой эксперимент

«Идеальный лжец»: карантин и классовые отношения

Weekend
5 ошибок, которые мешают вам копить деньги 5 ошибок, которые мешают вам копить деньги

Почему у вас не получается накопить сумму на мечту?

Psychologies
Имел несчастие быть немцем… Имел несчастие быть немцем…

Кто такой был Эрнст Иоганн Бирон и как он был связан с Анной Иоанновной?

Дилетант
Сухбат Афлатуни: «Катехон». Фрагмент из романа-головоломки Сухбат Афлатуни: «Катехон». Фрагмент из романа-головоломки

Глава из «Катехона» — истории любви и хроники жизни от Сухбата Афлатуни

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