怎么用A*算法解决8puzzle八数码问题?

怎么用A*算法解决8puzzle八数码问题?
在此只介绍八数码问题A*算法的主要思想及思路:

1、什么是八数码问题A*算法?

简单来说八数码问题A*算法就是会将队列中的结点按“估价值”由小至大按序并让“估价值”小的结点优先出队的广度优先搜索算法。

2、下面看该算法相关介绍:

(1)、启发式搜索

广度优先搜索和双向广度优先搜索都属于盲目搜索,这在状态空间不大的情况下是很合适的算法,可是当状态空间十分庞大时,它们的效率实在太低,往往都是在搜索了大量无关的状态结点后才碰到解答,甚至更本不能碰到解答。

搜索是一种试探性的查寻过程,为了减少搜索的盲目性引,增加试探的准确性,就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估,从中选择最好、可能容易到达目标的位置,再从这个位置向前进行搜索,这样就可以在搜索中省略大量无关的结点,提高了效率。

(2)、A*算法

A*算法是一种常用的启发式搜索算法。

在A*算法中,一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为:

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

这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值(也称为最小耗费或最小代价),h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的,所以实际上使用的是下面的估价函数:

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

其中g(n)是从初始结点到节点n的实际代价,h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。用f(n)作为f'(n)的近似,也就是用g(n)代替g'(n),h(n)代替h'(n)。这样必须满足两个条件:(1)g(n)>=g'(n)(大多数情况下都是满足的,可以不用考虑),且f必须保持单调递增。(2)h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 3、估价函数算法: 估价函数f(n)=结点深度g(n)+结点至目标结点的估价h(n) 示意图: 856246879154885856

4、算法示意图:

856246879154885875

5、队列重复键处理。

(1)、若新生结点与已出队结点重复则不入队。

(2)、若新生结点与队列中结点重复则保留深度较浅的结点。

发表评论

您的电子邮箱地址不会被公开。