八数码问题A算法的实现及性能分析.docx
《八数码问题A算法的实现及性能分析.docx》由会员分享，可在线阅读，更多相关《八数码问题A算法的实现及性能分析.docx（22页珍藏版）》请在冰点文库上搜索。
八数码问题A算法的实现及性能分析
八数码问题A＊算法的实现及性能分析
计算机科学与技术学院
专业:
计算机科学与技术
161210404杨凯迪
一、8数码问题
1。
问题描述
八数码问题是指这样一种游戏:
将分别标有数字1，2，3,…,8的八块正方形数码牌任意地放在一块3×3的数码盘上。
放牌时要求不能重叠。
于是，在3×3的数码盘上出现了一个空格。
现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态.空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如图1-1所示
初始状态过渡状态最终状态
图1-1八数码问题执行过程
2.八数码问题形式化描述
初始状态：
初始状态向量:
规定向量中各分量对应的位置，各位置上的数字。
把3×3的棋盘按从左到右，从上到下的顺序写成一个一维向量。
我们可以设定初始状态:
〈1，5,2，4，0，3，6，7，8>
后继函数：
按照某种规则移动数字得到的新向量.例如：
〈1,5,2,4,0，3，6，7，8〉→〈1,0,2,4,5，3，6，7，8〉
目标测试：
新向量是都是目标状态。
即〈1，2，3，4,5，6,7，8，0>是目标状态?
路径耗散函数：
每次移动代价为1，每执行一条规则后总代价加1。
3。
解决方案
该问题是一个搜索问题。
它是一种状态到另一种状态的变换。
要解决这个问题,必须先把问题转化为数字描述.由于八数码是一个3＊3的矩阵，但在算法中不实用矩阵,而是将这个矩阵转化为一个一维数组,使用这个一维数组来表示八数码，但是移动时要遵守相关规则。
（1）可用如下形式的规则来表示数字通过空格进行移动:
〈a1,a2，a3,a4，a5，a6,a7，a8，a9〉→
（2）共24条移动规则，对应与每个位置的移动规则。
（3）搜索顺序举例：
1）优先移动行数小的棋子（数字）
2）同一行中优先移动列数大的棋子
（4）约束规则：
不使离开既定位置的数字数增加
八数码的节点扩展应当遵循棋子的移动规则.按规则,每一次可以将一个与空格相邻的棋子移动到空格中,实际上也可以看做空格的相反方向移动。
空格的移动方向可以是上下左右,当然不能出边界.棋子的位置，也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化，在不移出边界的条件下，空格向右,下，左，上移动后，新位置是原位置分别加上1，3,-1,-3。
在这里，空格可以用任意数字表示。
操作本文用u（up）r（right）d（down）l（left）分别表示空格的向上向右向下向左四个操作。
经分析，8数码问题的搜索策略共有：
1。
广度优先搜索、2。
深度优先搜索、3.有界深度优先搜索、4。
最好优先搜索、5。
局部择优搜索，等等.其中广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。
本实验采用启发式A*搜索算法来实现。
二、A*算法
1.A＊搜索算法一般介绍
A*算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数评估每次的的决策的价值，决定先尝试哪一种方案，这样可以极大的优化普通的广度优先搜索。
一般来说，从出发点（A）到目的地（B）的最短距离是固定的，我们可以写一个函数judge（）估计A到B的最短距离,如果程序已经尝试着从出发点A沿着某条路线移动到了C点,那么我们认为这个方案的AB间的估计距离为A到C实际已经行走了的距离H加上用judge（）估计出的C到B的距离。
如此，无论我们的程序搜索展开到哪一步，都会算出一个评估值，每一次决策后，将评估值和等待处理的方案一起排序，然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步,一直循环到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的路径则结束。
A*算法是一个可采纳的最好优先算法.A*算法的估价函数可表示为:
f’（n）=g'（n）+h’（n）
这里，f'（n）是估价函数，g'（n）是起点到终点的最短路径值，h'（n）是n到目标的最断路经的启发值.由于这个f’（n）其实是无法预先知道的，所以我们用前面的估价函数f（n）做近似。
g（n）代替g’（n），但g（n）〉=g’（n）才可（大多数情况下都是满足的，可以不用考虑），h（n）代替h'（n）,但h（n）<=h'（n）才可.可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。
2。
A*算法的伪代码
创建两个表,OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;
将起点放入OPEN表;
while（OPEN!
=NULL）
｛
从OPEN表中取估价值f最小的节点n;
if（n节点==目标节点）｛
break;
}
for（当前节点n的每个子节点X）
{
算X的估价值;
if（XinOPEN）
｛
if（X的估价值小于OPEN表的X估价值）｛
把n设置为X的父亲;
更新OPEN表中的估价值；//取最小路径的估价值
｝
｝
if（XinCLOSE）{
if（X的估价值小于CLOSE表的X估价值）｛
把n设置为X的父亲;
将该节点从close表中除去
把X节点放入OPEN//取最小路径的估价值
}
}
if（Xnotinboth）｛
把n设置为X的父亲；
求X的估价值;
并将X插入OPEN表中；//升序排列open
｝
｝//endfor
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序；//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
｝//endwhile（OPEN！
=NULL）
保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；
3。
建立合适的启发式
A*算法有个计算公式f（x）=g（x）+h（x）
其中g（x）为从起始状态到当前状态所消耗的步数,h（x）为一个启发值，估算从当前状态到目标状态所需的步数，一般h（x）小于等于实际需要步数为好，这样不会将最优解忽略,因为h（x）和解空间有一些关系，如果h（x）设置的比实际需要的步数多，那么解空间就有可能将最优解忽略。
举个例子吧，宽度优先搜索就是h（x）=0带来的效果，深度优先搜索就是g（x）=0带来的效果，不过h（x）距离h＊（x）［实际需要的步数］的程度不能过大,否则h（x）就没有过强的区分能力，算法效率并不会很高。
对一个好的h（x）的评价是：
h（x）在h*（n）[实际需要的步数］的下界之下，并且尽量接近h*（n）［实际需要的步数］。
那么8数码问题g（x）为经过上下左右移动空格附近的数字来得到新状态所需步数，h（x）为当前状态与目标状态的距离，就是所有不在目标位置的数字总和，必然小于h*（x）
三、算法实现及性能比较
这里通过c++语言来实现各种排序算法（源码见附录），程序运行环境为windows7，所用编译器为vs2013。
实验分别以不同的初始棋盘和相同的目标棋盘为例进行测试.
初始数码棋盘1：
203146758
初始数码棋盘2:
243068175
初始数码棋盘3:
237648105
初始数码棋盘4:
324507816
初始数码棋盘5:
403268175
初始数码棋盘6：
143570268
初始数码棋盘7：
463285107
目标数码棋盘：
123456780
实验部分结果如图3—1：
图3—1。
测试结果
四、算法性能分析
在测试中我们根据不同的初始数码状态相同的目标数码状态,产生不同的移动步骤，并给出了其步数和运行时间（单位ms）。
表1为不同的初始数码状态相同的目标数码状态测试后得到的运行时间数据。
表2为不同的初始数码状态相同的目标数码状态能否的到正确的步骤与否的数据。
初始
数据
棋盘1
棋盘2
棋盘3
棋盘4
棋盘5
棋盘6
棋盘7
步数
5
11
21
0
13
0
17
时间（ms）
52.531
507。
69
1822
0
134。
42
0
2815。
83
表1步数和运行时间（单位ms）
初始
数据
棋盘1
棋盘2
棋盘3
棋盘4
棋盘5
棋盘6
棋盘7
正确与否
T
T
T
F
T
F
T
表2能否得到正确步骤
为了直观起见，根据实验数据画出不同的初始数码状态相同的目标数码状态下时间随步数的变化趋势图如图3-2所示：
图3-2时间随步数的变化趋势图
根据实验数据表2，我们可得到该算法得到正确步骤路径的概率为:
71.42％。
五、结论
最后我们得出结论:
时间性能上，
算法所需时间随步数的增加而逐渐呈增加趋势，但并不是线性增长.部分时间不随移动步数变化。
该算法能得到正确的解概率约为71.42％
六、参考文献
1．《Artificialintelligence:
;amodernapproach人工智能:
一种现代方法》作者:
Russell,StuartJ。
出版社：
清华大学出版社
附录
＃include〈iostream>
＃include＃includeh〉
＃include〈vector〉
＃include〈cmath>
usingnamespacestd;
structnode｛
inta[3］［3]；//存放矩阵
intfather;//父节点的位置
intgone；//是否遍历过,1为是，0为否
intfn；//评价函数的值
intx，y;//空格的坐标
intdeep;//节点深度
｝；
vector〈node〉store;//存放路径节点
intmx[4］=｛-1,0,1,0};
intmy[4］=｛0，-1，0,1};//上下左右移动数组
inttop；//当前节点在store中的位置
boolcheck（intnum）//判断store[num]节点与目标节点是否相同，目标节点储存在store［0]中
{
for（inti=0;i〈3；i++）｛
for（intj=0;j<3;j++）｛
if（store[num］.a[i][j]！
=store［0］.a[i]［j]）
returnfalse；
}
｝
returntrue;
}
boolsearch（intnum）//判断store［num]节点是否已经扩展过,没有扩展返回true
{
intpre=store[num］。
father；//pre指向store［num]的父节点位置
booltest=true;
while（！
pre）{//循环直到pre为0，既初始节点
for（inti=0;i〈3；i++）｛
for（intj=0；j<3;j++）｛
if（store［pre］.a［i］[j]！
=store[num］.a［i］[j］）｛
test=false；
break；
}
}
if（test==false）break;
｝
if（test==true）returnfalse；
pre=store［pre］.father;//pre继续指向store[pre]父节点位置
}
returntrue;
}
voidprint（intnum）//打印路径,store[num］为目标节点
{
vector〈int〉temp；//存放路径
intpre=store[num]。
father;
temp.push_back（num）；
while（pre！
=0）{//从目标节点回溯到初始节点
temp。
push_back（pre）；
pre=store[pre]。
father;
}
cout<〈endl;
cout<〈”＊**＊*****数码移动步骤*＊**＊＊＊＊＊”〈intmm=1；//步数
for（intm=temp.size（）-1；m〉=0；m-—）｛
cout<<"-—-第"<"〈for（inti=0；i<3;i++）{
for（intj=0;j<3;j++）{
cout〈〈store[temp［m]］。
a[i]［j］<<”";
}
cout〈〈endl；
}
mm++;
cout<}
cout〈〈”所需步数为：
”〈〈store［num］。
deep<return;
}
intget_fn（intnum）//返回store［num]的评价函数值
{
intfn_temp=0；//评价函数值
booltest=true;
for（inti=0;i〈3;i++）｛//当找到一个值后,计算这个值位置与目标位置的距离差，test置为false后继续寻找下一个值
for（intj=0；j<3;j++）｛
test=true；
for（intk=0；k〈3;k++）{
for（intl=0；l〈3;l++）{
if（（store［num]。
x！
=i|｜store[num］。
y!
=j）＆＆store［num］。
a[i]［j］==store［0］。
a[k］[l］）{//寻值时排除空格位
fn_temp=fn_temp+abs（i-k）+abs（j-l）；
test=false;
}
if（test==false）break；
}
if（test==false）break；
}
｝
}
fn_temp=fn_temp+store[num］.deep；//加上节点深度
returnfn_temp;
}
voidkongxy（intnum）//获得空格坐标
｛
for（inti=0;i〈3；i++）｛
for（intj=0；j<3；j++）｛
if（store［num].a[i]［j］==0）｛
store[num］。
x=i；
store［num］。
y=j;
}
｝
}
return;
｝
intmain（）
{
cout<〈”-—--——--———A*算法解决8数码问题—————-———--—"〈〈endl;
while（true）｛
store。
clear（）；//清空store
vectorinti,j,m,n，f;
intmin;//store［min］储存fn值最小的节点
inttemp；
booltest;
top=1;//当前节点在store的位置,初始节点在store［1]
inttarget[9];
intbegin[9];//储存初始状态和目标状态,用于判断奇偶
intt1=0，t2=0;//初始状态和目标状态的奇偶序数
nodenode_temp；
store。
push_back（node_temp）；
store。
push_back（node_temp）；//用于创建store[0]和store［1］,以便下面使用
cout〈<"请输入初始数码棋盘状态，0代表空格：
”<〈endl；//输入初始状态，储存在store［1]中
test=false；
while（test==false）｛
f=0;
for（i=0；i<3;i++）{
for（j=0；j<3；j++）｛
cin>〉temp;
store［1].a［i]［j］=temp；
begin［f++]=temp；
｝
｝
test=true；
for（i=0;i<8;i++）｛//检查是否有重复输入，若有则重新输入
for（j=i+1；j〈9；j++）{
if（begin[i]==begin［j]）｛
test=false;
break；
｝
}
if（test==false）break;
}
if（test==false）cout〈〈"输入重复，请重新输入：
"<〈endl;
｝
kongxy
（1）；//找出空格的坐标
cout〈<”请输入目标数码棋盘状态,0代表空格：
"<〈endl;//输入目标状态，储存在store［0]中
test=false；
while（test==false）{
f=0;
for（i=0;i〈3;i++）{
for（j=0;j〈3;j++）{
cin>>temp;
store［0］。
a［i］[j]=temp;
target[f++]=temp；
｝
}
test=true；
for（i=0;i〈8；i++）｛//检查是否有重复输入,若有则重新输入
for（j=i+1;j〈9;j++）｛
if（target[i］==target[j]）{
test=false;
break；
｝
}
if（test==false）break;
}
if（test==false）｛
cout<<”输入重复，请重新输入:
”〈〈endl；
continue;//若重复，重新输入
}
for（i=0;i〈9；i++）｛//检查目标状态与初始状态是否匹配
test=false；
for（j=0；j〈9；j++）｛
if（begin［i]==target[j］）｛
test=true；
break；
}
}
if（test==false）break;
｝
if（test==false）cout<〈”输入与初始状态不匹配,请重新输入：
”<}
for（i=1;i<9;i++）{//判断奇偶序数是否相同，若不相同则无法找到路径
for（j=1;i-j>=0；j++）{
if（begin［i]〉begin［i—j］）｛
if（begin［i—j]!
=0）t1++；
｝
｝
}
for（i=1；i<9；i++）｛
for（j=1;i—j〉=0;j++）{
if（target[i]〉target［i-j]）{
if（target[i—j]!
=0）t2++;
}
｝
｝
if（!
（t1％2==t2％2））{
cout〈〈"无法找到路径。
”〈〈endl；
cout〈〈endl；
//system（"pause”）;
//return0；
continue；
}
LARGE_INTEGERFreg;
LARGE_INTEGERCount1，Count2;
QueryPerformanceFrequency（&Freg）；
QueryPerformanceCounter（＆Count1）；//获取时间Count1
doubled；
store［1]。
father=0；//初始化参数
store［1］.gone=0;
store[1].deep=0;//初始节点的父节点为0
store［1]。
fn=get_fn
（1）；
if（check
（1））{//判断初始状态与目标状态是否相同
print
（1）；
//system（"pause”）;
//return0;
cout<〈endl；
continue；
}
open。
push_back
（1）；//把初始状态在store中的位置数压入open表中
while（!
open.empty（））｛//当open表不为空时,开始寻找路径
if（check（top））break;
min=top;
inti_min=0;
for（i=0；i〈open.size（）；i++）{//遍历open表中元素，找出store中fn值最小的节点
if（store[open[i]］。
fn〈=store［min].fn&＆store[open［i]］.gone==0）{
min=open［i];
i_min=i;
}
}
store［min］.gone=1；
open.erase（open。
begin（）+i_min）；//把最小节点标记遍历过，并从open表中删除
m=store［min］。
x;
n=store[min］。
y；//空格坐标
for（f=0;f<4；f++）{//上下左右移动空格
i=m+mx［f]；
j=n+my[f］;
if（i〉=0＆＆i<=2＆&j〉=0&&j<=2）｛//当变换后的空格坐标在矩阵中时，开始移动
top++;
store.push_back（store[min］）;//把sto
升级会员 