1408090213闫伟明(人工智能实验3)

人工智能上机实验报告学号：1408090213姓名：闫伟明所在系：信息学院班级：惠普测试142班实验名称：知识表示方法及应用实验日期2016年12月3日实验指导教师李辉实验机房A401------------------------------------------------------------------------------------------------------1.实验目的：(1)在掌握状态空间搜索策略的基础上，理解知识表示的方法。(2)能够应用知识表示方法，解决实际问题。2.实验内容：(1)M-C问题描述有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。(2)基本要求：1.输入：牧师人数(即野人人数)：n；小船一次最多载人量：c。2.输出：若问题无解，则显示Failed，否则，显示Successed输出一组最佳方案。用三元组(X1,X2,X3)表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程：初始状态-中间状态-目标状态。3.例：当输入n=2，c=2时，输出：221-110-211-010-021-0004.其中：X1表示起始岸上的牧师人数；X2表示起始岸上的野人人数；X3表示小船现在位置(1表示起始岸，0表示目的岸)。5.要求：写出算法的设计思想和源程序，并以图形用户界面实现人机交互，进行输入和输出结果，如：Pleaseinputn:2Pleaseinputc:2SuccessedorFailed?:SuccessedOptimalProcedure:221-110-211-010-021-0003.算法设计packagecn.xiaoyangege.mvc.yerenguohe;//CrossRiverQuestion.javaimportjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassCrossRiverQuestion{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intn=0;intc=0;Stringns=null;Stringcs=null;booleanflag;do{flag=false;System.out.print(Pleaseinputn:);ns=scanner.nextLine();System.out.print(Pleaseinputc:);cs=scanner.nextLine();try{n=Integer.parseInt(ns);c=Integer.parseInt(cs);}catch(NumberFormatExceptione){System.out.println(输入不合法。);flag=true;continue;}if(!flag&&(n0||c0)){System.out.println(输入不合法。);flag=true;}}while(flag);scanner.close();CrossRiverQuestionq=newCrossRiverQuestion(n,c);q.solveQuestion();}privateintpeoNum;privateintsavageNum;privateListNoderesultList=newArrayListNode();publicListNodesolveQuestion(){Noden=newNode(peoNum,savageNum,0,0,0,newArrayListInteger(),0,0);booleandfsResult=dfs(n);System.out.print(SucceedorFailed?:);if(dfsResult){System.out.println(Succeed.);System.out.print(OptimalProcedure:);resultList.add(0,n);for(Nodenode:resultList){System.out.print(node.getLeftPeo()++node.getLeftSavage()++(1-node.getCURR_STATE())+--);}System.out.println(End);returnresultList;}else{System.out.println(Failed.);}returnnull;}publicCrossRiverQuestion(intpeoNum,intsavageNum){super();this.peoNum=peoNum;this.savageNum=savageNum;}privatebooleandfs(Noden){if(n.hasVisited()){returnfalse;}n.addCheckSum();if(n.getLeftPeo()==0&&n.getLeftSavage()==0){returntrue;}if(n.getLeftPeo()0||n.getRightPeo()0||n.getLeftSavage()0||n.getRightSavage()0){returnfalse;}if(n.getLeftPeo()n.getLeftSavage()&&n.getLeftPeo()0){returnfalse;}if(n.getRightPeo()n.getRightSavage()&&n.getRightPeo()0){returnfalse;}if(n.getCURR_STATE()==n.getStateBoatLeft()){Noden1=newNode(n.getLeftPeo()-1,n.getLeftSavage()-1,n.getRightPeo()+1,n.getRightSavage()+1,n.getStateBoatRight(),n.getNodesCheckSum(),1,1);if(dfs(n1)){resultList.add(0,n1);returntrue;}Noden4=newNode(n.getLeftPeo()-2,n.getLeftSavage(),n.getRightPeo()+2,n.getRightSavage(),n.getStateBoatRight(),n.getNodesCheckSum(),2,0);if(dfs(n4)){resultList.add(0,n4);returntrue;}Noden5=newNode(n.getLeftPeo(),n.getLeftSavage()-2,n.getRightPeo(),n.getRightSavage()+2,n.getStateBoatRight(),n.getNodesCheckSum(),0,2);if(dfs(n5)){resultList.add(0,n5);returntrue;}}else{Noden6=newNode(n.getLeftPeo(),n.getLeftSavage()+1,n.getRightPeo(),n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),0,1);if(dfs(n6)){resultList.add(0,n6);returntrue;}Noden7=newNode(n.getLeftPeo()+1,n.getLeftSavage(),n.getRightPeo()-1,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),1,0);if(dfs(n7)){resultList.add(0,n7);returntrue;}Noden1=newNode(n.getLeftPeo()+1,n.getLeftSavage()+1,n.getRightPeo()-1,n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),1,1);if(dfs(n1)){resultList.add(0,n1);returntrue;}Noden4=newNode(n.getLeftPeo()+2,n.getLeftSavage(),n.getRightPeo()-2,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),2,0);if(dfs(n4)){resultList.add(0,n4);returntrue;}Noden5=newNode(n.getLeftPeo(),n.getLeftSavage()+2,n.getRightPeo(),n.getRightSavage()-2,n.getStateBoatLeft(),n.getNodesCheckSum(),0,2);if(dfs(n5)){resultList.add(0,n5);returntrue;}}returnfalse;}publicListNodegetResultList(){returnresultList;}}classNode{privateListIntegernodesCheckSum=newArrayListInteger();privateintleftPeo;privateintrightPeo;privateintleftSavage;privateintrightSavage;privateintCURR_STATE=0;privateintonBoatPeoNum=0;privateintonBoatSavageNum=0;privatefinalintSTATE_BOAT_LEFT=0;privatefinalintSTATE_BOAT_RIGHT=1;publicNode(intleftPeo,intleftSavage,intrightPeo,intrightSavage,intstate,ListIntegercheckSumList,intonBoatPeoNum,intonBoatSavageNum){CURR_STATE=state;this.leftPeo=leftPeo;this.leftSavage=leftSavage;this.rightPeo=rightPeo;this.rightSavage=rightSavage;nodesCheckSum.addAll(checkSumList);this.onBoatPeoNum=onBoatPeoNum;this.onBoatSavageNum=onBoatSavageNum;}publicintgetLeftPeo(){returnleftPeo;}publicvoidsetLeftPeo(intleftPeo){this.leftPeo=leftPeo;}publicintgetRightPeo(){returnrightPeo;}publicvoidsetRightPeo(intrightPeo){this.rightPeo=rightPeo;}publicintgetLeftSavage(){returnleftSavage;}publicvoidsetLeftSavage(intleftSavage){this.leftSavage=leftSav