昆明理工大学 八数码实验报告.docx
《昆明理工大学 八数码实验报告.docx》由会员分享，可在线阅读，更多相关《昆明理工大学 八数码实验报告.docx（26页珍藏版）》请在冰点文库上搜索。
昆明理工大学八数码实验报告
昆明理工大学信息工程与自动化学院学生实验报告
（2014—2015学年第1学期）
课程名称：
人工智能及其应用开课实验室：
信自楼5042014年11月26日
年级、专业、班
计科122班
学号
201210405204
邹华宇
成绩
实验项目名称
八数码问题
指导教师
吴霖
教师评语
该同学是否了解实验原理：
A.了解□B.基本了解□C.不了解□
该同学的实验能力：
A.强□B.中等□C.差□
该同学的实验是否达到要求：
A.达到□B.基本达到□C.未达到□
实验报告是否规范：
A.规范□B.基本规范□C.不规范□
实验过程是否详细记录：
A.详细□B.一般□C.没有□
教师签名：
年月日
一、上机目的及内容
1.上机内容：
求解八数码问题。
问题描述：
八数码难题，问题描述：
在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态S1如图所示，可以使用的操作有：
空格上移，空格左移，空格右移，空格下移。
只允许位于空格左，上，右，下方的牌移入空格。
用广度优先搜索策略寻找从初始状态到目标状态的解路径。
2.上机目的:
（1）复习程序设计和数据结构课程的相关知识；
（2）熟悉人工智能系统中的问题求解过程；
（3）熟悉对八码数问题的建模、求解及编程语言的运用。
二、实验原理及基本技术路线图（方框原理图或程序流程图）
（1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点的表中；
（2）建立一个叫做CLOSED的已扩展节点表，其初始为空表；
（3）LOOP:
若OPEN表是空表，则失败退出；
（4）选择OPEN表上的第一个节点，把它从OPEN表移除并放进CLOSED表中，称此节点为节点n；
（5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的；
（6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。
把M的这些成员作为n的后继节点舔到图中；
（7）对那些未曾在G中出现过的M成员设置一个通向n的指针。
把M的这些成员加进OPEN表。
对已经在OPEN表或CLOSED表上的成员，确定是否需要更改通到n的指针方向；
（8）按某一任意方式或按某个探视值，重排OPEN表。
宽度优先算法实现过程
（1）把起始节点放到OPEN表中；
（2）如果OPEN是个空表，则没有解，失败退出；否则继续；
（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；
（4）扩展节点n。
如果没有后继节点，则转向
（2）；
（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；
（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转
（2）。
深度优先实现过程
（1）把起始节点S放入未扩展节点OPEN表中。
如果此节点为一目标节点，则得一个解；
（2）如果OPEN为一空表，则失败退出；
（3）把第一个节点从OPEN表移到CLOSED表；
（4）如果节点n的深度等于最大深度，则转向
（2）；
（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。
如果没有后裔，则转向
（2）；
（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向
（2）。
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1台PC及VISUALC++6.0软件
四、实验方法、步骤（或：
程序代码或操作过程）
1、先创建项目，新建SourceFile文件：
main.cpp。
#include
#include"Node.h"
#include"Queue.h"
#include"Search.h"
#include"Tree.h"
voidCreateNode1（std:
:
vector&s）
{
s.push_back
（2）;
s.push_back（8）;
s.push_back（3）;
s.push_back
（1）;
s.push_back（0）;
s.push_back（4）;
s.push_back（7）;
s.push_back（6）;
s.push_back（5）;
}
voidCreateNode4（std:
:
vector&d）
{
d.push_back
（2）;
d.push_back（8）;
d.push_back（3）;
d.push_back
（1）;
d.push_back（6）;
d.push_back（4）;
d.push_back（7）;
d.push_back（0）;
d.push_back（5）;
}
voidCreateNode8（std:
:
vector&d）
{
d.push_back（0）;
d.push_back
（2）;
d.push_back（3）;
d.push_back
（1）;
d.push_back（8）;
d.push_back（4）;
d.push_back（7）;
d.push_back（6）;
d.push_back（5）;
}
voidCreateNode20（std:
:
vector&d）
{
d.push_back
（2）;
d.push_back（0）;
d.push_back（8）;
d.push_back
（1）;
d.push_back（4）;
d.push_back（3）;
d.push_back（7）;
d.push_back（6）;
d.push_back（5）;
}
voidCreateNode27（std:
:
vector&d）
{
d.push_back
（1）;
d.push_back
（2）;
d.push_back（3）;
d.push_back（8）;
d.push_back（0）;
d.push_back（4）;
d.push_back（7）;
d.push_back（6）;
d.push_back（5）;
}
voidCreateNode_test1（std:
:
vector&d）
{
d.push_back（7）;
d.push_back（6）;
d.push_back（5）;
d.push_back（4）;
d.push_back（0）;
d.push_back
（1）;
d.push_back（3）;
d.push_back（8）;
d.push_back
（2）;
}
voidtest_expand（）
{
std:
:
vectors;
CreateNode1（s）;
std:
:
vectord;
CreateNode4（d）;
Nodesource（s）;
Nodedest（d）;
source.Display（）;
Searchsearch（&source）;
std:
:
cout<}
voidtest_search（）
{
std:
:
vectors;
CreateNode1（s）;
std:
:
vectord;
CreateNode4（d）;
Nodesource（s）;
Nodedest（d）;
source.Display（）;
dest.Display（）;
Searchsearch（&source）;
search.Find（&dest）;
search.DisplayRoute（）;
}
voidtest_search2level（）
{
std:
:
vectors;
CreateNode1（s）;
std:
:
vectord;
CreateNode8（d）;
Nodesource（s）;
Nodedest（d）;
source.Display（）;
dest.Display（）;
Searchsearch（&source）;
search.Find（&dest）;
search.DisplayRoute（）;
}
voidtest_search_lab1（）
{
std:
:
vectors;
CreateNode1（s）;
std:
:
vectord;
CreateNode27（d）;
Nodesource（s）;
Nodedest（d）;
source.Display（）;
dest.Display（）;
Searchsearch（&source）;
search.Find（&dest）;
search.DisplayRoute（）;
}
intmain（intargc,char**argv）
{
//test_expand（）;
//test_search（）;
//test_search2level（）;
//test_search_lab1（）;
std:
:
vectors;
CreateNode1（s）;
std:
:
vectord;
CreateNode27（d）;
Nodesource（s）;
Nodedest（d）;
source.Display（）;
dest.Display（）;
Searchsearch（&source）;
search.Find（&dest）;
search.DisplayRoute（）;
return0;
}
2、新建SourceFile文件：
Node.cpp。
#ifndefPROGECT_1_NODE
#definePROGECT_1_NODE
#include
#include"Search.h"
enumOP
{
EMPTY,
UP,
DOWN,
LEFT,
RIGHT
};
boolIsOpposite（OPopa,OPopb）;
classNode
{
public:
Node（std:
:
vectorconst&state）;
boolExpand（Nodeconst&destNode,Search&search）;
voidDisplay（）const;
voidDisplayRoute（）const;
booloperator==（Nodeconst&v）const;
private:
Node*CreateChild（OPop）;
intFindEmptySpaceId（）const;
std:
:
vectorGenerateLegalOperators（intspaceId）const;
intCalIdBasedOP（OPop,intspaceId）const;
boolIsWithinRange（OPop,intspaceId）const;
std:
:
vectorm_state;
Node*m_pParent;
std:
:
vectorm_children;
OPm_op;
};
#endif//PROGECT_1_NODE
3新建HeardFile文件：
node.h。
#include
#include
#include"Node.h"
boolIsOpposite（OPopa,OPopb）
{
if（LEFT==opa&&RIGHT==opb）
returntrue;
if（RIGHT==opa&&LEFT==opb）
returntrue;
if（UP==opa&&DOWN==opb）
returntrue;
if（DOWN==opa&&UP==opb）
returntrue;
returnfalse;
}
Node:
:
Node（std:
:
vectorconst&state）
:
m_state（state）
m_pParent（NULL）
m_children（）
m_op（EMPTY）
{
}
voidShowOP（OPop）
{
switch（op）
{
caseEMPTY:
std:
:
cout<<"EMPTY";
break;
caseUP:
std:
:
cout<<"UP";
break;
caseDOWN:
std:
:
cout<<"DOWN";
break;
caseLEFT:
std:
:
cout<<"LEFT";
break;
caseRIGHT:
std:
:
cout<<"RIGHT";
break;
default:
exit（-1）;
}
}
voidShowOPs（std:
:
vectorconst&ops）
{
for（intid=0;id{
ShowOP（ops[id]）;
std:
:
cout<<"";
}
std:
:
cout<:
endl;
}
boolNode:
:
Expand（Nodeconst&destNode,Search&search）
{
intspaceId=FindEmptySpaceId（）;
std:
:
cout<<"spaceisat"<:
endl;
std:
:
vectorlegalOPs=GenerateLegalOperators（spaceId）;
ShowOPs（legalOPs）;
while（legalOPs.size（）>0）
{
OPop=legalOPs[legalOPs.size（）-1];
legalOPs.pop_back（）;
Node*pChild=CreateChild（op）;
if（*pChild==destNode）
{
search.SetDestPt（pChild）;
returntrue;
}
search.GetQueue（）.EnQueue（pChild）;
}
returnfalse;
}
voidNode:
:
Display（）const
{
for（inti=0;i{
std:
:
cout<}
std:
:
cout<:
endl;
std:
:
cout<<"pParent:
"<:
endl;
std:
:
cout<<"op:
";
ShowOP（m_op）;
std:
:
cout<:
endl;
std:
:
cout<<"";
for（intj=0;j{
std:
:
cout<}
std:
:
cout<:
endl;
}
voidNode:
:
DisplayRoute（）const
{
std:
:
vectorrouteOps;
Nodeconst*pNode=this;
while（NULL!
=pNode）
{
routeOps.push_back（pNode->m_op）;
pNode=pNode->m_pParent;
}
for（intid=routeOps.size（）-2;id>=0;--id）
{
ShowOP（routeOps[id]）;
std:
:
cout<<"";
}
std:
:
cout<:
endl;
}
boolNode:
:
operator==（Nodeconst&v）const
{
for（intid=0;id{
if（m_state[id]!
=v.m_state[id]）
returnfalse;
}
returntrue;
}
Node*Node:
:
CreateChild（OPop）
{
std:
:
vectorchildState=m_state;
intexchangePos1=FindEmptySpaceId（）;
intexchangePos2=CalIdBasedOP（op,exchangePos1）;
inttemp=childState[exchangePos1];
childState[exchangePos1]=childState[exchangePos2];
childState[exchangePos2]=temp;
Node*child=newNode（childState）;
child->m_pParent=this;
child->m_op=op;
m_children.push_back（child）;
returnchild;
}
intNode:
:
FindEmptySpaceId（）const
{
for（intid=0;id{
if（0==m_state[id]）
{
returnid;
}
}
return-1;
}
std:
:
vectorNode:
:
GenerateLegalOperators（intspaceId）const
{
std:
:
vectorallPossibleOps;
allPossibleOps.push_back（UP）;
allPossibleOps.push_back（DOWN）;
allPossibleOps.push_back（LEFT）;
allPossibleOps.push_back（RIGHT）;
std:
:
vectorops;
for（intid=0;id{
OPop=allPossibleOps[id];
if（IsOpposite（op,m_op））
{
continue;
}
if（IsWithinRange（op,spaceId））
{
ops.push_back（op）;
}
}
returnops;
}
intNode:
:
CalIdBasedOP（OPop,intspaceId）const
{
switch（op）
{
caseUP:
spaceId-=int（sqrt（m_state.size（）））;
break;
caseDOWN:
spaceId+=int（sqrt（m_state.size（）））;
break;
caseLEFT:
--spaceId;
break;
caseRIGHT:
++spaceId;
break;
default:
return-1;
}
returnspaceId;
}
boolNode:
:
IsWithinRange（OPop,intspaceId）const
{
spaceId=CalIdBasedOP（op,spaceId）;
if（spaceId>=0&&spaceId{
returntrue;
}
returnfalse;
}
4、新建SourceFile文件：
Queue.cpp。
#include"Queue.h"
voidQueue:
:
EnQueue（Node*pNode）
{
m_queue.push_back（pNode）;
}
Node*Queue:
:
DeQueue（）
{
if（m_queue.size（）==0）
{
returnNULL;
}
Node*pNode=m_queue[0];
m_queue.pop_front（）;
returnpNode;
}
5、新建HeardFile文件：
Queue.h。
#ifndefPROGECT_1_QUEUE
#definePROGECT_1_QUEUE
#include
classNode;
classQueue
{
public:
voidEnQueue（Node*pNode）;
Node*DeQueue（）;
private:
std:
:
dequem_queue;
};
#endif//PROGECT_1_QUEUE
6、新建SourceFile文件：
Search.cpp。
#include"Search.h"
#include"Node.h"
Search:
:
Search（Node*root）
:
m_queue（）
m_pDestNode（NULL）
{
m_queue.EnQueue（root）;
}
Node*Search:
:
Select（）
{
returnm_queue.DeQueue（）;
}
voidSearch:
:
Find（Node*destNode）
{
boolisFound=false;
while（!
isFound）
{
Node*pNode=Select（）;
pNode->Display（）;
isFound=pNode->Expand（*destNode,*this）;
}
}
voidSearch:
:
DisplayRoute（）const
{
升级会员 