浅谈寻路A算法

浅谈寻路A*算法

算法

路是游戏中非常重要的一个元素，如何到一条最短的路径是程序需要设计的算法，现在最为流行的寻路算法是A*算法。A*算法与状态空间搜索结合的相当紧密。

状态空间搜索，就是将问题求解的过程表现为从初始状态到目标状态寻这个路径的过程，通俗的说就是在解一个问题的时候到一条解题过程可以从求解的开始到问题的结束。

由于求解过程中求解条件的不确定与不完备性使得问题的求解过冲中的分支有很多，这就产生了多条求解的路径，这些路径过程一个图这个图就是状态空间。问题的求解时机上就是在这个图中个一个路径可以从开始到结束，这个过程就是状态空间搜索。

下载 (75.86 KB)
浅谈寻路A*算法

2009-6-22 12:19

常用的状态空间搜索有深度优先和广度优先，广度优先是从初始状态一层一层的向下，知道到结果目标为止，深度优先是按照一定的顺序先查完一个分支再查另一个分支，知道到目标结果为止。这两种搜索方法有的很大缺陷是它们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很适合的算法，但是当空间很大并且不可预测的情况下就不可取。这个时候这两种算法的效率太低甚至有时是无法完成，所以要用到另一种算法---启发式搜索。

启发式搜索就是在状态空间中对每一个搜索为止进行评估，指导到最好的为止，再从这个位置进行搜索直到目标位置为止。在启发式搜索中对为止的评估是十分重要的，采用不同的估价可能有不同的结果。

氯化氢压缩机启发式搜索中的估价函数表示为：

其中是节点的估价函数，是在状态空间中从初始点到节点的实际代价，是从节点到目标节点最佳路径的估价代价。这个里主要是体现了搜索的启发信息，因为是己知的。换个说法就是代表了索索的广度优先趋势但是当时，可以省略，从而提高效率。

启发式搜索其实也有很多算法，比如局部择优搜索，最好优先搜索等。A*也是如此，这些算法都启用了启发函数，但在具体的选取最佳搜索节点时的策略不同。比如局部择优算法就是在搜索的过程中选取了最佳节点候舍弃了其他的兄弟节点，父亲节点并且一直搜索下去。这种搜索结果很明显，由于舍弃了其他的节点因此可能也把最佳的节点舍去偶尔。最好优先就聪明一点搜索的时候并没有舍去节点，除非该节点是死节点。在没一步的估价中都吧当前的节点和以前的节点的估价值进行比较从而得到最佳节点，这样防止了最佳节点的丢失。

A*算法也是一种最好优先的算法，只是加上了一些特定的约束条件，由于在一些问题求解时，希望能够求解出状态空间搜索的最短路径也就是用最快的方法求解出问题，A*算法的目的就是这样。其估价的函数可以表示为：

这里的是估价函数，是起点到终点的最短路径值，是到目标的最短路径的启发值。由于是无法提前预先知道的，因此用前面的估价函数做近似代表，但是g(n)≥g'(n)才可以通常都是大于所以不要考虑，但是代替时候需要才可以。可以证明应用这样的评估函数是可以到最短路径的，因此应用这种评估函数的最好的优先算法就是A*算法。

至于的启发函数的信息性，就是在估计一个节点值的约束条件，如果信息越多或者约束条件越多则排除节点就越多，估价函数就越好或者说这个算法就越好。这就是为什么广度优先算法很不好的原因，因为起一点启发信息都没有，但是在游戏的开发中由于实时性的要求，的实质信息越多计算量也大消耗的时间就长，其次在牺牲算法准确性的前提下就可以适当的减少固体破碎机的启发信息。

我们先看下最好优先算法的逻辑（起始为止为A结束位置是P，字母后数字为节点的估价值）：

下载 (39.85 KB)
浅谈寻路A*算法

2009-6-22 12:19

搜索的过程中设置两个表：OPEN和CLOSE。OPEN表保存了所有已生成的未考察的节点。CLOSE表中记录了已访问的节点。算法中有一步是根据估价函数重新排列OPEN表，这样循环中的每一步值考虑OPEN萨纳克中状态最好的节点搜索过程如下：

1.初始状态

OPEN=[A5];CLOSED=[];
包装盒fonmoo
2.估算A5，取得所有子节点，并放入OPEN表中

OPEN=[B4,C4,D6];CLOSED=[A5];

3.估算B4,取得所有子节点，并放入OPEN表中

OPEN=[C4,E5,F5,D6];CLOSED=[B4,A5];

4.估算C4，取得所有子节点，并放入OPEN表中

OPEN=[H3,G4,E5,F5,D6];CLOSED=[C4,B4,A5];

5.估算H3，取得所有子节点，并放入OPEN表中

OPEN=[O2,P3,G4,E5,F5,D6];CLOSED=[H3,C4,B4,A5];

6.估算O2，取得所有子节点，并放入OPEN表中

OPEN=[P3,G4,E5,F5,D6];CLOSED=[O2,H3,C4,B4,A5];

7.估算P3得到解

伪代码如下：

1. Best_First_Seach()

2. {

3. Open=[起始节点]；

4. Closed=[];

5. while(Open表非空)

6. {

7. 从Open中取得一个节点X，并从Open表中删除。

8. if(X节点是目标节点)

9. {

10. 求的路径PATH;

11. returnPATH;

12. }

13. for(每个X的子节点Y)

14. {

15. if(Y不在OPEN表和CLOSE表中)

16. {

17. 求Y的估价值；

18. 将Y插入OPEN表中；输液瓶

19. }

20. elseif(Y在OPEN表中)

21. {

22. if(Y的估价值小于OPEN表的估价值)

23. 更新OPEN表中的估价值；

24. }lcm液晶显示模块

25. else

26. {

27. if(Y的估价值小于CLOSE表的估价值)

28. 更新CLOSE表中的股价值

29. 从CLOSE表中移出节点，放入OPEN表中；

30. }

31. }

32. 讲X节点插入CLOSE表中；

33. 按照估价值讲OPEN表中的节点排序；

34. }

35. }

本文发布于:2024-09-22 18:30:51，感谢您对本站的认可！

本文链接：https://www.17tex.com/tex/4/104632.html

上一篇：基于深度学习的室内简单环境寻路算法

下一篇：物联网考试题库答案

标签：节点搜索算法求解状态

留言与评论（共有 0 条评论）