🚖 «Геометрия таксиста»

❓Почему путь по прямой — не обязательно самый короткий, и как это используют навигаторы?

Представьте, что вы — таксист на Манхэттене, острове с идеальной сеткой улиц. У вас срочный заказ: нужно доехать от точки A до точки Б. Как навигатор поймет, какой путь — оптимальный?

По евклидовой геометрии, которую мы все учили в школе, кратчайший путь — это прямая линия. Но в «геометрии таксиста», или «метрике Манхэттена», такая линия почти бесполезна, ведь такси не умеет ездить сквозь здания. В этой системе расстояние между двумя точками считается не по формуле Пифагора, как в евклидовой геометрии, а, грубо говоря, по количеству улиц, которые нужно проехать.

При этом в «геометрии таксиста» может быть не один, а несколько кратчайших маршрутов из точки А в точку Б. Можно менять порядок движений по горизонтали и вертикали (если мы смотрим на карту города в виде сетки), выбирать разные дороги и всё равно доехать с минимальными временными затратами.

Если город устроен примерно как Манхэттен, навигатор использует алгоритм, в основе которого — именно такая система. Но сразу скажем, здесь мы сильно упрощаем. Все-таки работа навигаторов — очень сложная тема.

Где применяют «геометрию таксиста» помимо навигаторов?
🔴 В маршрутизации сетевого трафика.
🔴 Логистике.
🔴 Геймдеве.
🔴 Обработке изображений.
🔴 И даже в шахматах. Ход ладьи — чистая метрика таксиста!

А еще многие современные дата-центры строятся по топологиям вроде Fat-Tree или Torus, где серверы связаны сеткой коммутаторов. Пакеты данных не могут «двигаться» по диагонали, а пересылаются от узла к узлу по горизонтали и вертикали — прямо как в «геометрии таксиста».

Вот так, геометрия повлияла на города, а города — на геометрию ↔️

А для тех, кто хочет немного углубиться в тему, собрали полезные ссылки:
➡️ Введение в «геометрию таксиста»
➡️ Про параболы и гиперболы в «геометрии таксиста»
➡️ Сайт, где можно попробовать построить «эллипсы таксиста»
➡️ Наглядная демонстрация «геометрии таксиста» в Wolfram

#как_устроено