人工智能实验报告27

1、江苏科技大学实验报告（2012/2013学年第2学期）课程名称：人工智能学生姓名：陈嘉生学生学号：1040501211院系：数理学院专业：信息与计算 科学2013年 5 月 18 日实验一：知识表示方法一、实验目的状态空间表示法是人工智能领域最基本的知识表示方法之一， 也是进一步学习状态空间搜索策略的基础， 本实验通过牧师与野人渡河的问题， 强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定基础。二、问题描述有 n 个牧师和 n 个野人准备渡河， 但只有一条能容纳 c 个人的小船， 为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数 (除非牧师人数为 0)，且假定野人

2、与牧师都会划船， 试设计一个算法， 确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。三、基本要求输入：牧师人数 (即野人人数 )： n；小船一次最多载人量： c。输出：若问题无解，则显示 Failed，否则，显示 Successed输出一组最佳方案。用三元组 (X1 , X2, X3 )表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程：初始状态 ->中间状态 ->目标状态。例：当输入 n=2，c=2 时，输出： 221->110->211->010->021->000其中： X 1 表示起始岸上的牧师人数； X2 表示起始岸上的野

3、人人数； X 3 表示小船现在位置 (1 表示起始岸， 0 表示目的岸 )。要求：写出算法的设计思想和源程序，并以图形用户界面实现人机交互，进行输入和输出结果，如：Please input n: 2Please input c: 2Successed or Failed?: SuccessedOptimal Procedure: 221->110->211->010->021->000四、实验组织运行要求本实验采用集中授课形式，每个同学独立完成上述实验要求。五、实验条件每人一台计算机独立完成实验。六、实验代码Main.cpp#include<iostream

4、>#include"RiverCrossing.h"usingnamespace std;/ 主函数voidmain()RiverCrossing:ShowInfo();intn, c;cout<< "Please input n: "cin>>n;cout<< "Please input c: "cin>>c;RiverCrossingriverCrossing(n, c);riverCrossing.solve();system("pause");River

5、Crossing.h#pragma once#include<list>/ 船classBoatpublic:staticintc;intpastor;/ 牧师intsavage;/ 野人Boat( intpastor,intsavage);/ 河岸状态classStatepublic:staticintn;intiPastor;/ 牧师数量intiSavage;/ 野人数量intiBoatAtSide;/ 船所在河岸State*pPrevious;/ 前一个状态State(intpastor,intsavage,intboatAtSide);intgetTotalCount();

6、/ 获得此岸总人数bool check();/ 检查人数是否符合实际bool isSafe();/ 检查是否安全Stateoperator + (Boat&boat);Stateoperator - (Boat&boat);booloperator = (State&state);/ 过河问题classRiverCrossingprivate:std:list<State *> openList, closeList;StateendState;bool move( State*nowState,Boat *boat);/ 进行一次决策State * fin

7、dInList(std:list<State *> &listToCheck,State&state);/ 检查某状态节点是否在列表中void print(State *endState);/ 打印结果public:staticvoidShowInfo();RiverCrossing(intn,intc);bool solve();/ 求解问题;RiverCrossing.cpp#include"RiverCrossing.h"#include<iostream>#include<stack>#include<alg

8、orithm>usingnamespace std;/ 类静态变量定义intState :n = 0;intBoat :c = 0;/*=Methods for class "Boat"=*/Boat :Boat(intpastor ,intsavage )this ->pastor =this ->savage =pastor ;savage ;/*=Methods for class "State"=*/ 构造函数State :State(intpastor ,intsavage ,intboatAtSide)this ->i

9、Pastor =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);/

10、按照规则检查牧师得否安全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 +ret.pPrevious =returnret;boat .pastor, iSavage + this ;b

11、oat .savage, iBoatAtSide + 1);/ 重载 - 符号，表示船从此岸开走StateState :operator-(Boat & boat )Stateret(iPastor -ret.pPrevious =returnret;boat .pastor, iSavage - this ;boat .savage, iBoatAtSide - 1);/ 重载 =符号，比较两个节点是否是相同的状态boolState :operator=(State& state )return( this ->iPastor =state .iPastor &

12、&this ->iSavage =state .iSavage &&this->iBoatAtSide =state.iBoatAtSide);/*=Methods for class "RiverCrossing"=*/ 显示信息voidRiverCrossing:ShowInfo()cout<< "*" cout<< " 牧师与野人过河问题求解 cout<< " by 1040501211 陈嘉生 cout<< "*""

13、;"<<endl;<<endl;<<endl;<<endl;/ 构造函数RiverCrossing:RiverCrossing(intn,intc):endState(0, 0, 0)State :n =Boat :c =n;c ;/ 解决问题boolRiverCrossing:solve()openList.push_back(new State ( State :n,State :n, 1);while (!openList.empty() / 获取一个状态为当前状态State*nowState = openList.front()

14、;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) Boat b

