日常生活における数学：衛星ナビゲータ

衛星ナビゲーターは確かに非常に一般的なツールであり、その操作は単に「道を示す」衛星からの情報を受信することであると考えられることがよくあります。 実際には、任意の目的地に到達するためのルートを確立する能力は、さまざまな手法の組み合わせの結果です。これは、現在の場所を正確に特定する能力、正確で更新されたロードマップの可用性、およびとりわけ、目的地に到達するための最適なルートを計算する機能。 この記事では、この最後の点に注目し、この計算の基礎には非常に正確な数学的理論があることを説明します。グラフ理論「これにより、XNUMX点間の最短経路を特定する方法を理解できます。 実際には、抽象的な科学的概念がどのように実用的、現実的、そして何よりも非常に有用なオブジェクトの基礎になることがわかります。

まず、下から始めましょう。グラフとは何ですか？

実際には、相互に接続された要素のセットにすぎません。各要素は「ノード」と呼ばれ、接続は「アーク」と呼ばれます。 グラフの例は、高速道路ネットワークを介して接続された一連の都市を要素として持つものです。この場合、ノードは都市であり、アークは都市間の高速道路セグメントです。 グラフは、線（円弧）で接続された一連の色付きのボールまたは円（ノード）として想像できます。 アークは方向付けすることも方向付けしないこともできます。方向付けられたアークは、開始ノードから到着ノードへの通過のみを許可するものです（逆も同様です）。 無向アーチは、両方向の通過を可能にするものです。 ナビゲーターの例では、道路は一方通行の場合は方向付けられた円弧と見なすことができますが、双方向の場合は無向アーチと見なすことができます。

重みと呼ばれる値が各アークに関連付けられている場合、グラフは重み付きであると言われます。 この値は通常、正または負になります。 前の都市と高速道路の例を参照すると、各高速道路セクションをその長さ（キロメートル）に関連付けることにより、加重グラフを取得できます。 グラフでは、理論的には、さまざまなアークを使用して、ノードAからノードBにさまざまな方法で移動できます。実際には、さまざまな道路を使用して、ある都市から別の都市に移動できます。 次に、「最短パス」を「最短方法」と呼び、ノードAをノードBに接続します。

私たちの衛星ナビゲーターの場合、始点と終点の間のパスを見つけることは、グラフ内の最短パスを見つけることと同じです。 グラフの数学的理論では、最短経路の計算の問題があらゆる観点から研究および分析されており、多くのアルゴリズムが作成されています。 たとえば、最も使用されているもののXNUMXつは Dijkstraのアルゴリズム、しかし他にもたくさんあります。 したがって、最も適切と思われるアルゴリズムを選択するのはブラウザの製造元の選択です。 この選択では、特に非常に複雑なロードマップで計算を実行する場合、XNUMXつのノード間の最短パスの検索の背後にある理論が非常に複雑になる可能性があることを確実に考慮する必要があります。 たとえば、各ノードの「統計的推定」を使用して最短パスを検索するA *アルゴリズムが開発されました。 「難しい言葉」で言えば、この見積もりは、最終目的地に向かう途中で、あるノードを別のノードよりも通過することの利点の事前評価を表しています。 いずれにせよ、アルゴリズムの詳細に入るのはやや複雑になり、特定の知識が必要になります。 いずれにせよ、問題の基本的なビジョンを提供し、おそらく日常生活に多くの実際的な意味を持つ数学理論への関心を刺激したことを願っています。

ジョン・キャルセラーノ