人工智能-实验报告

实验一：知识表示方法一、实验目的状态空间表示法是人工智能领域最基本的知识表示方法之一，也是进一步学习状态空间搜索策略的基础，本实验通过牧师与野人渡河的问题，强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定基础。二、问题描述有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:2SuccessedorFailed?:SuccessedOptimalProcedure:221-110-211-010-021-000四、实验组织运行要求本实验采用集中授课形式，每个同学独立完成上述实验要求。五、实验条件每人一台计算机独立完成实验。六、实验代码Main.cpp#includeiostream#includeRiverCrossing.husingnamespacestd;//主函数voidmain(){RiverCrossing::ShowInfo();intn,c;coutPleaseinputn:;cinn;coutPleaseinputc:;cinc;RiverCrossingriverCrossing(n,c);riverCrossing.solve();system(pause);}RiverCrossing.h#pragmaonce#includelist//船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::listState*openList,closeList;StateendState;boolmove(State*nowState,Boat*boat);//进行一次决策State*findInList(std::listState*&listToCheck,State&state);//检查某状态节点是否在列表中voidprint(State*endState);//打印结果public:staticvoidShowInfo();RiverCrossing(intn,intc);boolsolve();//求解问题};RiverCrossing.cpp#includeRiverCrossing.h#includeiostream#includestack#includealgorithmusingnamespacestd;//类静态变量定义intState::n=0;intBoat::c=0;/*=========================MethodsforclassBoat=========================*/Boat::Boat(intpastor,intsavage){this-pastor=pastor;this-savage=savage;}/*=========================MethodsforclassState=========================*///构造函数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);}/*=======================MethodsforclassRiverCrossing=======================*///显示信息voidRiverCrossing::ShowInfo(){cout************************************************endl;cout牧师与野人过河问题求解endl;coutby1040501211陈嘉生endl;cout************************************************endl;}//构造函数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(listState*&listToCheck,State&state){for(listState*::iteratorite=listToCheck.begin();ite!=listToCheck.end();++ite){if(**ite==state)return*ite;}returnNULL;}//根据达到的目标状态，回溯打印出求解过程voidRiverCrossing::print(State*endState){cout================================================endl;if(!endState){coutSearchfailed!endl;}else{coutSearchsuccessed!endl;coutOp