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

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

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

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

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

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

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

Playboy в кино Playboy в кино

Playboy в кино: голливудские хиты, сошедшие со страниц легендарного журнала

Playboy
10 сложностей в отношениях, о которых молчат мужчины 10 сложностей в отношениях, о которых молчат мужчины

Какие сложности испытывают мужчины в отношениях и как с ними справиться?

Psychologies
Следите за руками: как распознать популярные жесты Следите за руками: как распознать популярные жесты

Движения рук могут подчас рассказать о человеке больше, чем слова

Psychologies
Куда вложить деньги, чтобы они работали в 2024 году? Куда вложить деньги, чтобы они работали в 2024 году?

Вопрос вложения свободных денежных средств беспокоит многих

Наука и техника
Адель Вейгель: «Не считаю, что только профессионалы должны заниматься музыкой» Адель Вейгель: «Не считаю, что только профессионалы должны заниматься музыкой»

Адель Вейгель — о том, как ей удалось залететь в топ с первой песни

ЖАРА Magazine
5 способов укрепить свой внутренний стержень 5 способов укрепить свой внутренний стержень

Как развивать внутреннюю опору, которая поможет справляться с трудностями

Psychologies
Рационализаторское предложение или изобретение: что регистрировать? Рационализаторское предложение или изобретение: что регистрировать?

Основные преимущества осуществления рационализаторской деятельности

Наука и техника
Набрать, сбросить, повторить: как актеры вынуждены менять свою внешность ради карьеры Набрать, сбросить, повторить: как актеры вынуждены менять свою внешность ради карьеры

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

Forbes
Мария Орлова: «Чтение – это в первую очередь удовольствие» Мария Орлова: «Чтение – это в первую очередь удовольствие»

Как привить ребенку любовь к чтению – не обязательно расти на классике

Grazia
Овощ в мундире Овощ в мундире

Молодой картофель – какой лучше выбрать и как приготовить?

Лиза
Цепляет с первого дня Цепляет с первого дня

Кавказ: как окружить себя принципиально другой реальностью

2Xplore
Биоритмы: что это такое, на что влияют, как наладить Биоритмы: что это такое, на что влияют, как наладить

Учимся быть чуткими к биологическим часам и разбираемся, как наладить режим

РБК
Изотопный анализ показал, как питались элита и низшие классы во Франции 1000 лет назад Изотопный анализ показал, как питались элита и низшие классы во Франции 1000 лет назад

​​​​​​​Археологи узнали средневековые диетические практики Франции

ТехИнсайдер
Список продуктов с низким гликемическим индексом: что это и зачем нужен Список продуктов с низким гликемическим индексом: что это и зачем нужен

Какие продукты имеют низкий ГИ и как правильно вводить их в рацион

РБК
От модели до CEO: как Брук Шилдс основала собственный бьюти-бренд для зрелых женщин От модели до CEO: как Брук Шилдс основала собственный бьюти-бренд для зрелых женщин

Брук Шилдс о том, как она решилась начать новую карьеру — в бизнесе

Forbes
Пять минут позора: как подготовиться к интервью на английском и перестать бояться Пять минут позора: как подготовиться к интервью на английском и перестать бояться

Как успешно пройти интервью, даже если ваш английский пока далек от идеала?

Forbes
Жестокость, доказавшая потребность в любви: неэтичный эксперимент XX века о детской привязанности Жестокость, доказавшая потребность в любви: неэтичный эксперимент XX века о детской привязанности

Как Гарри Харлоу доказал значимость эмоциональной связи ребенка с родителями

ТехИнсайдер
Утерянное человечество: кем мы станем через миллионы лет? Утерянное человечество: кем мы станем через миллионы лет?

Антиутопия, космический ужас, утопия и наука – «Все грядущие дни»

Наука и техника
Удаляют себе ногти на ногах! Вот на какие жертвы идут бегуны Канады ради победы Удаляют себе ногти на ногах! Вот на какие жертвы идут бегуны Канады ради победы

Профессиональные спортсмены подвергают свои тела экстремальным практикам

ТехИнсайдер
Аллергия на дождь! Узнайте факты о необычной болезни: аквагенная крапивница Аллергия на дождь! Узнайте факты о необычной болезни: аквагенная крапивница

Аквагенная крапивница: что это за заболевание и как она влияет на жизнь человека

ТехИнсайдер
Письмена доколумбовой Америки Письмена доколумбовой Америки

Системы письма у майя, ацтеков, мештеков и инков

Знание – сила
Новая смена Новая смена

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

Лиза
Уголок школьника Уголок школьника

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

Лиза
Нанимать мигрантов станут по-новому: как изменится рынок труда в России Нанимать мигрантов станут по-новому: как изменится рынок труда в России

Процедура найма мигрантов может измениться в сторону ужесточения

ФедералПресс
Без перегрузок Без перегрузок

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

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

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

СНОБ
«Бесконечная смоляная мгла»: роман об алкогольной зависимости посреди полярной ночи «Бесконечная смоляная мгла»: роман об алкогольной зависимости посреди полярной ночи

Отрывок из романа Ксении Буржской «Литораль»

Forbes
Инвазивные змеи на Гуаме не смогли проглотить половину убитых птиц Инвазивные змеи на Гуаме не смогли проглотить половину убитых птиц

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

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

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

ТехИнсайдер
«Это ЗИЛ?!» Как советские инженеры изобретали совершенный вездеход «Это ЗИЛ?!» Как советские инженеры изобретали совершенный вездеход

Машины, по проходимости которым не было бы равных

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