Математика в повседневной жизни: спутниковый навигатор
Спутниковый навигатор, безусловно, является очень широко используемым инструментом, и часто предполагается, что его функция заключается просто в получении информации от спутников, которые «указывают путь». В действительности, его способность прокладывать маршрут для достижения любого пункта назначения является результатом сочетания различных методов, которые касаются способности точно определять точку, в которой мы находимся в любой момент, наличия точных и обновленных дорожных карт и Прежде всего, способность рассчитать лучший маршрут, чтобы добраться до пункта назначения. В этой статье мы сосредоточим наше внимание на этом последнем пункте, объяснив, что в основе этого расчета лежит очень специфическая математическая теория,теория графов», что позволяет нам понять, как можно определить кратчайший путь между двумя точками. На практике мы видим, как абстрактное научное понятие становится основой практического, реального и прежде всего очень полезного объекта.
Для начала начнем снизу: что такое график?
На самом деле это не что иное, как набор связанных друг с другом элементов: каждый из элементов называется «узлом», а соединения — «дугами». Примером графа является граф, элементами которого являются серии городов, соединенных друг с другом сетью автомагистралей: в этом случае узлами являются города, а дугами — сегменты автомагистралей между самими городами. Мы можем представить граф как серию цветных шариков или кругов (узлов), соединенных друг с другом линиями (дугами). Дуга может быть ориентированной и неориентированной: ориентированной является дуга, допускающая переход только от начального узла к узлу прибытия (а не наоборот); неориентированная арка — это арка, позволяющая проход в обоих направлениях. В нашем примере с навигатором дорогу можно считать направленной дугой, если она односторонняя, и ненаправленной дугой, если она двусторонняя.
Граф называется взвешенным, если каждой дуге соответствует значение, называемое весом. Это значение может быть, как правило, положительным или отрицательным. Обращаясь к предыдущему примеру с городами и автомагистралями, мы можем получить взвешенный график, связав каждый участок автомагистрали с его длиной в километрах. В графе теоретически можно пройти от узла А к узлу Б несколькими разными способами, используя разные дуги, так же как в реальности можно пройти из одного города в другой по разным дорогам. Затем мы назовем «кратчайший путь» для соединения узла A с узлом B «кратчайшим путем».
Для нашего спутникового навигатора поиск пути между начальной точкой и точкой прибытия эквивалентен поиску кратчайшего пути на графике. В математической теории графов проблема вычисления кратчайшего пути изучалась и анализировалась со всех точек зрения, было создано множество алгоритмов. Одним из наиболее часто используемых, например, является Алгоритм Дейкстры, но есть и много других. Поэтому производитель навигатора должен выбрать алгоритм, который он считает наиболее подходящим. При таком выборе, безусловно, стоит учитывать, что теория, лежащая в основе поиска кратчайшего пути между двумя узлами, может быть очень сложной, особенно если речь идет о проведении расчетов на очень сложных дорожных картах. Например, был разработан алгоритм A*, который ищет кратчайший путь, используя «статистическую оценку» для каждого узла; говоря «трудными словами», эта оценка представляет собой априорную оценку преимущества прохождения одного узла над другим на пути к конечному пункту назначения. В любом случае, вникновение в детали алгоритмов становится довольно сложным и требует специальных знаний; В любом случае мы надеемся, что предоставили базовое видение проблемы и, возможно, стимулировали интерес к математической теории, имеющей множество практических последствий в повседневной жизни.
Джон Калсерано