МАТЕМАТИКА В ЖИЗНИ ✊

Ждали? Традиционная рубрика! Сегодня на повестке - задача коммивояжера!

Давай представим, что ты - курьерыч 🤨, который стартует из красной точки (см. рисунок). Тебе нужно посетить все фиолетовые точки, доставить заказы и вернуться в красную. Ясен пень ты хочешь потратить как можно меньше времени и сил, поэтому тебе нужно найти наикротчайший маршрут между ними.

Черные прямые - ребра, которые соединяют все нужные нам точки. Допустим, мы на вертолете (чтобы упростить задачу). Какой путь будет наикратчайшим?

Сколько у нас вариантов маршрута можешь написать в комментариях) Подскажу, что из точки 1 мы можем пойти в 2, 3, 4, 5. Из каждой последней мы можем пойти в другие 3 точки, далее в следующие 2 и тд. Можно воспользоваться банальным перебором и просчитать все варианты маршрутов, тем самым выбрать оптимальный. Задача не такая уж и сложная.

Но для серьезных компаний, которые занимаются, например, грузоперевозками, задача уровня МОЕ ПОЧТЕНИЕ! Представь, что таких точек в масштабах РФ хотя бы 20. Тогда вариантов перебора уже 19! Для решения подобных задач используется нехилый математический аппарат, о котором ты узнаешь на втором курсе университета

Кстати, эта задача еще решается с помощью прогича. В 2015 проблему коммивояжера решали для 24 727 пабов Великобритании (видно хотели посетить все😄) на протяжении 10 месяцев! Нашли наиболее оптимальный маршрут и доказали, что короче не существует. Линия оказалась длиной 45 495 239 метров.

Телеграм Чайки | Бесплатная летняя школа ☀️