八数码问题的A*搜索算法
在如下初始状态下八数码进行A*搜索算法。
2 | 8 | 3 |
---|---|---|
1 | 4 | |
7 | 6 | 5 |
搜索树的估价函数为f(n)=d(n)+h(n)
d(n):初始状态到当前状态的代价,当前状态处于搜索树的深度。
h(n):以“不在位”的数码数作为启发信息的度量,即当前不位于目的状态数码的个数。
初始化
初始状态为S(3),其中d(n)等于当前状态位于搜索树的深度0,h(n)等于当前状态不位于目的状态数码的个数2,故2+1=3。
第一次循环:
1、从Open表中取出第一个代价最小的状态S(3),如果该状态是目的状态,则搜索结束并返回Closed表;如果没有,则继续循环。
2、空白区域可以往上下左右四个方向移动,通过上述的计算方法可以得到A(4)、B(4)、C(5)和D(5)四个状态。
3、将A(4)、B(4)、C(5)和D(5)四个状态归入Open表中按每一个状态的代价升序排列,并将上一步状态S(3)归入Closed表中。
第二次循环:
1、从Open表中取出第一个代价最小的状态A(4),如果该状态是目的状态,则搜索结束并返回Closed表;如果没有,则继续循环。
2、空白区域可以往左右移动,由于往下移动后得到的状态已经在Closed表中出现,故不考虑。
3、将得到的E(4)和F(6)归入Open表中,并对Open表重新排序,将上一步状态A(4)归入Cloesd表中。
第三次循环:
1、从Open表中取出第一个代价最小的状态B(4),如果该状态是目的状态,则搜索结束并返回Closed表;如果没有,则继续循环。
2、空白区域可以往上下移动,由于往右移动后得到的状态已经在Closed表中出现,故不考虑。
3、将得到的G(5)和H(6)归入Open表中,并对Open表重新排序,将上一步状态B(4)归入Cloesd表中。
第四次循环:
1、从Open表中取出第一个代价最小的状态E(4),如果该状态是目的状态,则搜索结束并返回Closed表;如果没有,则继续循环。
2、空白区域可以往下移动,由于往右移动后得到的状态已经在Closed表中出现,故不考虑。
3、将得到的I(4)归入Open表中,并对Open表重新排序,将上一步状态E(4)归入Cloesd表中。
第五次循环:
1、从Open表中取出第一个代价最小的状态I(4),如果该状态是目的状态,则搜索结束并返回Closed表;如果没有,则继续循环。
2、空白区域可以往下、右移动,由于往上移动后得到的状态已经在Closed表中出现,故不考虑。
3、将得到的J(4)和K(6)归入Open表中,并对Open表重新排序,将上一步状态I(4)归入Cloesd表中。
第六次循环
1、从Open表中取出第一个代价最小的状态J(4),该状态就是目的状态,停止搜索并返回Cloesd表。