人工智能十五数码实验报告Word下载.docx
《人工智能十五数码实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《人工智能十五数码实验报告Word下载.docx（23页珍藏版）》请在冰点文库上搜索。
否则问题无解。
状
态的逆序数是定义如下：
把四行数展开排成一行，并且丢弃数字o不计入其中,
ni是第i个数之前比该数小的数字的个数，则n=》ni是该状态的逆序数例如：
对于初始状态：
5、1、2、4、9、63、8、13、15、10、11、14、7、12.其n=0+0+1+2+4+4+2+6+8+9+8+9+11+6+11=81对于目标状态：
1、2、3、4、5、6、7、8、9、10、11、12、13、14、15,其n
=0+1+2+3+4+5+6+7+8+9+10+11+12+13+14=105初始状态和目标状态的奇偶性相同，故存在解路径。
3问题的求解策略
3.1算法分析
十五数码问题的解空间树属排列树，用于排列树搜索的方法主要有两大类：
一类是盲目搜索，如深度优先搜索DFS和广度优先搜索BFS另一类是启发式搜索，如A*算法。
对于十五数码问题，深度优先搜索的状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。
应用此策略
很可能得不到解。
宽度优先搜索的优势在于当问题有解时，一定能找到解，且
能找到最优解。
但其搜索时需要保存所有的待扩展结点，这样很容易扩展那些没有用的结点，造成状态的指数增长，甚至“组合爆炸”。
这对宽度优先搜索很不利。
这两种搜索方法的共同缺点是结点排序杂乱无章，往往在搜索了大量无关结
点后才能得到目的结点，只适合于复杂度较低的问题的求解。
启发式搜索利用特定问题自身所携带的启发信息在一定程度上避免了盲目搜索的不足，适合于解决十五数码问题。
其核心思想是引入一个启发式函数（或
称为评估函数）利用评估函数为生成的结点估值％并按估值的大小对结点进行排
序，优先搜索估值小的结点。
该评估函数根据问题的启发信息建立，评估了解
决问题所需的最小费用，其基本形式是f（n）=g（n）+h（n）。
其中g（n）：
从初始状态s到中间状态n的最佳代价g*（n）的估值，h（n）：
从中间状态n到目标状态t的最佳代价h*（n）的估值，利用评估函数来进行的图搜索算法称为A算法，若
还有h（n）<
=h*（n）则称为A*算法。
在八数码问题中，通常g（n）是搜索树中当前结点n的深度，是从根结点到当前结点n的最短路径长度；
h（n）的取值则有多种，如错位将牌数、曼哈顿距离。
这里主要是h（n）体现了启发信息，h（n）设计的好坏体现了算法的“智能”水平。
本课设借鉴这些算法h（n）采用曼哈顿距离。
3.2A*算法设计
（1）根据初始排列生成初始结点s,并判断问题的可解性。
若可解则转
（2）否则退出。
（2）初始化open，closed表，并将初始节点加入open表。
（3）从open表中取出第一个节点。
（4）若是目标节点则成功退出。
（5）把该节点从open表删除，并添加到closed表中。
（6）对该节点进行扩展，其生成节点mi分成三种情况，mj，mk，ml。
mj:
新生成的节点既不在open表中也不在closed表中，直接把生成的节点添加到open表即可。
Mk：
新生成的节点出现在open表中且新生成节点的f（n）小于open表中该节点的f（n），则更改open表中的f（n）的值。
Ml:
新生成的节点在closed表中并且新生成节点的f（n）小于closed表中对应节点的f（n）的值，则把该节点从open表中删除，添加到open表中并写该其f值为新生成节点的f值。
（7）对open表中的节点按f值从小到大的顺序进行排列。
（8）转到（3）。
4实验总结
4.1实验可视化界面
圏L[g回
I劃1*
E
^1
鱼ILla回
r~ar—t
L.-.i
2
3
4
1
l.-.i
尊
6
7
8
5
9
10
j0
11
"
I-
12
13
14
15
第12步
第佗步
4.2个人体会
初学人工智能时，最先联想到的便是机器人，一直感觉机器人是非常智能且神秘的，这也令人工智能在我的思想里笼罩了一层非同寻常的面纱，非常迫切的
想要了解他的内涵。
经过三十多个学时的学习，我对人工智能已经有了初步的了解，也深深的被它吸引，尤其通过本次课程设计，对人工智能的学习兴趣更加浓厚了！
15数码问题是人工智能的一个经典的问题。
本文中通过设计一个基于A*算
法的状态空间搜索程序，对于给定的初始状态，采用f（n）=h（n）+g（n）表示以当前节点与其目标节点相应位置不相同元素的个数与搜索深度之和作为启发函数的度量，并用面相对象的编程语言java来实现该问题。
在程序的设计与实现过程中，遇到了很多的问题。
首先由于初学人工智能，理解上有一定的困难，对A*算法
的深入学习是一个曲折的过程。
其次，在程序真正的设计及实现过程中，的确需要花费大量的精力来思考，反复试验。
所设计的程序能够运行，但缺陷还是非常之大的，如其中重排OPEN表时，没有进行真正意义上的重新排列，只是选出代价最小的放在最先的位置，这实际上对程序的运行效率有很大的影响。
同时通
过输入大量的初始状态和目标状态发现，在一般情况下都可以找到最优的动作序列。
但对某些稍微复杂的初始状态虽能得到正确解却不能完全得到最短的搜索路径，对于某些极其复杂的状态，甚至得不到解。
这是有待进一步学习并改进的地方。
但本程序还是有些值得肯定之处。
界面设计比较友好，容易操作。
而且在程序开始时，就判断目标状态是否可达，这样可节约大量的时间。
虽然很多地方设计的不尽如意，但这是针对十五数码这个具体问题的一点优化。
4.3详细代码:
publicclassMain{
publicstaticfinalintN=4;
staticintnum[][]={{5,1,2,4},{9,6,3,8},{13,15,10,11},{14,0,7,12}};
staticintstandard[][]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};
publicstaticvoidmain（String[]args）{
inttotalnum=0;
Nodenode=newNode（num）;
if（!
Data.isDataOk（num,standard））{
System.out.println（”此种方案无解"
）;
System.exit（-1）;
}
System.out.println（”数据的变化情况如下所示：
\n"
Noderesultnode=FifteenNum.moveManHa（node）;
for（inti=1;
i<
=resultnode.getPnodes（）.size（）;
i++）{
Interfacef=newInterface（）;
f.P1（resultnode.getPnodes（）.get（i-1）.data,i-1）;
try{
Thread.sleep（2000）;
}catch（InterruptedExceptione）{
e.printStackTrace（）;
resultnode.getPnodes（）.get（i-1）.print（）;
System.out.println（）;
System.out.println（"
第"
+i+"
步"
totalnum=i;
f.P1（resultnode.data,totalnum）;
resultnode.print（）;
importjava.util.ArrayList;
importjava.util.List;
publicclassNode{
privateintf;
privateinth;
privateintw;
List<
Node>
pnodes=newArrayList<
（）;
FifteenNum.Directionlast_Dirction;
intdata[][]=newint[N][N];
publicNode（intdata[][]）{
this.h=0;
this.w=0;
this.f=0;
this.last_Dirction=null;
Data.arrayCopy（this.data,data）;
//pnodes.add（this）;
publicList<
getPnodes（）{
returnpnodes;
publicFifteenNum.DirectiongetLast_Dirction（）{
returnlast_Dirction;
publicvoidsetLast_Dirction（FifteenNum.DirectionlastDirction）{last_Dirction=lastDirction;
publicintgetF（）{
returnf;
publicvoidsetF（intf）{
this.f=f;
publicintgetH（）{
returnh;
publicvoidsetH（inth）{
this.h=h;
publicintgetW（）{
returnw;
publicvoidsetW（intw）{
this.w=w;
publicvoidprint（）{
for（inti=0;
8;
System.out.print（"
*"
N;
for（intj=0;
j<
j++）{
if（data[i][j]==0）{
}elseif（data[i][j]<
10）{
System.out.print（data[i][j]+"
}else{
*"
publicbooleanisequal（Nodenode）{
booleanflag=true;
if（data[i][j]!
=node.data[i][j]）{
flag=false;
break;
flag）break;
returnflag;
publicNodegetSameStateFrom（List<
list）{
list.size（）;
i++）{if（this.isequal（list.get（i）））returnlist.get（i）;
returnnull;
importjava.util.Scanner;
publicclassData{
publicstaticintn=Main.N;
staticScannersc=newScanner（System.in）;
publicstaticvoidinputNum（intnum[][]）{
intk=0;
n;
num[i][j]=sc.nextlnt（）;
publicstaticvoidarrayCopy（inta[][],intb[][]）{
a[i][j]=b[i][j];
publicstaticintinverseNum（intdata[][]）{
intindex=0;
intnum=0;
inttempnum=0;
inttemp[]=newint[n*n-1];
=0）{
temp[index]=data[i][j];
〃System.out.print（temp[index]+"
index++;
n*n-1;
tempnum=0;
for（intj=0;
i;
if（temp[j]<
temp[i]）{
tempnum++;
num+=tempnum;
returnnum;
publicstaticintWrongLocationNum（inttemp[][]）{
intcount=0;
if（temp[i][j]!
=Main.standard[i][j]）{
count++;
returncount;
publicstaticintmanHa（inttemp[][]）{
intd=0;
booleanflag=false;
for（intx1=0;
x1<
x1++）{
for（inty1=0;
y1<
y1++）{
if（temp[x1][y1]!
for（intx2=0;
x2<
x2++）{
for（inty2=0;
y2<
y2++）{
if（temp[x1][y1]==Main.standard[x2][y2]）{
d+=Math.abs（x1-x2）+Math.abs（y1-y2）;
flag=true;
if（flag）break;
returnd;
publicstaticbooleansameOdevity（intm,intn）{
if（m%2==n%2）returntrue;
elsereturnfalse;
publicstaticbooleanisDataOk（inta[][],intb[][]）{
returnsameOdevity（inverseNum（a）,inverseNum（b））;
publicclassFifteenNum{
publicstaticintopenNum=0;
publicstaticintclosedNum=0;
publicenumDirection{UP,RIGHT,DOWN,LEFT};
publicstaticfinalintn=Main.N;
staticList<
open=newArrayList<
closed=newArrayList<
publicstaticbooleanchangeTo（Directiondirection,inti,intj,intdata_temp[][]）{inttemp;
switch（direction）{
caseUP:
{
if（i>
=1）{
temp=data_temp[i][j];
data_temp[i][j]=data_temp[i-1][j];
data_temp[i-1][j]=temp;
}else{
caseRIGHT:
if（j<
=2）{
data_temp[i][j]=data_temp[i][j+1];
data_temp[i][j+1]=temp;
caseDOWN:
if（i<
data_temp[i][j]=data_temp[i+1][j];
data_temp[i+1][j]=temp;
caseLEFT:
if（j>
data_temp[i][j]=data_temp[i][j-1];
data_temp[i][j-1]=temp;
publicstaticbooleanoppositeDirection（Directiond1,Directiond2）{
if（d1==Direction.UP&
&
d2==Direction.DOWN||d1==Direction.DOWN&
d2==Direction.UP）{
returntrue;
}elseif（d1==Direction.RIGHT&
d2==Direction.LEFT||d1==Direction.LEFT&
d2==Direction.RIGHT）{
returnfalse;
publicstaticNodemoveManHa（Nodenode1）{
Directiondirection[]={Direction.UP,Direction.RIGHT,Direction.DOWN,
Direction.LEFT};
inti=0;
intj=0;
intwrongNum;
booleanisOver=false;
//设定初始节点的参数
node1.setH（0）;
node1.setW（Data.manHa（node1.data））;
//曼哈顿
node1.setF（node1.getW（）+node1.getH（））;
Nodenode=null;
open.add（node1）;
node=open.remove（O）;
inta=0;
while（node.getW（）!
//定位要扩展节点的空格所在的位置
for（intx=0;
x<
x++）{
for（inty=0;
y<
y++）{
if（node.data[x][y]==0）{
i=x;
j=y;
//System.out.println（”
空格的坐标="
j="
+j）
inttemp[][]=newint[n][n];
//对刚才从open表中取岀的节点试探性的进行四个方向的扩展
for（intdir_index=0;
dir_index<
4;
dir_index++）{
if（FifteenNum.oppositeDirection（node.getLast_Dirction（）,direction[dir_index]））{
continue;
Data.arrayCopy（temp,node.data）;
if（FifteenNum.changeTo（direction[dir_index],i,j,temp））{
wrongNum=Data.manHa（temp）;
//曼哈顿距离
Nodenode_temp=newNode（te
升级会员 