当前位置:   article > 正文

启发式搜索算法_头歌启发式搜索第二关a*搜索算法

头歌启发式搜索第二关a*搜索算法

第1关:评估函数和启发信息

任务描述
本关任务:掌握问题的求解过程,并完成相应的选择题。

相关知识
为了完成本关任务,你需要掌握:评估函数和启发信息。

评估函数和启发信息
启发式搜索就是在状态空间中搜索时,对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

A


A
  • 1
  • 2
  • 3
  • 4

第2关:A*搜索算法

任务描述
本关任务:编写一个利用 A* 算法实现地图寻路的程序。

相关知识
为了完成本关任务,你需要掌握 A* 算法。

A算法
A
算法是由著名的人工智能学者 Nilsson 提出的,它是目前最具有影响的启发图搜索算法,也称为最佳图搜索算法。之前我们已经了解了一般的启发式搜索算法评估函数f(n)可定义为:
f(n)=g(n)+h(n)
而在 A 算法中定义 h(n) 为状态 n 到目的状态的最优路径的代价。* 下面是 A* 算法的描述。

1.把起点加入 open list ;
2.重复如下过程:
a. 遍历 open list ,查找 F 值最小的节点,把它作为当前要处理的节点。
b.把这个节点移到 close list 。
c.对当前方格的 8 个相邻方格的每一个方格?
◆如果它是不可抵达的或者它在 close list 中,

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/738859
推荐阅读