网站首页制作,江苏纬信网站建设,山西省诚信建设网站,wordpress 主题文件A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度
1 中心思路
A*算法通过下面这个函数来计算每个节点n的优先级 f(n)g(n)h(n) f(n)是节点n的综合优先级。当选择下一个要遍历的节点时#xff0c;总会选取综合优先级最高#xff08;f(n)值最小#xff0…A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度
1 中心思路
A*算法通过下面这个函数来计算每个节点n的优先级 f(n)g(n)h(n) f(n)是节点n的综合优先级。当选择下一个要遍历的节点时总会选取综合优先级最高f(n)值最小的节点。g(n) 是节点n距离起点的代价h(n)是节点n距离终点的预计代价这也就是A*算法的启发函数A*算法在运算过程中每次从优先队列中选取f(n)值最小优先级最高的节点作为下一个待遍历的节点。
1.1 伪代码
A*算法使用两个集合来表示待遍历的节点open_set与已经遍历过的节点close_set 初始化open_set和close_set将起点n0加入open_set中并设置f(n0)0优先级最高如果open_set不为空则从open_set中选取优先级最高的节点n 如果节点n为终点 从终点开始逐步追踪parent节点一直达到起点返回找到的结果路径算法结束如果节点n不是终点 将节点n从open_set中删除并加入close_set中遍历节点n所有的邻近节点 如果邻近节点m在close_set中已经访问过来则 跳过选取下一个邻近节点如果邻近节点m也不在open_set中则 设置节点m的parent为节点n计算节点m的优先级f(n)将节点m加入open_set中 2 启发函数
在极端情况下当启发函数h(n)始终为0则将由g(n)决定节点的优先级此时算法就退化成了Dijkstra算法 ntu 课程笔记 MAS714(7) 最短路径和优先队列_UQI-LIUWJ的博客-CSDN博客如果h(n)始终小于等于节点n到终点的代价则A*算法保证一定能够找到最短路径。 但是当h(n)的值越小算法将遍历越多的节点也就导致算法越慢。如果h(n)完全等于节点n到终点的代价则A*算法将找到最佳路径并且速度很快。 可惜的是并非所有场景下都能做到这一点。因为在没有达到终点之前我们很难确切算出距离终点还有多远。如果h(n)的值比节点n到终点的代价要大则A*算法不能保证找到最短路径不过此时会很快 比如这种情况最短路路径应该是下路但如果我们估计的h(n)为实际路径的两倍 那么选择中间节点的时候A*算法会选择上路 53*21143.6*211.2
2.1 一些经验启发函数
如果图形中只允许朝上下左右四个方向移动则可以使用曼哈顿距离 如果图形中允许朝八个方向移动则可以使用对角距离 如果图形中允许朝任何方向移动则可以使用欧几里得距离
