Python 中 A* 算法及代码实例_用python编写一个简单的a*搜索算法

什么是 A* 算法？

A* 是最受欢迎的寻路选择，因为它相当灵活，可以在各种环境中使用。
它是一种人工智能算法，用于查找从开始到结束状态的最短路径。
它可以应用于角色路径查找、解谜等等。它确实有无数的应用。
斯坦福研究所（现为SRI International）的Peter Hart、Nils Nilsson和Bertram Raphael于1968年首次发表了该算法。
A* 算法同时使用从起点到起点的实际距离和到目标的估计距离。
它是如何工作的？
现在让我们看看 A* 算法是如何工作的。它基于以下概念——

计划从哪里开始，它的目标是从哪里开始。
如何衡量实现目标的进展。
如何生成子项或所有可能的解决方案路径。
在其主循环的每次迭代中，A* 需要确定要扩展的路径。它基于路径的成本和对将路径一直延伸到目标所需的成本的估计来执行此操作。具体而言，A* 选择最小化的路径

f(n)=g(n)+h(n)

n = 路径上的下一个节点

g（n） = 从起始节点到 n 的路径成本

h（n） = 一个启发式函数，用于估计从 n 到目标的最便宜路径的成本

A* 算法
现在您将看到 A* 算法的算法。
创建基类
首先，从队列中导入 PriorityQueue。然后你必须定义一个名为 State 或任何你想要的类。此类基本上是基类。

创建子类
现在我们将创建一个子类，其中包含两个方法 GetDistance（） 和 CreateChildren（ ） 方法。因此，请编写以下代码。

创建A_Star_Solver子类
现在我们将创建一个真正神奇的类。因此，让我们编写以下代码

创建 Main 函数
现在，我们将创建一个最终代码，它实际上调用了所有存在的东西。因此，请编写以下代码。

A* 算法 Python 完整程序