智能大作业.docx
《智能大作业.docx》由会员分享,可在线阅读,更多相关《智能大作业.docx(14页珍藏版)》请在冰点文库上搜索。
智能大作业
人工智能及其应用
大作业
宋洋02115089
徐晓雅02115090
八数码难题
一.题目
八数码难题的宽度优先搜索
二.实验目的
在3×3组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1-8八个数码中的某一个数码。
棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。
给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态),如何移动将牌,实现从初始状态到目标状态的转变。
三.实验设备及软件环境
实验设备:
个人计算机win764位
软件环境:
MicrosoftVisualC++6.0
四.实验方法:
宽度优先搜索
算法描述
(1)把起始节点放到open表中(如果该起始节点为一目标节点,则求得一个解答)。
(2)如果open表是个空表,则没有解,失败退出;否则继续。
(3)把第一个节点(节点n)从open表移出,并把它放入closed的扩展节点表中。
(4)扩展节点n。
如果没有后继节点,则转向步骤
(2)
(5)把n的所有后继节点放到open表的末端,并提供从这些后继节点回到n的指针。
(6)如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向步骤
(2)。
算法流程图
程序代码
#include
#include
#include
#include
#include
usingnamespacestd;
#defineHashTableSize362881
#defineNOT!
#defineUP0
#defineDOWN1
#defineLEFT2
#defineRIGHT3
#defineBitchar
typedefstructmaps
{
Bitdetail[9];
intmyindex;//记录自己节点在hash表中的位置
Bitposition;//记录空格(0)在序列中的位置
}Map,*PMap;
Maporg;//初始状态
intEndIndex;//目标,上移,下移,左移,右移
intconstderection[4]={-3,3,-1,1};
//可移动的四个方向
intconstFactorial[9]={40320,5040,720,120,24,6,2,1,1};
intHashTable[HashTableSize]={0};
//hash表,其中记录的是上一个父节点对应的位置
/****八数码的输入(在这里不做任何输入检查,均认为输入数据是正确的)***/
voidinput()
{
inti,j;
intsum,count,index;
for(i=0;i<9;i++)
{
scanf("%1d",&org.detail[i]);
org.detail[i]||(org.position=i);
}
for(i=0;i<9;i++)//计算逆序
{
if(0==org.detail[i])
continue;
for(j=0;j
sum+=(0!
=org.detail[j]&&org.detail[j]}
for(i=0,index=0;i<9;i++)
//计算初始状态的hash值
{
for(j=0,count=0;j
count+=org.detail[j]>org.detail[i];
index+=Factorial[org.detail[i]]*count;
}
org.myindex=index+1;
EndIndex=sum%2?
161328:
322561;//目标状态的hash值
return;
}
/***hash值的计算*Parent:
父状态的hash值*direct:
移动的方向**/
inlineintHashValue(Map&Parent,int&direct)
{
inti=Parent.position;
intnewindex=Parent.myindex;
Bit*p=Parent.detail;
switch(direct)
{
caseUP:
{
newindex-=3*40320;
newindex+=(p[i-2]>p[i-3])?
(Factorial[p[i-3]]):
(-Factorial[p[i-2]]);
newindex+=(p[i-1]>p[i-3])?
(Factorial[p[i-3]]):
(-Factorial[p[i-1]]);
break;
}
caseDOWN:
{
newindex+=3*40320;
newindex-=(p[i+2]>p[i+3])?
(Factorial[p[i+3]]):
(-Factorial[p[i+2]]);
newindex-=(p[i+1]>p[i+3])?
(Factorial[p[i+3]]):
(-Factorial[p[i+1]]);
break;
}
caseLEFT:
returnnewindex-40320;break;
caseRIGHT:
returnnewindex+40320;break;
}
returnnewindex;
}
/****广度优先搜索***/
voidBfs()
{
queue
Queue.push(org);
HashTable[org.myindex]=-1;
while(NOTQueue.empty())
{
Mapnode=Queue.front();
Queue.pop();
for(intk=0;k<4;k++)
{
Maptmp=node;
tmp.position=node.position+derection[k];
if(tmp.position<0||tmp.position>8||(k>1&&tmp.position/3!
=node.position/3))
continue;
tmp.myindex=HashValue(node,k);
if(0!
=HashTable[tmp.myindex])continue;
tmp.detail[node.position]=tmp.detail[tmp.position];
//移动空格
tmp.detail[tmp.position]=0;
HashTable[tmp.myindex]=node.myindex;
//状态记录到hashtable中
if(node.myindex==EndIndex)return;
Queue.push(tmp);
}
}
return;
}
/****通过hash表中记录的进行查找路径***/
voidFindPath()
{
intnowindex;
intcount=0;
intnixu[9],result[9];
inti,j,k;
stackStack;
Stack.push(EndIndex);
nowindex=EndIndex;
while(-1!
=HashTable[nowindex])
{
Stack.push(HashTable[nowindex]);
nowindex=HashTable[nowindex];
}
printf("共需:
%d步\n",Stack.size()-1);
getchar();
while(NOTStack.empty())
{
nowindex=Stack.top()-1;
Stack.pop();
for(i=0;i<9;i++)//计算出逆序
{
nixu[i]=nowindex/Factorial[i];
nowindex%=Factorial[i];
}
memset(result,-1,9*sizeof(int));
for(i=0;i<9;i++)//根据逆序计算排列
{
for(j=0,k=nixu[i];j<9;j++)
{
if(result[j]==-1)k--;
if(k<0)break;
}
result[j]=i;
}
for(i=0;i<9;i++)
{
printf("%3d",result[i]);
if(2==i%3)printf("\n");
}
if(0!
=Stack.size())
{
printf("\n↓第%d步\n",++count);
getchar();
}
}
printf("\nTheEnd!
\n");
return;
}
intmain()
{
input();//输入要排序的序列0--8
longtime=GetTickCount();
Bfs();
printf("计算用时:
%dMS\n",GetTickCount()-time);
FindPath();
return0;//返回结果
}
五.实验结果
程序运行结果:
搜索树:
2
8
3
1
4
7
6
5
2
8
3
1
4
7
6
5
2
3
1
8
4
7
6
5
2
8
3
1
6
4
7
5
2
8
3
1
4
7
6
5
2
8
3
1
4
5
7
6
8
3
2
1
4
7
6
5
……
……
……
搜索路径:
2 8 3
1 0 4n=1
7 6 5
2 0 3
1 8 4 n=3
7 6 5
0 2 3
1 8 4 n=8
7 6 5
1 2 3
0 8 4 n=16
7 6 5
1 2 3
8 0 4 n=27
7 6 5
共5步,27个节点
六.实验分析
由上面的结果,通过和其它的算法比较,我得出了以下对广度优先法的归纳:
广度优先搜索法在有解的情形总能保证搜索到最短路经,也就是移动最少步数的路径。
但广度优先搜索法的最大问题在于搜索的结点数量太多,因为在广度优先搜索法中,每一个可能扩展出的结点都是搜索的对象。
随着结点在搜索树上的深度增大,搜索的结点数会很快增长,并以指数形式扩张,从而所需的存储空间和搜索花费的时间也会成倍增长。
在进行广度搜索时候,将父结点所在的数组索引记录在子结点中了,所以得到目标排列的时候,我们只要从子结点逆向搜索就可以得到最优搜索路径了。
用变量m_iPathsize来记录总步数。
七.结论
通过这次实验我认识到了人工智能的一个典型的应用,也让我在一定程度上了解了人工智能的发展。
当然也发现自己的许多不足,真的是书到用时方恨少啊,以后还得多动手了,而不只是掌握课本知识。