人工智能-实验报告

1、 实验一：知识表示方法一、实验目的状态空间表示法是人工智能领域最根本的知识表示方法之一，也是进一步学习状态空间搜索策略的根底，本实验通过牧师与野人渡河的问题，强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定根底。二、问题描述有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，假设能，那么给出小船来回次数最少的最正确方案。三、根本要求输入：牧师人数(即野人人数)：n；小船一次最多载人量：c。输出：假设问题无解，那么显示Fail

2、ed，否那么，显示Successed输出一组最正确方案。用三元组(X1, X2, X3)表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程：初始状态->中间状态->目标状态。例：当输入n=2，c=2时，输出：221->110->211->010->021->000其中：X1表示起始岸上的牧师人数；X2表示起始岸上的野人人数；X3表示小船现在位置(1表示起始岸，0表示目的岸)。要求：写出算法的设计思想和源程序，并以图形用户界面实现人机交互，进行输入和输出结果，如：Please input n: 2 Please input c: 2Successe

3、d or Failed?: SuccessedOptimal Procedure: 221->110->211->010->021->000四、实验组织运行要求本实验采用集中授课形式，每个同学独立完成上述实验要求。五、实验条件每人一台计算机独立完成实验。六、实验代码Main.cpp#include <iostream>#include "RiverCrossing.h"using namespace std;/主函数void main()RiverCrossing:ShowInfo();int n, c;cout<<&q

4、uot;Please input n: "cin>>n;cout<<"Please input c: "cin>>c;RiverCrossing riverCrossing(n, c);riverCrossing.solve();system("pause");RiverCrossing.h#pragma once#include <list>/船class Boatpublic:static int c;int pastor;/牧师int savage;/野人Boat(int pastor, i

5、nt savage);/河岸状态class Statepublic:static int n;int iPastor;/牧师数量int iSavage;/野人数量int iBoatAtSide;/船所在河岸State *pPrevious;/前一个状态State(int pastor, int savage, int boatAtSide);int getTotalCount();/获得此岸总人数bool check();/检查人数是否符合实际bool isSafe();/检查是否平安State operator + (Boat &boat);State operator - (Boa

6、t &boat);bool operator = (State &state);/过河问题class RiverCrossingprivate:std:list<State*> openList, closeList;State endState;bool move(State *nowState, Boat *boat);/进行一次决策State* findInList(std:list<State*> &listToCheck, State &state);/检查某状态节点是否在列表中void print(State *endStat

7、e);/打印结果public:static void ShowInfo();RiverCrossing(int n, int c);bool solve();/求解问题;RiverCrossing.cpp#include "RiverCrossing.h"#include <iostream>#include <stack>#include <algorithm>using namespace std;/类静态变量定义int State:n = 0;int Boat:c = 0;/*=Methods for class "Boa

8、t"=*/Boat:Boat(int pastor, int savage)this->pastor = pastor;this->savage = savage;/*=Methods for class "State"=*/构造函数State:State(int pastor, int savage, int boatAtSide)this->iPastor = pastor;this->iSavage = savage;this->iBoatAtSide = boatAtSide;this->pPrevious = NULL

9、;/获取此岸总人数int State:getTotalCount()return iPastor + iSavage;/检查人数是否在0到n之间bool State:check()return (iPastor >=0 && iPastor <= n && iSavage >= 0 && iSavage <=n);/按照规那么检查牧师得否平安bool State:isSafe()/此岸的平安：x1 = 0 | x1 >= x2/此岸的平安：(n-x1) = 0 | (n-x1) >= (n-x2)/将上述条件联

