tgoop.com/practicum_math/572
Last Update:
🚖 «Геометрия таксиста»
Представьте, что вы — таксист на Манхэттене, острове с идеальной сеткой улиц. У вас срочный заказ: нужно доехать от точки A до точки Б. Как навигатор поймет, какой путь — оптимальный?
По евклидовой геометрии, которую мы все учили в школе, кратчайший путь — это прямая линия. Но в «геометрии таксиста», или «метрике Манхэттена», такая линия почти бесполезна, ведь такси не умеет ездить сквозь здания. В этой системе расстояние между двумя точками считается не по формуле Пифагора, как в евклидовой геометрии, а, грубо говоря, по количеству улиц, которые нужно проехать.
При этом в «геометрии таксиста» может быть не один, а несколько кратчайших маршрутов из точки А в точку Б. Можно менять порядок движений по горизонтали и вертикали (если мы смотрим на карту города в виде сетки), выбирать разные дороги и всё равно доехать с минимальными временными затратами.
Если город устроен примерно как Манхэттен, навигатор использует алгоритм, в основе которого — именно такая система. Но сразу скажем, здесь мы сильно упрощаем. Все-таки работа навигаторов — очень сложная тема.
Где применяют «геометрию таксиста» помимо навигаторов?
А еще многие современные дата-центры строятся по топологиям вроде Fat-Tree или Torus, где серверы связаны сеткой коммутаторов. Пакеты данных не могут «двигаться» по диагонали, а пересылаются от узла к узлу по горизонтали и вертикали — прямо как в «геометрии таксиста».
Вот так, геометрия повлияла на города, а города — на геометрию
А для тех, кто хочет немного углубиться в тему, собрали полезные ссылки:
#как_устроено
