人工智能实验报告完整版.docx
《人工智能实验报告完整版.docx》由会员分享，可在线阅读，更多相关《人工智能实验报告完整版.docx（35页珍藏版）》请在冰点文库上搜索。
人工智能实验报告完整版
江苏科技大学
试验汇报
（/第2学期）
课程名称:
人工智能
学生姓名:
陈嘉生
学生学号:
院系:
数理学院
专业:
信息与计算科学
5月18日
试验一:
知识表示方法
一、试验目
状态空间表示法是人工智能领域最基础知识表示方法之一,也是深入学习状态空间搜索策略基础,本试验经过牧师与野人渡河问题,强化学生对知识表示了解和应用,为人工智能后续步骤课程奠定基础。
二、问题描述
有n个牧师和n个野人准备渡河,但只有一条能容纳c个人小船,为了预防野人侵犯牧师,要求不管在何处,牧师人数不得少于野人人数（除非牧师人数为0）,且假定野人与牧师都会划船,试设计一个算法,确定她们能否渡过河去,若能,则给出小船往返次数最少最好方案。
三、基础要求
输入:
牧师人数（即野人人数）:
n;小船一次最多载人量:
c。
输出:
若问题无解,则显示Failed,不然,显示Successed输出一组最好方案。
用三元组（X1,X2,X3）表示渡河过程中状态。
并用箭头连接相邻状态以表示迁移过程:
初始状态->中间状态->目标状态。
例:
当输入n=2,c=2时,输出:
221->110->211->010->021->000
其中:
X1表示起始岸上牧师人数;X2表示起始岸上野人人数;X3表示小船现在位置（1表示起始岸,0表示目岸）。
要求:
写出算法设计思想和源程序,并以图形用户界面实现人机交互,进行输入和输出结果,如:
Pleaseinputn:
2Pleaseinputc:
2
SuccessedorFailed?
:
Successed
OptimalProcedure:
221->110->211->010->021->000
四、试验组织运行要求
本试验采取集中讲课形式,每个同学独立完成上述试验要求。
五、试验条件
每人一台计算机独立完成试验。
六、试验代码
Main.cpp
#include
#include"RiverCrossing.h"
usingnamespacestd;
//主函数
voidmain（）
{
RiverCrossing:
:
ShowInfo（）;
intn,c;
cout<<"Pleaseinputn:
";
cin>>n;
cout<<"Pleaseinputc:
";
cin>>c;
RiverCrossingriverCrossing（n,c）;
riverCrossing.solve（）;
system（"pause"）;
}
RiverCrossing.h
#pragmaonce
#include
//船
classBoat
{
public:
staticintc;
intpastor;//牧师
intsavage;//野人
Boat（intpastor,intsavage）;
};
//河岸状态
classState
{
public:
staticintn;
intiPastor;//牧师数量
intiSavage;//野人数量
intiBoatAtSide;//船所在河岸
State*pPrevious;//前一个状态
State（intpastor,intsavage,intboatAtSide）;
intgetTotalCount（）;//取得此岸总人数
boolcheck（）;//检验人数是否符合实际
boolisSafe（）;//检验是否安全
Stateoperator+（Boat&boat）;
Stateoperator-（Boat&boat）;
booloperator==（State&state）;
};
//过河问题
classRiverCrossing
{
private:
std:
:
listopenList,closeList;
StateendState;
boolmove（State*nowState,Boat*boat）;//进行一次决议
State*findInList（std:
:
list&listToCheck,State&state）;//检验某状态节点是否在列表中
voidprint（State*endState）;//打印结果
public:
staticvoidShowInfo（）;
RiverCrossing（intn,intc）;
boolsolve（）;//求解问题
};
RiverCrossing.cpp
#include"RiverCrossing.h"
#include
#include
#include
usingnamespacestd;
//类静态变量定义
intState:
:
n=0;
intBoat:
:
c=0;
/*=========================Methodsforclass"Boat"=========================*/
Boat:
:
Boat（intpastor,intsavage）
{
this->pastor=pastor;
this->savage=savage;
}
/*=========================Methodsforclass"State"=========================*/
//结构函数
State:
:
State（intpastor,intsavage,intboatAtSide）
{
this->iPastor=pastor;
this->iSavage=savage;
this->iBoatAtSide=boatAtSide;
this->pPrevious=NULL;
}
//获取此岸总人数
intState:
:
getTotalCount（）
{
returniPastor+iSavage;
}
//检验人数是否在0到n之间
boolState:
:
check（）
{
return（iPastor>=0&&iPastor<=n&&iSavage>=0&&iSavage<=n）;
}
//根据规则检验牧师得否安全
boolState:
:
isSafe（）
{
//此岸安全:
x1==0||x1>=x2
//彼岸安全:
（n-x1）==0||（n-x1）>=（n-x2）
//将上述条件联立后得到以下条件
return（iPastor==0||iPastor==n||iPastor==iSavage）;
}
//重载+符号,表示船开到此岸
StateState:
:
operator+（Boat&boat）
{
Stateret（iPastor+boat.pastor,iSavage+boat.savage,iBoatAtSide+1）;
ret.pPrevious=this;
returnret;
}
//重载-符号,表示船以后岸开走
StateState:
:
operator-（Boat&boat）
{
Stateret（iPastor-boat.pastor,iSavage-boat.savage,iBoatAtSide-1）;
ret.pPrevious=this;
returnret;
}
//重载==符号,比较两个节点是否是相同状态
boolState:
:
operator==（State&state）
{
return（this->iPastor==state.iPastor&&this->iSavage==state.iSavage&&this->iBoatAtSide==state.iBoatAtSide）;
}
/*=======================Methodsforclass"RiverCrossing"=======================*/
//显示信息
voidRiverCrossing:
:
ShowInfo（）
{
cout<<"************************************************"<cout<<"牧师与野人过河问题求解"<cout<<"by陈嘉生"<cout<<"************************************************"<}
//结构函数
RiverCrossing:
:
RiverCrossing（intn,intc）
:
endState（0,0,0）
{
State:
:
n=n;
Boat:
:
c=c;
}
//处理问题
boolRiverCrossing:
:
solve（）
{
openList.push_back（newState（State:
:
n,State:
:
n,1））;
while（!
openList.empty（））{
//获取一个状态为目前状态
State*nowState=openList.front（）;
openList.pop_front（）;
closeList.push_back（nowState）;
//从目前状态开始决议
if（nowState->iBoatAtSide==1）{//船在此岸
//过河人越多越好,且野人优先
intcount=nowState->getTotalCount（）;
count=（Boat:
:
c>=count?
count:
Boat:
:
c）;
for（intcapticy=count;capticy>=1;--capticy）{
for（inti=0;i<=capticy;++i）{
Boatboat（i,capticy-i）;
if（move（nowState,&boat））
returntrue;
}
}
}elseif（nowState->iBoatAtSide==0）{//船在彼岸
//把船开回来人要最少,且牧师优先
for（intcapticy=1;capticy<=Boat:
:
c;++capticy）{
for（inti=0;i<=capticy;++i）{
Boatboat（capticy-i,i）;
if（move（nowState,&boat））
returntrue;
}
}
}
}
print（NULL）;
returnfalse;
}
//实施一步决议,将得到新状态添加到列表,返回是否达成目标状态
boolRiverCrossing:
:
move（State*nowState,Boat*boat）
{
//取得下一个状态
State*destState;
if（nowState->iBoatAtSide==1）{
destState=newState（*nowState-*boat）;//船离开此岸
}elseif（nowState->iBoatAtSide==0）{
destState=newState（*nowState+*boat）;//船开到此岸
}
if（destState->check（））{//检验人数
if（*destState==endState）{//是否达成目标状态
closeList.push_back（destState）;
print（destState）;
returntrue;//找到结果
}elseif（destState->isSafe（））{//检验是否安全
if（!
findInList（openList,*destState）&&!
findInList（closeList,*destState））{//检验是否在表中
//添加没出现过状态节点到open表
openList.push_back（destState）;
returnfalse;
}
}
}
deletedestState;
returnfalse;
}
//检验给定状态是否存在于列表中
State*RiverCrossing:
:
findInList（list&listToCheck,State&state）
{
for（list:
:
iteratorite=listToCheck.begin（）;ite!
=listToCheck.end（）;++ite）{
if（**ite==state）
return*ite;
}
returnNULL;
}
//依据达成目标状态,回溯打印出求解过程
voidRiverCrossing:
:
print（State*endState）
{
cout<<"================================================"<if（!
endState）{
cout<<"Searchfailed!
"<}else{
cout<<"Searchsuccessed!
"<cout<<"OptimalProcedure:
"<State*pState=endState;
stackst;//用栈将链表逆序,方便输出
while（pState）{
st.push（pState）;
pState=pState->pPrevious;
}
intcount=0;
while（!
st.empty（））{
pState=st.top（）;
st.pop（）;
cout<iPastor<<","<iSavage<<","<iBoatAtSide;
if（st.size（）>0）
cout<<"->";
if（++count%5==0）//每五个步骤换行
cout<}
cout<cout<<"Totalmove:
"<}
cout<<"================================================"<}
七、试验结果
试验二:
九宫重排
一、试验目
A*算法是人工智能领域最关键启发式搜索算法之一,本试验经过九宫重排问题,强化学生对A*算法了解与应用,为人工智能后续步骤课程奠定基础。
二、问题描述
给定九宫格初始状态,要求在有限步操作内,使其转化为目标状态,且所得到解是代价最小解（即移动步数最少）。
如:
三、基础要求
输入:
九宫格初始状态和目标状态
输出:
重排过程,即路径状态
四、试验组织运行要求
本试验采取集中讲课形式,每个同学独立完成上述试验要求。
五、试验条件
每人一台计算机独立完成试验。
六、试验代码
Main.cpp
#include
#include"NineGrid.h"
usingnamespacestd;
//主函数
voidmain（）
{
NineGrid:
:
ShowInfo（）;
stringstart,end;
cout<<"Pleaseinputtheinitialstate:
（ex:
）"<cin>>start;
cout<<"Pleaseinputthetargetstate:
（ex:
）"<cin>>end;
NineGridnineGrid（start,end）;
nineGrid.solve（）;
system（"pause"）;
}
NineGrid.h
#pragmaonce
#include
#include
#include
usingnamespacestd;
#defineSPACE'0'
#defineAT（s,x,y）（s）[（x）*3+（y）]
enumMove{
UP=0,DOWN=1,LEFT=2,RIGHT=3
};
//九宫格状态
classState
{
public:
staticState*pEndState;//指向目标状态,用于评价h值
stringgrid;//用字符串保留目前棋盘状态
intx,y;//空格所在位置
intmoves;//到此状态移动次数
intvalue;//价值
State*pPrevious;//前一个状态
State（string&grid,State*pPrevious=NULL）;
intgetReversedCount（）;//获取逆序数
voidevaluate（）;//评价函数
boolcheck（Movemove）;//检验是否能够移动
StatetakeMove（Movemove）;//实施移动,生成子状态
//重载==运算符,判定两个状态是否相等
inlinebooloperator==（State&state）{returngrid==state.grid;}
};
//九宫重排问题
classNineGrid
{
private:
vectoropenList,closeList;
StatestartState,endState;
clock_tstartTime;
boolcompareReversed（）;//比较逆序数奇偶性是否相同
booltakeMove（State*nowState,Movemove）;//进行一次决议
State*findInList（vector&listToCheck,State&State）;//检验某状态节点是否在列表中
voidprint（State*endState）;//打印结果
//用于排序
staticboolgreater_than（constState*state1,constState*state2）;
public:
staticvoidShowInfo（）;//显示信息
NineGrid（string&start,string&dest）;
boolsolve（）;//求解问题
};
NineGrid.cpp
#include"NineGrid.h"
#include
#include
#include
usingnamespacestd;
State*State:
:
pEndState=NULL;
/*=======================Methodsforclass"State"=======================*/
//结构函数
State:
:
State（string&grid,State*pPrevious）
{
this->grid=grid;
this->pPrevious=pPrevious;
if（this->pPrevious）
this->moves=pPrevious->moves+1;
else
this->moves=0;
this->value=0;
evaluate（）;
for（inti=0;i<3;++i）{
for（intj=0;j<3;++j）{
if（AT（grid,i,j）==SPACE）{
x=i;
y=j;
return;
}
}
}
}
boolState:
:
check（Movemove）
{
switch（move）{
caseUP:
if（x-1<0）
returnfalse;
break;
caseDOWN:
if（x+1>=3）
returnfalse;
break;
caseLEFT:
if（y-1<0）
returnfalse;
break;
caseRIGHT:
if（y+1>=3）
returnfalse;
break;
}
returntrue;
}
StateState:
:
takeMove（Movemove）
{
intdestX,destY;
switch（move）{
caseUP:
destX=x-1;
destY=y;
break;
caseDOWN:
destX=x+1;
destY=y;
break;
caseLEFT:
destX=x;
destY=y-1;
break;
caseRIGHT:
destX=x;
destY=y+1;
break;
}
stringtGrid=grid;
chart=AT（tGrid,destX,destY）;
AT（tGrid,destX,
升级会员 