当前位置:   article > 正文

A*算法,简单实现八数码问题_a 算法实现八数码与a*算法实现八数码

a 算法实现八数码与a*算法实现八数码

A*算法求解N数码问题的设计与实现

Table of Contents

任务要求:

1. 关于A*算法:

2. 算法复杂度:

3. Solution:

4. CODE


任务要求:

  1. 以八数码问题为例实现A*算法的求解程序(编程语言不限),要求设计两种以上的不同估价函数;
  2. 在求解八数码问题的A*算法程序中,设置相同的初始状态和目标状态,针对不同的估价函数,求得问题的解,并比较它们对搜索算法性能的影响,包括扩展节点数、生成节点数等;
  3. 对于八8数码问题,设置与上述2相同的初始状态和目标状态,用宽度优先搜索算法(即令估计代价h(n)=0的A*算法)求得问题的解,以及搜索过程中的扩展节点数、生成节点数;
  4. 上交源程序(要求有代码注释)。

1. 关于A*算法:

A*算法的核心代价函数的设计,loss = g + h,g为当前状态深度,h是关键,h代表当前状态到达目标状态的估计值,h必须满足某些条件,而最重要的条件是h < r,r为当前状态到目标状态的估计值。

以实例理解上述条件。例如在八数码问题中,h可以被设计为“各个数到目标状态需要走的步数的和”,这显然是小于真实需要步数和的,h也可以被设计为“各个数和目标状态不同的个数和”,这个条件显然比第一个条件更加宽松,必然小于真实需要步数。以上即为本次设计的两个代价函数。

另一个例子是连续地图中的寻路算法,h一般设计为欧式距离,即直线距离,这显然比真实需要走的路要短(可能有障碍,弯路等等)。

通过以上两个例子,我们可以直观地理解,为什么估计值h必须小于真实值,但要尽可能的大,接近真实值的下界。例如寻路算法中,你估算的距离越接近真实距离,那么你启发式找到可能的路径就会越准确。理论上,可以严格证明满足这些条件,必然可以找到最优解。

从另一个角度来审视A*算法,它可以视为以代价为步长的广度优先算法,这一点要从代码实现上才能感受到。每次都优先处理代价最小的状态,如果观察搜索树,将会看到它在整个搜索数的节点之间无序跳动(选全局估计代价最小)。

再次,例如在寻路算法中,A*算法在实际运行中,类似于我们人类在找两点之间的最快路径,尽管我们无法确定中间要从何处绕开障碍,但是我们却知道要忘目标靠。下面是A*算法运行实例,它在每个状态,都会对目标计算一次欧式距离,以此约束选择,就仿佛被欧式距离牵引到目标状态一样。

https://pic1.zhimg.com/80/v2-99dea949704bd4d7a52f397586954c04_720w.jpg

2. 算法复杂度:

  1. 广度优先搜索,算法复杂度为O(4^n),或者从另外的角度,八字码的所有状态为n个数字的全排列,估计O(n!)。
  2. A*算法的好坏和代价函数h的设计密切相关,h必须尽可能小于并贴近真实代价,这样朝目标贴近的方向越笔直(参考上图),算法的一个上界和广度搜索是一样的,但实际上可以很快,我感觉在一些问题中可以接近线性复杂度。
  3. A*算法的空间消耗非常大,和实际复杂度类似,它需要保存每个状态,同样和h的设计相关。
  4. 过小的h的估计,会导致“这条路比较最短,我要深入下去,但其实这条路是错的”这种现象,即会在错误的路上深入太深,h太小,那么g就要越大才会发现走错,越深的搜索,节点增长得越快,越接近指数级别。

3. Solution

 

init_state

[[3 1 7]

 [6 8 0]

 [4 2 5]]

target

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

闽ICP备14008679号