日常生活中的數學：衛星導航儀

衛星導航儀無疑是一種非常常用的工具，人們通常認為它的功能只是接收來自“指路”衛星的信息。 事實上，它建立到達任何目的地的路線的能力是不同技術組合的結果，這些技術涉及隨時精確識別我們所處地點的能力、準確和更新的路線圖的可用性以及最重要的是，能夠計算到達目的地的最佳路線。 在本文中，我們將把注意力集中在最後一點上，解釋在這個計算的基礎上有一個非常具體的數學理論，“圖論”這使我們能夠了解如何確定兩點之間的最短路徑。 在實踐中，我們看到抽象的科學概念如何成為實際、真實且最重要的是非常有用的對象的基礎。

首先，我們從最底層開始：什麼是圖表？

實際上，它無非是一組相互連接的元素：每個元素稱為“節點”，連接稱為“弧”。 一個圖的例子是，其元素是一系列通過高速公路網絡相互連接的城市：在這種情況下，節點是城市，弧線是城市本身之間的高速公路路段。 我們可以將圖形想像為一系列通過線（弧）相互連接的彩色球或圓（節點）。 弧可以是有向的，也可以是無向的：有向弧是指只允許從起始節點到到達節點的通道（反之亦然）； 無方向的拱門是一種允許雙向通行的拱門。 在我們的導航器示例中，如果一條道路是單向的，則可以將其視為有向弧；如果是雙向的，則可以將其視為無向弧。

如果每個弧都與一個稱為權重的值相關聯，則稱該圖是加權的。 一般來說，該值可以是正值或負值。 參考前面的城市和高速公路示例，我們可以通過將每條高速公路段與其長度（以公里為單位）相關聯來獲得加權圖。 在圖中，理論上可以使用不同的弧以多種不同的方式從節點 A 到達節點 B，就像現實中可以使用不同的道路從一個城市到達另一個城市一樣。 然後，我們將連接節點 A 到節點 B 的“最短路徑”稱為“最短路徑”。

對於我們的衛星導航儀來說，找到起點和到達點之間的路徑相當於找到圖中的最短路徑。 在圖的數學理論中，對計算最短路徑的問題從各個角度進行了研究和分析，並產生了很多算法。 例如，最常用的之一是 迪傑斯特拉算法，但還有很多其他的。 因此，導航儀製造商應選擇他認為最合適的算法。 在這種選擇中，當然值得考慮的是，搜索兩個節點之間最短路徑的理論可能非常複雜，特別是在非常複雜的路線圖上進行計算時。 例如，A*算法已經被開發出來，它使用每個節點的“統計估計”來搜索最短路徑； 用“難言之隱”來說，這個估計代表了對在到達最終目的地的路徑上經過一個節點相對於另一個節點的優勢的先驗評估。 無論如何，深入研究算法的細節會變得相當複雜，並且需要特定的知識； 無論如何，我們希望能夠提供對該問題的基本看法，或許還能激發人們對在日常生活中具有許多實際意義的數學理論的興趣。

約翰Calcerano