🌟Чудесный алгоритм
Представьте ситуацию: вы опаздываете на встречу, прыгаете в машину, выбираете пункт назначения в навигаторе, и через полсекунды на экране появляется идеальный маршрут в обход пробок. Как ему удаётся придумать дорогу так быстро? Дело в чудесном алгоритме! ✨
👨🔬 Навигатор не перебирает все варианты пути на свете. Вместо этого, он работает по алгоритму, который изобрёл еще в 1956 году голландский ученый Эдсгер Вибе Дейкстра.
Немного условностей
Набору проводов и плат (так назваемому компьютеру) трудно даётся вообразить что такое город. Чтобы донести это понятие до нерадивого ученика, программисты еще сильнее его упростили — сжали карту до схемы, которую математики называют граф.
Представим его как сеть из колышков и ниточек.
📌Колышки — перекрестки, площади или станции метро. Иначе говоря, точки, в которых можно изменить направление
🦙 Ниточки — дороги между ними.
🌏 Длина ниточки (или её «вес») — это время, которое вы потратите на прохождение этого участка. В случае, если на дороге глухая пробка, ниточка в глазах навигатора становится длиннее (не 5 единиц веса, а 40).
Задача навигатора — найти самый короткий по времени путь от колышка Дом до колышка Работа.
😴 Если бы мы искали путь вручную, пришлось бы перебирать все варианты подряд. Но ведь дорог миллионы, компьютер бы намертво завис! Дейкстра придумал интересный трюк. Используя алгоритм, мы не гадаем, а расширяем зону видимости шаг за шагом.
🚘 Представьте, что вы стоите на старте, а в ваших руках находится блокнот. Возле каждого перекрестка (колышка) в городе мы вешаем табличку со временем, за которое мы до них доберёмся. В самом начале на всех табличках написано бесконечность, потому что мы там еще не были. А на старте — 0 минут.
Осматриваемся вокруг
Мы стоим на стартовой точке. Из неё ведут три дороги:
1. К точке А (ехать 5 минут)
2. К точке Б (ехать 10 минут)
3. К точке В (ехать 25 минут)
🗒 Навигатор записывает в свой блокнот эти ориентиры. Теперь он знает: до А можно доехать за 5 минут, до Б — за 10. Точка В пока кажется сли-и-ишком долгой...
🔮 Чудесный алгоритм очень последователен: он всегда продолжает путь из той точки, до которой уже сейчас добраться быстрее всего. Наш лидер — точка А (всего 5 минут).
Мы мысленно «переходим» в точку А. И смотрим, куда можно поехать оттуда. Допустим, из точки А можно доехать до финиша за 15 минут. Навигатор складывает время: 5 минут до А + 15 минут до финиша = 20 минут. Он записывает этот маршрут как рабочий.
❗ И на этом навигатор не успокаивается. Он возвращается к точке Б, до которой было 10 минут. Вдруг от неё до финиша всего 2 минуты? Он проверяет дорогу от Б. Оказывается, от Б до финиша ехать 15 минут. Итого: 10 + 15 = 25! Это дольше, чем через точку А. Навигатор вычеркивает этот путь.
✨ Навигатор, как наступающая вода, планомерно заполняет собой все ближайшие перекрестки. Ни за какие шиши он не пойдет проверять глухие переулки, если у него под носом есть быстрый вариант. Как только "вода" добирается до финиша кратчайшим путем — расчет окончен. ✨
Конечно, и этот алгоритм не безупречен... Вода ведь течёт во все стороны сразу! 🌊
Так называемый нюанс
😁 Если вам нужно доехать из Москвы в Санкт-Петербург, алгоритм Дейкстры начнёт проверять дороги не только на север, но и на юг, и на восток и на запад!! Он будет затапливать перекрёстки в сторону Рязани и Владимира, просто потому что они находятся близко к старту. Навигатор от такого объёма вычислений знатно бы призадумался.
Поэтому в современных приложениях чистый алгоритм Дейкстры почти не используется — его докрутили и сделали умнее. Внимание на карту:
Разработчики нашли классные лазейки, чтобы не гонять компьютер попусту:
- Алгоритм A* (А-стар или А-звёздочка) Наш Дейкстра, только с компасом в руках. Сразу движется в направлении финиша (на картинке видно, как зелёная зона поиска аккуратно вытягивается в сторону цели).
- Двунаправленный поиск: Вода пускается одновременно из Дома и из Работы навстречу друг другу. Как только два потока встретились посередине — идеальный маршрут готов! Круто экономит время.
- Жадный алгоритм (Greedy): Самый торопливый. Не думает наперёд. На каждом перекрёстке выбирает ту дорогу, которая физически ближе всего ведёт к финишу. Быстро, но часто заводит в тупики.
Вместо послесловия
❤ Каждый раз, когда навигатор за долю секунды перестраивает вам маршрут из-за внезапной аварии впереди, знайте: под капотом вашего смартфона бьются алгоритмы.
Они спорят, считают, заливают виртуальные улицы и складывают миллионы чисел в секунду — и всё это только для того, чтобы вы успели на свидание, важную встречу или приехали домой на 5 минут раньше.
Делитесь в комментариях своими историями: заводил ли вас телефон в глушь или, наоборот, спасал от пробок? 👇
#технологии #интересныефакты #смартфоны #авто #автомобилистам #яндекснавигатор #программирование #it #наука