10、立后得到如下条件return (iPastor = 0 | iPastor = n | iPastor = iSavage);/重载+符号，表示船开到此岸State State:operator+(Boat &boat)State ret(iPastor + boat.pastor, iSavage + boat.savage, iBoatAtSide + 1);ret.pPrevious = this;return ret;/重载-符号，表示船从此岸开走State State:operator-(Boat &boat)State ret(iPastor - boat.past

11、or, iSavage - boat.savage, iBoatAtSide - 1);ret.pPrevious = this;return ret;/重载=符号，比拟两个节点是否是相同的状态bool State:operator=(State &state)return (this->iPastor = state.iPastor && this->iSavage = state.iSavage && this->iBoatAtSide = state.iBoatAtSide);/*=Methods for class "

12、RiverCrossing"=*/显示信息void RiverCrossing:ShowInfo()cout<<"*"<<endl;cout<<" 牧师与野人过河问题求解 "<<endl;cout<<" by 1040501211 陈嘉生 "<<endl;cout<<"*"<<endl;/构造函数RiverCrossing:RiverCrossing(int n, int c):endState(0, 0, 0

13、)State:n = n;Boat:c = c;/解决问题bool RiverCrossing:solve()openList.push_back(new State(State:n, State:n, 1);while(!openList.empty() /获取一个状态为当前状态State *nowState = openList.front();openList.pop_front();closeList.push_back(nowState);/从当前状态开始决策if (nowState->iBoatAtSide = 1) /船在此岸/过河的人越多越好，且野人优先int count

14、 = nowState->getTotalCount();count = (Boat:c >= count ? count : Boat:c);for (int capticy = count; capticy >= 1; -capticy) for (int i = 0; i <= capticy; +i) Boat boat(i, capticy - i);if (move(nowState, &boat)return true; else if (nowState->iBoatAtSide = 0) /船在此岸/把船开回来的人要最少，且牧师优先for

15、 (int capticy = 1; capticy <= Boat:c; +capticy) for (int i = 0; i <= capticy; +i) Boat boat(capticy - i, i);if (move(nowState, &boat)return true;print(NULL);return false;/实施一步决策，将得到的新状态添加到列表，返回是否到达目标状态bool RiverCrossing:move(State *nowState, Boat *boat)/获得下一个状态State *destState;if (nowState

16、->iBoatAtSide = 1) destState = new State(*nowState - *boat);/船离开此岸 else if (nowState->iBoatAtSide = 0) destState = new State(*nowState + *boat);/船开到此岸if (destState->check() /检查人数if (*destState = endState) /是否到达目标状态closeList.push_back(destState);print(destState);return true;/找到结果 else if (de

17、stState->isSafe() /检查是否平安if (!findInList(openList, *destState) && !findInList(closeList, *destState) /检查是否在表中/添加没出现过的状态节点到open表openList.push_back(destState);return false;delete destState;return false;/检查给定状态是否存在于列表中State* RiverCrossing:findInList(list<State*> &listToCheck, State

18、 &state)for (list<State*>:iterator ite = listToCheck.begin(); ite != listToCheck.end(); +ite) if (*ite = state)return *ite;return NULL;/根据到达的目标状态，回溯打印出求解过程void RiverCrossing:print(State *endState)cout<<"="<<endl;if (!endState) cout<<"Search failed!"<

19、;<endl; else cout<<"Search successed!"<<endl;cout<<"Optimal Procedure: "<<endl;State *pState = endState;stack<State*> st;/用栈将链表逆序，以便输出while (pState) st.push(pState);pState = pState->pPrevious;int count = 0;while (!st.empty() pState = st.top();s

20、t.pop();cout<<pState->iPastor<<","<<pState->iSavage<<","<<pState->iBoatAtSide;if (st.size() > 0)cout<<" -> "if (+count % 5 = 0)/每五个步骤换行cout<<endl;cout<<endl;cout<<"Total move: "<<count

21、- 1<<endl;cout<<"="<<endl;七、实验结果实验二：九宫重排一、实验目的A*算法是人工智能领域最重要的启发式搜索算法之一，本实验通过九宫重排问题，强化学生对A*算法的理解与应用，为人工智能后续环节的课程奠定根底。二、问题描述给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)。如：三、根本要求输入：九宫格的初始状态和目标状态输出：重排的过程，即途径的状态四、实验组织运行要求本实验采用集中授课形式，每个同学独立完成上述实验要求。五、实验条件每人一台计算机独立完成实验

22、。六、实验代码Main.cpp#include <iostream>#include "NineGrid.h"using namespace std;/主函数void main()NineGrid:ShowInfo();string start, end;cout<<"Please input the initial state: (ex:134706582)"<<endl;cin>>start;cout<<"Please input the target state: (ex:123

23、804765)"<<endl;cin>>end;NineGrid nineGrid(start, end);nineGrid.solve();system("pause");NineGrid.h#pragma once#include <vector>#include <string>#include <time.h>using namespace std;#define SPACE '0'#define AT(s, x, y) (s)(x) * 3 + (y)enum Move UP =

24、 0, DOWN = 1, LEFT = 2, RIGHT = 3;/九宫格状态class Statepublic:static State *pEndState;/指向目标状态，用于评价h的值string grid;/用字符串保存当前棋盘状态int x, y;/空格所在位置int moves;/到此状态的移动次数int value;/价值State *pPrevious;/前一个状态State(string &grid, State *pPrevious = NULL);int getReversedCount();/获取逆序数void evaluate();/评价函数bool ch

25、eck(Move move);/检查是否可以移动State takeMove(Move move);/实施移动，生成子状态/重载=运算符，判断两个状态是否相等inline bool operator = (State &state) return grid = state.grid; ;/九宫重排问题class NineGridprivate:vector<State*> openList, closeList;State startState, endState;clock_t startTime;bool compareReversed();/比拟逆序数奇偶性是否相同b

26、ool takeMove(State *nowState, Move move);/进行一次决策State* findInList(vector<State*> &listToCheck, State &State);/检查某状态节点是否在列表中void print(State *endState);/打印结果/用于排序static bool greater_than(const State *state1, const State *state2);public:static void ShowInfo();/显示信息NineGrid(string &st

27、art, string &dest);bool solve();/求解问题;NineGrid.cpp#include "NineGrid.h"#include <iostream>#include <stack>#include <algorithm>using namespace std;State* State:pEndState = NULL;/*=Methods for class "State"=*/构造函数State:State(string &grid, State *pPrevious)

28、this->grid = grid;this->pPrevious = pPrevious;if (this->pPrevious)this->moves = pPrevious->moves + 1;elsethis->moves = 0;this->value = 0;evaluate();for (int i = 0; i < 3; +i) for(int j = 0; j < 3; +j) if (AT(grid, i, j) = SPACE) x = i;y = j;return;bool State:check(Move mov

29、e)switch (move) case UP:if (x - 1 < 0)return false;break;case DOWN:if (x + 1 >= 3)return false;break;case LEFT:if (y - 1 < 0)return false;break;case RIGHT:if (y + 1 >= 3)return false;break;return true;State State:takeMove(Move move)int destX, destY;switch (move) case UP:destX = x - 1;des

30、tY = y;break;case DOWN:destX = x + 1;destY = y;break;case LEFT:destX = x;destY = y - 1;break;case RIGHT:destX = x;destY = y + 1;break;string tGrid = grid;char t = AT(tGrid, destX, destY);AT(tGrid, destX, destY) = AT(tGrid, x, y);AT(tGrid, x, y) = t;return State(tGrid, this);void State:evaluate()if (

31、!pEndState)return;int g = moves, h = 0;for (int i = 0; i < 3; +i) for (int j = 0; j < 3; +j) /if (AT(grid, i, j) != AT(pEndState->grid, i, j)/+h;if(AT(grid, i, j) = SPACE)continue;for (int ii = 0; ii < 3; +ii) for (int jj = 0; jj < 3; +jj) if (AT(grid, i, j) = AT(pEndState->grid, i

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

33、e;if (gridi > gridj)+count;return count;/*=Methods for class "NineGrid"=*/显示信息void NineGrid:ShowInfo()cout<<"*"<<endl;cout<<" 九宫重排问题求解 "<<endl;cout<<" by 1040501211 陈嘉生 "<<endl;cout<<"*"<<endl;/构造函数N

34、ineGrid:NineGrid(string &start, string &dest): startState(start), endState(dest)State:pEndState = &endState;endState.evaluate();/当初始状态和目标状态的逆序数的奇偶性相同时，问题才有解bool NineGrid:compareReversed()return startState.getReversedCount() % 2 = endState.getReversedCount() % 2;/解决问题bool NineGrid:solve()

35、cout<<"="<<endl;if (!compareReversed() cout<<"初始状态和目标状态的逆序数的奇偶性不同，问题无解！"<<endl; else cout<<"Start searching."<<endl;startTime = clock();/取得开始搜索的时间openList.push_back(new State(startState);while(!openList.empty() /获取一个状态为当前状态State *nowS

36、tate = openList.back();openList.pop_back();closeList.push_back(nowState);/从当前状态开始决策for (int i = 0; i < 4; +i) Move move = (Move)i;if (nowState->check(move) if (takeMove(nowState, move)return true;print(NULL);return false;/实施一步决策，将得到的新状态添加到列表，返回是否到达目标状态bool NineGrid:takeMove(State *nowState, Mo

37、ve move)/获得下一个状态State *destState = new State(nowState->takeMove(move);if (*destState = endState) /是否到达目标状态closeList.push_back(destState);print(destState);return true;/找到结果 else if (!findInList(openList, *destState) && !findInList(closeList, *destState) /添加没出现过的状态节点到open表openList.push_back

38、(destState);sort(openList.begin(), openList.end(), greater_than);return false;delete destState;return false;/检查给定状态是否存在于列表中State* NineGrid:findInList(vector<State*> &listToCheck, State &state)for (vector<State*>:iterator ite = listToCheck.begin(); ite != listToCheck.end(); +ite)

39、if (*ite = state)return *ite;return NULL;/根据到达的目标状态，回溯打印出求解过程void NineGrid:print(State *endState)if (!endState) cout<<"Search failed!"<<endl; else float elapsed = (float)clock() - startTime) / CLOCKS_PER_SEC * 1000;/取得搜索花费时间cout<<"Search successed!"<<endl;

40、cout<<"Elapsed time: "<<elapsed<<"(ms)"<<endl;cout<<"Total move: "<<endState->moves<<endl;cout<<"Optimal Procedure: "<<endl;State *pState = endState;stack<State*> st;/用栈将链表逆序，以便输出while (pState) st.

41、push(pState);pState = pState->pPrevious;/3行一起输出，更直观一点string out3;int count = 0;while (!st.empty() pState = st.top();st.pop();for (int i = 0; i < 3; +i) for(int j = 0; j < 3; +j) if (AT(pState->grid, i, j) = SPACE)outi += ' 'elseouti += AT(pState->grid, i, j);outi += ' '

42、;if (st.size() != 0) out0 += " "out1 += "-> "out2 += " "if (+count % 5 = 0 | st.size() = 0) for (int i = 0; i < 3; +i) cout<<outi<<endl;outi = ""cout<<endl;cout<<"="<<endl;/定义的排列函数bool NineGrid:greater_than(const S

43、tate *state1, const State *state2)return state1->value > state2->value;七、实验结果实验三：专家系统一、实验目的专家系统是人工智能的重要研究内容和组成局部之一，本实验通过设计一个简单的专家系统，加深学生对专家系统的组成结构和构造原理的理解，并能转化为具体的应用。二问题描述设计一个简单的专家系统，可根据属性的输入值自动识别事物的具体类别，内容自拟。如一个动物专家系统可由以下11个属性组成，根据属性的对应值(Y或N)，可判断动物的具体种类，运行结果如下列图所示：三、实验组织运行要求本实验采用开放授课形式，每个同

44、学独立完成上述实验要求。四、实验条件每人一台计算机独立完成实验。五、实验代码Main.cpp#include "Expert.h"#include <iostream>using namespace std;void main()Expert:ShowInfo();Expert expert;if (expert.initDiseaseList() expert.diagnosis(); else cout<<"初始化失败！"<<endl;system("pause");Expert.h#pragm

45、a once#include <string>#include <vector>using namespace std;/疾病信息定义typedef structstring name;vector<string> symptomList; Disease;/疾病诊断专家系统class Expertprotected:vector<Disease> m_DiseaseList;/疾病列表bool readFile();/读取文件bool optionSelect(const string &question);/提示用户选择public:

46、static void ShowInfo();/显示信息bool initDiseaseList();/初始化疾病列表Disease* addDisease(const string &name);/添加疾病void addSymptom(Disease *disease, const string &symptom);/添加疾病的病症void diagnosis();/诊断;Expert.cpp#include "Expert.h"#include <iostream>#include <algorithm>#include <

47、;fstream>using namespace std;/显示信息void Expert:ShowInfo()cout<<"*"<<endl;cout<<" 疾病诊断专家系统 "<<endl;cout<<" by 1040501211 陈嘉生 "<<endl;cout<<"*"<<endl;/初始化疾病列表，返回是否初始化成功bool Expert:initDiseaseList()_try return rea

48、dFile();_except(true) cout<<"知识库文件(Disease.txt)解析错误！"<<endl;return false;/读取Disease.txt文件，获取疾病信息bool Expert:readFile()fstream ioFile;ioFile.open("Disease.txt", fstream:in);if (!ioFile.is_open() cout<<"无法翻开知识库文件(Disease.txt)！"<<endl;return false;D

49、isease *pDisease = NULL;while (!ioFile.eof() string strInput;ioFile>>strInput;if (strInput.size() = 0)continue;if (strInput.front() = '' && strInput.back() = '') /有包裹的是疾病名称strInput = strInput.substr(1,strInput.size() - 2);pDisease = addDisease(strInput); else /其余的是病症名称a

50、ddSymptom(pDisease, strInput);ioFile.close();return true;/添加一个疾病，返回此疾病信息的指针Disease* Expert:addDisease(const string &name)Disease disease; = name;m_DiseaseList.push_back(disease);return &m_DiseaseList.back();/添加疾病的病症void Expert:addSymptom(Disease *disease,const string &symptom

51、)disease->symptomList.push_back(symptom);/诊断函数void Expert:diagnosis()/用户输入的第一个病症string symptomInput;/用户有的病症和没有的病症vector<string> symptomHave, symptomNotHave;/搜索的结果列表vector<Disease*> findList;cout<<"【病症询问】"<<endl;cout<<endl<<"->请输入病症: 或"不确定

52、"以开始模糊搜索"<<endl;cin>>symptomInput;if (symptomInput = "不确定") /添加所有疾病到findList列表中for (unsigned int i = 0; i < m_DiseaseList.size(); +i) findList.push_back(&m_DiseaseListi); else /添加有此病症的疾病到findList列表中for (unsigned int i = 0; i < m_DiseaseList.size(); +i) Disease *pDisease = &m_DiseaseListi;for (unsigned int j = 0; j < pDisease->symptomList.size(); +j) if (symptomInput = pDisease->symptomListj) findList.push_back(pDisease);/添加输入的病症到symptomHave列表中symptomHave.push_back(symptomInput);for (vector&l