人工智能作业homework2--------A*算法解决八数码

1．启发式搜索算法A

启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

评价函数的形式如下：

f(n)＝g(n)＋h(n)

其中n是被评价的节点。

f(n)、g(n)和h(n)各自表述什么含义呢？我们先来定义下面几个函数的含义，它们与f(n)、g(n)和h(n)的差别是都带有一个“*”号。

g*(n)：表示从初始节点s到节点n的最短路径的耗散值；

h*(n)：表示从节点n到目标节点g的最短路径的耗散值；

f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。

而f(n)、g(n)和h(n)则分别表示是对f*(n)、g*(n)和h*(n)三个函数值的的估计值。是一种预测。A算法就是利用这种预测，来达到有效搜索的目的的。它每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，总是选择当前f值最小的节点来优先扩展。

过程A

①OPEN:＝(s)，f(s):＝g(s)+h(s);

②LOOP: IF OPEN＝( ) THEN EXIT(FAIL)；

③n:＝FIRST(OPEN)；

④IF GOAL(n)THEN EXIT(SUCCESS)；

⑤REMOVE(n，OPEN)，ADD(n，CLOSED)；

⑥EXPAND(n)→{m_i}，计算f(n，m_i)＝g(n，m_i)+h(m_i)；g(n，m_i)是从s通过n到m_i的耗散值，f(n，m_i)是从s通过n、m_i到目标节点耗散值的估计。

·ADD(m_j，OPEN)，标记m_i到n的指针。

·IF f(n，m_k)<f(m_k)THEN f(m_k):＝f(n，m_k)，标记m_k到n的指针；比较f(n，m_k)和f(m_k)，f(m_k)是扩展n之前计算的耗散值。

·IF f(n，m₁)<f(m₁)THEN f(m₁):＝f(n，m₁)，标记m₁到n的指针，ADD(m₁，OPEN)；当f(n，m₁)<f(m₁)时，把m₁重放回OPEN中，不必考虑修改到其子节点的指针。

⑦OPEN中的节点按f值从小到大排序；

⑧GO  LOOP；

A算法同样由一般的图搜索算法改变而成。在算法的第7步，按照f值从小到大对OPEN表中的节点进行排序，体现了A算法的含义。

算法要计算f(n)、g(n)和h(n)的值，g(n)根据已经搜索的结果，按照从初始节点s到节点n的路径，计算这条路径的耗散值就可以了。而h(n)则依赖于启发信息，是与问题有关的，需要根据具体的问题来定义。通常称h(n)为启发函数，是对未来扩展的方向作出估计。

算法A是按f(n)递增的顺序来排列OPEN表的节点，因而优先扩展f(n)值小的节点，体现了好的优先搜索思想，所以算法A是一个好的优先的搜索策略。图1.6表示出当前要扩展节点n之前的搜索图，扩展n后新生成的子节点m₁(∈{m_j})、m₂(∈{m_k})、m₃(∈{m₁})要分别计算其评价函数值：

f(m₁)=g(m₁)+h(m₁)

f(n，m₂)=g(n，m₂)+h(m₂)

f(n，m₃)=g(n，m₃)+h(m₃)

然后按第6步条件进行指针设置和第7步重排OPEN表节点顺序，以便确定下一次要扩展的节点。

下面再以八数码问题为例说明A算法的搜索过程。

设评价函数f(n)形式如下：

f(n)=d(n)+W(n)

其中d(n)代表节点的深度，取g(n)=d(n)表示讨论单位耗散的情况；取h(n)=W(n)表示以“不在位”的将牌个数作为启发函数的度量，这时f(n)可估计出通向目标节点的希望程度。

“不在位的将牌数”计算方法如下：

我们来看下面的两个图。

其中左边的图是8数码问题的一个初始状态，右边的图是8数码问题的目标状态。我们拿初始状态和目标状态相比较，看初始状态的哪些将牌不在目标状态的位置上，这些将牌的数目之和，就是“不在位的将牌数”。比较上面两个图，发现1、2、6和8四个将牌不在目标状态的位置上，所以初始状态的“不在位的将牌数”就是4，也就是初始状态的h值。其他状态的h值，也按照此方法计算。

图1.7表示使用这种评价函数时的搜索树，图中括弧中的数字表示该节点的评价函数值f。算法每一循环结束时，其OPEN表和CLOSED表的排列如下：

根据目标节点L返回到s的指针，可得解路径S(4)，B(5)，E(5)，I(5)，K(5)，L(5)

2.  最佳图搜索算法A﹡（Optimal Search）

当在算法A的评价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n) ≤h*(n)时，则我们把这个算法称为算法A*。A*算法实际上是分支界限和动态规划原理及使用下界范围的h相结合的算法。当问题有解时，A*一定能找到一条到达目标节点的最佳路径。例如在极端情况下，若h(n)≡0（肯定满足下界范围条件），因而一定能找到最佳路径。此时若g≡d，则算法等同于宽度优先算法。前面已提到过，宽度优先算法能保证找到一条到达目标节点最小长度的路径，因而这个特例从直观上就验证了A*的一般结论。

一般地说对任意一个图&#