A*（A

2024-07-09 14:59| 来源: 网络整理| 查看: 265

文章目录引言定义特性基本原理及公式推导基本原理公式推导实现步骤与代码实现实现步骤Python代码代码说明代码运行结果应用案例优化和挑战挑战优化结论

引言

A*算法由Peter Hart, Nils Nilsson和Bertram Raphael在1968年提出，是解决路径搜索问题的一种启发式算法。它用于在图中找到从起始节点到目标节点的最短路径，并广泛应用于游戏设计、机器人导航等领域。

定义

A*（A-star）算法是一种在图中寻找从初始节点到目标节点最短路径的启发式搜索算法。它结合了Dijkstra算法的确保性（保证找到一条最短路径）和贪心算法的高效性（快速找到目标）。A* 算法通过评估函数 f ( n ) = g ( n ) + h ( n ) f(n) = g(n) + h(n) f(n)=g(n)+h(n) 来工作，其中 g ( n ) g(n) g(n) 是从起始点到任何顶点 n n n 的实际成本，而 h ( n ) h(n) h(n) 是从顶点 n n n 到目标的估计最低成本，通常用启发式函数来计算，这个函数需要事先设计来反映实际的地形或环境特征。理想情况下， h ( n ) h(n) h(n) 应该不会高估实际的成本，这种情况下，A* 算法保证找到一条最低成本路径。算法的性能和准确性高度依赖于启发式函数的选择。在实际应用中，A* 算法广泛应用于各类路径规划问题，如机器人导航、地图定位服务和游戏中的AI路径寻找等场景。通过适当选择和调整启发式函数，A* 算法能够在复杂的环境中有效地寻找最短路径，同时保持计算上的可行性和效率。

特性

A* 算法具有以下显著特性：

最优性：当启发式函数 h ( n ) h(n) h(n) 是可采纳的（即不会高估从任一节点到目标的成本时），A* 算法保证找到最短路径。完备性：只要有解存在，A* 算法总能找到解，前提是节点扩展没有限制且启发式函数不返回无穷大值。高效率：通过启发式函数有效指导搜索方向，A* 算法通常比其他简单的搜索算法如广度优先或深度优先搜索更快地找到最短路径。灵活性：启发式函数的选择可以根据具体的应用场景灵活调整，影响算法的效率和行为。普适性：适用于任何能够用图表示的路径搜索问题，从机器人路径规划到游戏设计中的AI挑战。适应性：能够根据实时反馈调整启发式评估，适应于动态变化的环境中。基本原理及公式推导基本原理

A*算法是一种在图中寻找从起始点到目标点最短路径的启发式搜索算法。该算法使用三个主要函数： g ( n ) g(n) g(n)， h ( n ) h(n) h(n)，和 f ( n ) f(n) f(n) 来评估路径的优劣。

g ( n ) g(n) g(n)：从起始点到任何节点 n n n 的实际路径成本。 h ( n ) h(n) h(n)：从节点 n n n 到目标的预估成本，这是一个启发式估计，通常是从 n n n 到目标的直线距离。 f ( n ) f(n) f(n)：节点 n n n 的总成本估算，计算为 f ( n ) = g ( n ) + h ( n ) f(n) = g(n) + h(n) f(n)=g(n)+h(n)。

这些评价指标共同帮助算法决定在图中的哪个方向上继续搜索，以期达到最有效的路径搜索。

公式推导

启发式函数 h ( n ) h(n) h(n) 的定义

对于网格中的点 ( x , y ) (x, y) (x,y)，若目标点是 ( x g o a l , y g o a l ) (x_{goal}, y_{goal}) (xgoal,ygoal)，一个常用的启发式是欧几里得距离：

h ( n ) = ( x − x g o a l ) 2 + ( y − y g o a l ) 2 h(n) = \sqrt{(x - x_{goal})^2 + (y - y_{goal})^2} h(n)=(x−xgoal)2+(y−ygoal)2

成本函数 g ( n ) g(n) g(n) 的计算

每当我们从起始点通过路径移动到一个新节点， g ( n ) g(n) g(n) 将累加上到达该节点的移动成本。例如，如果每步移动成本为 1，则：

g ( n n e w ) = g ( n c u r r e n t ) + 1 g(n_{new}) = g(n_{current}) + 1 g(nnew)=g(ncurrent)+1

总评价函数 f ( n ) f(n) f(n) 的计算

结合上述两个值，我们得到 f ( n ) f(n) f(n) 来评价节点的总成本，以决定哪些节点应该被优先考虑：

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

实现步骤与代码实现实现步骤

初始化：

创建起始节点和目标节点，初始化 g、h 和 f 值。创建开放列表（使用优先队列）和封闭列表，将起始节点加入开放列表。

节点处理：

从开放列表中取出 f 值最小的节点作为当前节点。检查当前节点是否为目标节点。如果是，回溯路径并返回。

邻接节点探索：

计算当前节点的四个方向的邻接节点（上、下、左、右）。对于每个邻接节点，检查是否为有效节点（即在网格范围内且不是障碍物）。

更新邻接节点：

对于每个有效的邻接节点，如果它不在封闭列表中，则计算它的 g、h 和 f 值。使用 add_to_open 函数判断是否将邻接节点添加到开放列表。

移动到封闭列表：

将当前节点移入封闭列表。如果开放列表为空，说明没有找到路径，返回失败。

重复过程：

重复步骤 2-5，直到找到目标节点或开放列表为空 Python代码 import heapq import matplotlib.pyplot as plt import numpy as np class Node: """节点类表示搜索树中的每一个点。""" def __init__(self, parent=None, position=None): self.parent = parent # 该节点的父节点 self.position = position # 节点在迷宫中的坐标位置 self.g = 0 # G值：从起点到当前节点的成本 self.h = 0 # H值：当前节点到目标点的估计成本 self.f = 0 # F值：G值与H值的和，即节点的总评估成本 # 比较两个节点位置是否相同 def __eq__(self, other): return self.position == other.position # 定义小于操作，以便在优先队列中进行比较 def __lt__(self, other): return self.f

【本文地址】

A*（A

A*（A

今日新闻

推荐新闻