15、oat(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) Boat boat(capticy - i, i);if(move(nowState, &boat)returntrue ;print(NULL);returnfalse

16、 ;/ 实施一步决策，将得到的新状态添加到列表，返回是否达到目标状态boolRiverCrossing:move( State* nowState ,Boat * boat )/ 获得下一个状态State*destState;if( nowState ->iBoatAtSide = 1) destState =new State (* nowState- *boat ); /船离开此岸elseif( nowState ->iBoatAtSide = 0) destState =new State (* nowState+ *boat ); /船开到此岸if(destState-&g

17、t;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);ret

18、urnfalse;deletedestState;returnfalse ;/ 检查给定状态是否存在于列表中State * RiverCrossing:findInList(list<State *> & listToCheck,State& state)for( list<State *>:iteratorite =listToCheck.begin(); ite !=listToCheck.end();+ite) if(*ite = returnstate *ite;)returnNULL;/ 根据达到的目标状态，回溯打印出求解过程voidRiver

19、Crossing:print(State * endState )cout<< "="<<endl; if (! endState ) cout<< "Search failed!"<<endl;else cout<< "Search successed!"<<endl;cout<< "Optimal Procedure: "<<endl;Statestackwhile*pState =endState ;<Sta

20、te *> st;/ 用栈将链表逆序，以便输出(pState) st.push(pState);pState = pState->pPrevious;intcount = 0;while(!st.empty() pState = st.top();st.pop();cout<<pState->iPastor<<"," <<pState->iSavage<<"," <<pState->iBoatAtSide;if(st.size() > 0)cout<&l

21、t; " -> "if(+count % 5 = 0)cout<<endl;/ 每五个步骤换行cout<<endl;cout<< "Total move: "<<count - 1<<endl;cout<< "="<<endl;七、实验结果实验二：九宫重排一、实验目的A* 算法是人工智能领域最重要的启发式搜索算法之一，本实验通过九宫重排问题，强化学生对 A* 算法的理解与应用，为人工智能后续环节的课程奠定基础。二、问题描述给定九宫格的初始状态，

22、要求在有限步的操作内， 使其转化为目标状态， 且所得到的解是代价最小解 (即移动的步数最少 )。如：三、基本要求输入：九宫格的初始状态和目标状态输出：重排的过程，即途径的状态四、实验组织运行要求本实验采用集中授课形式，每个同学独立完成上述实验要求。五、实验条件每人一台计算机独立完成实验。六、实验代码Main.cpp#include<iostream>#include"NineGrid.h"usingnamespace std;/ 主函数voidmain()NineGrid:ShowInfo();stringstart, end;cout<< &quo

23、t;Please input the initial state: (ex:134706582)"<<endl;cin>>start;cout<< "Please input the target state: (ex:123804765)"<<endl;cin>>end;NineGridnineGrid(start, end);nineGrid.solve();system("pause");NineGrid.h#pragmaonce#include<vector>#in

24、clude<string>#include<time.h>usingnamespace std;#define#defineSPACE '0'AT(s, x, y) (s)(x) * 3 + (y)enum Move UP = 0,DOWN= 1,LEFT = 2,RIGHT = 3;/ 九宫格状态classStatepublic:staticState*pEndState;/ 指向目标状态，用于评价h的值string grid; / 用字符串保存当前棋盘状态intx, y;/ 空格所在位置intmoves;/ 到此状态的移动次数intvalue;/ 价

25、值State*pPrevious;/ 前一个状态State(string&grid,State*pPrevious =NULL);intgetReversedCount();/ 获取逆序数voidevaluate();/ 评价函数boolcheck(Move move);/ 检查是否可以移动StatetakeMove(Move move);/ 实施移动，生成子状态/ 重载 =运算符，判断两个状态是否相等inlinebooloperator = (State& state) returngrid =state.grid; ;/ 九宫重排问题classNineGridprivate

26、:vector<State*> openList, closeList;StatestartState, endState;clock_tstartTime;boolboolStatecompareReversed();/ 比较逆序数奇偶性是否相同takeMove(State*nowState,Move move);/ 进行一次决策* findInList(vector< State*> &listToCheck,State&State);/ 检查某状态节点是否在列表中voidprint(State*endState);/打印结果/ 用于排序static

27、boolgreater_than(public:staticvoidShowInfo();constState/ 显示信息*state1,constState*state2);NineGrid(string&start,string&dest);boolsolve();/求解问题;NineGrid.cpp#include"NineGrid.h"#include<iostream>#include<stack>#include<algorithm>usingnamespace std;State*State:pEndStat

28、e =NULL;/*=Methods for class "State"=*/ 构造函数State:State(string& grid,State* pPrevious)this->grid =grid;this->pPrevious =pPrevious;if( this->pPrevious)this->moves =pPrevious->moves + 1;elsethis->moves = 0;this->value = 0;evaluate();for( inti = 0; i < 3; +i) for (

29、 intj = 0; j < 3; +j) if( AT( grid, i, j) =x = i;y = j;return;SPACE) boolState:check(Move move)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;

30、StateState:takeMove(Move move)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, destY) =AT(tGr

31、id, x, y) = t;returnState(tGrid,this);AT(tGrid, x, y);voidState:evaluate()if(!pEndState)return;intg = moves, h = 0;for( inti = 0; i < 3; +i) for( intj = 0; j < 3; +j) /if (AT(grid, i, j) != AT(pEndState->grid, i, j)/+h;if( AT(grid, i, j) =continue;SPACE)for( intii = 0; ii < 3; +ii) for(

32、intjj = 0; jj < 3; +jj) if( AT(grid, i, j) =h += abs(i - ii) + abs(j - jj);AT(pEndState->grid, ii, jj) this->value = g + h;/ 求该状态的逆序数/ 逆序数定义为：/ 不计空格，将棋盘按顺序排列，/对于 gridi，存在 j<i，使 gridj>gridi，即为逆序。/ 所有棋子的逆序总数为逆序数。intState:getReversedCount()intcount = 0;for( inti = 0; i < 9; +i) if (gr

33、idi =SPACE)continue;for( intj = 0; j < i; +j) if(gridj =SPACE)continue;if(gridi > gridj)+count;returncount;/*=Methods for class "NineGrid"=*/ 显示信息 void NineGrid :ShowInfo()cout<< "*"cout<< "九宫重排问题求解cout<< "by 1040501211陈嘉生cout<< "*&quo

34、t;""<<endl;<<endl;<<endl;<<endl;/ 构造函数NineGrid:NineGrid(: startState(string & start start ), endState(, string dest )& dest )State:pEndState = &endState;endState.evaluate();/ 当初始状态和目标状态的逆序数的奇偶性相同时，问题才有解boolNineGrid:compareReversed()returnstartState.getRe

35、versedCount() % 2 = endState.getReversedCount() %2;/ 解决问题boolNineGrid:solve()cout<< "="if(!compareReversed() cout<< " 初始状态和目标状态的逆序数的奇偶性不同，问题无解！elsecout<< "Start searching."<<endl;startTime = clock();/ 取得开始搜索的时间<<endl;" <<endl;openList

36、.push_back(new State(startState);while(!openList.empty() / 获取一个状态为当前状态State*nowState = openList.back();openList.pop_back();closeList.push_back(nowState);/ 从当前状态开始决策for( inti = 0; i < 4; +i) Move move = (Move)i;if(nowState->check(move) if(takeMove(nowState, move)returntrue;print(NULL);returnfal

37、se;/ 实施一步决策，将得到的新状态添加到列表，返回是否达到目标状态boolNineGrid:takeMove(State* nowState,Move move)/ 获得下一个状态State*destState =new State( nowState->takeMove(move);if(*destState = endState) closeList.push_back(destState);/ 是否达到目标状态print(destState);returntrue; / 找到结果elseif(!findInList(openList, *destState) &&

38、; !findInList(closeList,*destState) / 添加没出现过的状态节点到open 表openList.push_back(destState);sort(openList.begin(), openList.end(), greater_than);returnfalse;deletereturndestState;false;/ 检查给定状态是否存在于列表中State*NineGrid:findInList(vector<State*> & listToCheck,State& state)for( vector<State*&g

39、t;:iteratorite =listToCheck.begin(); ite !=listToCheck.end(); +ite) if(*ite =state)return*ite;returnNULL;/ 根据达到的目标状态，回溯打印出求解过程voidNineGrid:print(State* endState)if(!endState) cout<< "Search failed!"elsefloatelapsed= ( float<<endl;)clock()- startTime)/CLOCKS_PER_SEC* 1000; /取得搜索

40、花费时间cout<< "Search successed!"<<endl;cout<< "Elapsed time: "<<elapsed<<"(ms)"<<endl;cout<< "Total move: "<<endState->moves<<endl;cout<< "Optimal Procedure: "<<endl;State*pState =end

41、State;stack<State*> st;/ 用栈将链表逆序，以便输出while(pState) st.push(pState);pState = pState->pPrevious;/3 行一起输出，更直观一点stringout3;intcount = 0;while(!st.empty() pState = st.top();st.pop();for( inti = 0; i < 3; +i) for ( intj = 0; j < 3; +j) if( AT(pState->grid, i, j) =outi +=' 'SPACE)

42、elseouti +=AT(pState->grid, i, j);outi +=' 'if(st.size() != 0) out0 +=out1 +=out2 +="""-> """if(+count % 5 = 0 | st.size() = 0) for( inti = 0; i < 3; +i) cout<<outi<<endl;outi ="" ;cout<<endl;cout<< "="<<

43、;endl;/ 定义的排列函数boolNineGrid:greater_than(constState* state1,constState* state2)returnstate1->value >state2->value;七、实验结果实验三：专家系统一、实验目的专家系统是人工智能的重要研究内容和组成部分之一， 本实验通过设计一个简单的专家系统， 加深学生对专家系统的组成结构和构造原理的理解， 并能转化为具体的应用。二问题描述设计一个简单的专家系统，可根据属性的输入值自动识别事物的具体类别，内容自拟。如一个动物专家系统可由以下 11 个属性组成，根据属性的对应值 (Y 或 N) ，可判断动物的具