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

---

执照

该项目在麻省理工学院之下。请参阅此处以获取更多信息。

---