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

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

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

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

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

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

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

8 случайно потерянных ядерных бомб 8 случайно потерянных ядерных бомб

Потерянные ядерные бомбы со времен холодной войны

Maxim
Тетёрки: насукали и жуём Тетёрки: насукали и жуём

Приготовление весенних тетерок — это всегда импровизация

КАНТРИ Русская азбука
«Разные: мужское и женское глазами приматолога» «Разные: мужское и женское глазами приматолога»

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

N+1
Крафтсмены Крафтсмены

Рыцари невидимого фронта, которые помогают делать рестораны особенными

Bones
Неистовая Фанни. Драма террористки, покусившейся на вождя Неистовая Фанни. Драма террористки, покусившейся на вождя

О том, как любовная драма превратила наивную девушку Фанни Каплан в террористку

СНОБ
Осторожно, очень горячо! Что делать, если телефон перегрелся Осторожно, очень горячо! Что делать, если телефон перегрелся

Как реанимировать смартфон после перегрева?

ТехИнсайдер
Финифть: мир в стиле мини Финифть: мир в стиле мини

Финифть — это не только женские украшения, но и портреты, пейзажи и иконы

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

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

Bones
Вино из Воронежа Вино из Воронежа

В мир вина я попал очень просто — мама была большой ценительницей

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

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

N+1
Смерть в Тегеране: как гибель лидера ХАМАС изменит ситуацию на Ближнем Востоке Смерть в Тегеране: как гибель лидера ХАМАС изменит ситуацию на Ближнем Востоке

Ликвидация лидера движения ХАМАС едва ли изменит ситуацию в секторе Газа

Forbes
Искусственный интеллект за кадром: как цифровые сотрудники меняют правила игры Искусственный интеллект за кадром: как цифровые сотрудники меняют правила игры

Кто такие цифровые сотрудники, как они влияют на бизнес?

Forbes
Золотой завтрак: как хлопья стали символом успеха для олимпийских чемпионов Золотой завтрак: как хлопья стали символом успеха для олимпийских чемпионов

Почему попасть на коробку хлопьев Wheaties — мечта многих спортсменов

Forbes
В чем секрет успеха спортсменов на Олимпиаде? Психолог олимпийской сборной Британии раскрыла секреты! В чем секрет успеха спортсменов на Олимпиаде? Психолог олимпийской сборной Британии раскрыла секреты!

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

ТехИнсайдер
Экспресс-диагностика Экспресс-диагностика

Простые тесты, которые помогут оценить здоровье и физическую форму

Лиза
Ветер с Юга дул Ветер с Юга дул

Краткая история «Унесенных ветром» в 50 пунктах

Weekend
Как твой образ влияет на успех: практические советы Как твой образ влияет на успех: практические советы

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

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

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

2Xplore
Андрей Миронов. «Он нравился. Он влюблял в себя. В нем была магия...» Андрей Миронов. «Он нравился. Он влюблял в себя. В нем была магия...»

«Быть артистом — это абсолютно его предназначение. Сцена у него затмевала все»

Коллекция. Караван историй
Тула. Город мастеров Тула. Город мастеров

Тула – здесь плелись интриги и вершились судьбы

Зеркало Мира
В диалоге с цветами В диалоге с цветами

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

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

Какая часть «Сталкера» самая лучшая и интересная: атмосфера, геймплей и графика

CHIP
Жилища обтекаемой формы: зачем в СССР строили дома в виде бочек Жилища обтекаемой формы: зачем в СССР строили дома в виде бочек

Дома-бочки в СССР: для кого строили эти дома и почему они были такой формы?

ТехИнсайдер
«Каиссе» 50: история советской компьютерной программы, победившей в чемпионате мира по шахматам «Каиссе» 50: история советской компьютерной программы, победившей в чемпионате мира по шахматам

Почему среди игр для «тренировки» искусственного интеллекта были выбраны шахматы

ТехИнсайдер
«Главный вызов — создание нового уровня жизни» «Главный вызов — создание нового уровня жизни»

Алексей Чекунков о том, как решается кадровый дефицит на Востоке

РБК
Не те герои Не те герои

Минфин планирует активно выводить на рынок акций национализированные компании

Монокль
Исповедь рэп-звезды: как фильм «Телец» показывает взлеты и падения Machine Gun Kelly Исповедь рэп-звезды: как фильм «Телец» показывает взлеты и падения Machine Gun Kelly

«Телец» — тягучая музыкальная история рэпера Колсона Бэйкера

Forbes
Она — легенда: как Сьюзен Войджицки стала ролевой моделью для многих женщин в бизнесе Она — легенда: как Сьюзен Войджицки стала ролевой моделью для многих женщин в бизнесе

Почему Войджицки была не просто легендой в технологической индустрии

Forbes
Диво дивное Диво дивное

Воронежская область — поля подсолнухов, меловые столбы и водная гладь Дона

Лиза
Старость – не данность Старость – не данность

Можно ли на самом деле хотя бы замедлить старение?

Вокруг света
Открыть в приложении