a star algorithm

算法A*

在

• 貪婪算法
• 它發現最小的路徑超級有效。
• 它需要定義啟發式函數h（x），該函數低估了頂點XEO頂點目標之間的距離。
• A*背後的想法是將圖形變成樹
• 樹的根是原點節點
• 該樹將從其葉子（首先僅是原始節點）延伸的，使用圖作為參考
• 不會擴大所有可能性，只有那些看起來更有前途的可能性

---

？怎麼知道有可能有希望的？

• 通過函數f（x）= g（x） + h（x）
  • 這是一個啟發式功能
    • g（x）是到達x節點的成本
    • h（x）是估計下一個節點成本的啟發式功能
  • 我們始終查看擴展樹的可能性併計算F（x）的值
    • 我們添加了我們發現的節點最小的f（x）

---

• OA*是圖形中最小方法的最有效算法
• 但是，這是嚴重的限制
  • 有必要定義可接受的h（x）：它永遠不會返回一個大於x到y的實際距離的值
  • 如果H（x）是可以接受的，但太低估了實際距離，則該算法效率非常低。如果H（x）不可允許，則該算法可能找不到最小方法

---

？複雜

• 複雜性直接取決於所使用的函數h（x）。
• 在最壞的情況下，探索的節點的量在最小路徑的大小中是指數的，但是如果H ∗（x）-h（x）≤o（logh ∗（x）），則具有多項式複雜性。

---

？什麼時候使用好？

• 圖表可以低估兩個頂點之間的距離，如圖
• 兩點之間的最短距離是一條線，但實際距離可能大於

---

？在這種情況下，最小方法是什麼？

---

執行項目

結果

---

‍作者

Bia Chacon

---

執照

該項目在麻省理工學院之下。請參閱此處以獲取更多信息。

---