实验一：知识表示方法
一、实验目的
状态空间表示法是人工智能领域最基本的知识表示方法之一，也是进一步学习状态空间搜索策略的基础，本实验通过牧师与野人渡河的问题，强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定基础。
二、问题描述
有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。
三、基本要求
输入：牧师人数(即野人人数)：n；小船一次最多载人量：c。
输出：若问题无解，则显示Failed，否则，显示Successed输出一组最佳
方案。
用三元组(X
1, X
2
, X
3
)表示渡河过程中的状态。
并用箭头连接相邻状态以
表示迁移过程：初始状态->中间状态->目标状态。
例：当输入n=2，c=2时，输出：221->110->211->010->021->000
其中：X
1表示起始岸上的牧师人数；X
2
表示起始岸上的野人人数；X
3
表示小船现
在位置(1表示起始岸，0表示目的岸)。
要求：写出算法的设计思想和源程序，并以图形用户界面实现人机交互，进行输入和输出结果，如：
Please input n: 2 Please input c: 2
Successed or Failed?: Successed
Optimal 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<<"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 Boat
{
public:
static int c;
int pastor;//牧师
int savage;//野人
Boat(int pastor, int savage);
};
//河岸状态
class State
{
public:
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 - (Boat &boat);
bool operator == (State &state);
};
//过河问题
class RiverCrossing
{
private:
std::list<State*> openList, closeList;
State endState;
bool move(State *nowState, Boat *boat);//进行一次决策
State* findInList(std::list<State*> &listToCheck, State &state);//检查某状态节点是否在列表中
void print(State *endState);//打印结果
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 "Boat"=========================*/ 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;
}
//获取此岸总人数
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)
//将上述条件联立后得到如下条件
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.pastor, 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 "RiverCrossing"=======================*/ //显示信息
void RiverCrossing::ShowInfo()
{
cout<<"************************************************"<<endl;
cout<<" 牧师与野人过河问题求解 "<<endl;
cout<<" by 1040501211 陈嘉生 "<<endl;
cout<<"************************************************"<<endl;
}
//构造函数
RiverCrossing::RiverCrossing(int n, int c)
:endState(0, 0, 0)
{
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 = 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 (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->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 (destState->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 &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!"<<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();
st.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 - 1<<endl;
}
cout<<"================================================"<<endl;
}
七、实验结果
实验二：九宫重排
一、实验目的
A*算法是人工智能领域最重要的启发式搜索算法之一，本实验通过九宫重排问题，强化学生对A*算法的理解与应用，为人工智能后续环节的课程奠定基础。
二、问题描述
给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)。
如：
三、基本要求
输入：九宫格的初始状态和目标状态
输出：重排的过程，即途径的状态
四、实验组织运行要求
本实验采用集中授课形式，每个同学独立完成上述实验要求。
五、实验条件
每人一台计算机独立完成实验。
六、实验代码
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:123804765)"<<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 = 0, DOWN = 1, LEFT = 2, RIGHT = 3
};
//九宫格状态
class State
{
public:
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 check(Move move);//检查是否可以移动
State takeMove(Move move);//实施移动，生成子状态
//重载==运算符，判断两个状态是否相等
inline bool operator == (State &state) { return grid == state.grid; }
};
//九宫重排问题
class NineGrid
{
private:
vector<State*> openList, closeList;
State startState, endState;
clock_t startTime;
bool compareReversed();//比较逆序数奇偶性是否相同
bool 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 &start, 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)
{
this->grid = grid;
this->pPrevious = pPrevious;
if (this->pPrevious)
this->moves = pPrevious->moves + 1;
else
this->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 move)
{
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;
destY = 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 (!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, ii, jj)) {
h += abs(i - ii) + abs(j - jj);
}
}
}
}
}
this->value = g + h;
}
//求该状态的逆序数
//逆序数定义为：
// 不计空格，将棋盘按顺序排列，
// 对于grid[i]，存在j<i，使grid[j]>grid[i]，即为逆序。
// 所有棋子的逆序总数为逆序数。
int State::getReversedCount()
{
int count = 0;
for (int i = 0; i < 9; ++i) {
if(grid[i] == SPACE)
continue;
for (int j = 0; j < i; ++j) {
if (grid[j] == SPACE)
continue;
if (grid[i] > grid[j])
++count;
}
}
return count;
}
/*=====================Methods for class "NineGrid"=====================*/ //显示信息
void NineGrid::ShowInfo()
{
cout<<"************************************************"<<endl;
cout<<" 九宫重排问题求解 "<<endl;
cout<<" by 1040501211 陈嘉生 "<<endl;
cout<<"************************************************"<<endl;
}
//构造函数
NineGrid::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()
{
cout<<"================================================"<<endl;
if (!compareReversed()) {
cout<<"初始状态和目标状态的逆序数的奇偶性不同，问题无解！"<<endl;
} else {
cout<<"Start searching..."<<endl;
startTime = clock();//取得开始搜索的时间
openList.push_back(new State(startState));
while(!openList.empty()) {
//获取一个状态为当前状态
State *nowState = 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, Move 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(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) {
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;
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.push(pState);
pState = pState->pPrevious;
}
//3行一起输出，更直观一点
string out[3];
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)
out[i] += ' ';
else
out[i] += AT(pState->grid, i, j);
out[i] += ' ';
}
}
if (st.size() != 0) {
out[0] += " ";
out[1] += "-> ";
out[2] += " ";
}
if (++count % 5 == 0 || st.size() == 0) {
for (int i = 0; i < 3; ++i) {
cout<<out[i]<<endl;
out[i] = "";
}
cout<<endl;
}
}
}
cout<<"================================================"<<endl; }
//定义的排列函数
bool NineGrid::greater_than(const State *state1, const State *state2)
{
return state1->value > state2->value; }
七、实验结果
实验三：专家系统
一、实验目的
专家系统是人工智能的重要研究内容和组成部分之一，本实验通过设计一个简单的专家系统，加深学生对专家系统的组成结构和构造原理的理解，并能转化为具体的应用。
二﹑问题描述
设计一个简单的专家系统，可根据属性的输入值自动识别事物的具体类别，内容自拟。
如一个动物专家系统可由以下11个属性组成，根据属性的对应值(Y或N)，可判断动物的具体种类，运行结果如下图所示：
三、实验组织运行要求
本实验采用开放授课形式，每个同学独立完成上述实验要求。
四、实验条件
每人一台计算机独立完成实验。
五、实验代码
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
#pragma once
#include<string>
#include<vector>
using namespace std;
//疾病信息定义
typedef struct
{
string name;
vector<string> symptomList;
} Disease;
//疾病诊断专家系统
class Expert
{
protected:
vector<Disease> m_DiseaseList;//疾病列表
bool readFile();//读取文件
bool optionSelect(const string &question);//提示用户选择
public:
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<fstream>
using namespace std;
//显示信息
void Expert::ShowInfo()
{
cout<<"************************************************"<<endl;
cout<<" 疾病诊断专家系统 "<<endl;
cout<<" by 1040501211 陈嘉生 "<<endl;
cout<<"************************************************"<<endl; }
//初始化疾病列表，返回是否初始化成功
bool Expert::initDiseaseList()
{
__try {
return readFile();
}
__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;
}
Disease *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 {
//其余的是症状名称
addSymptom(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)
{
disease->symptomList.push_back(symptom);
}
//诊断函数
void Expert::diagnosis()
{
//用户输入的第一个症状
string symptomInput;
//用户有的症状和没有的症状
vector<string> symptomHave, symptomNotHave;
//搜索的结果列表
vector<Disease*> findList;
cout<<"【症状询问】"<<endl;
cout<<endl<<"->请输入症状: （或\"不确定\"以开始模糊搜索）"<<endl;
cin>>symptomInput;
if (symptomInput == "不确定") {
//添加所有疾病到findList列表中
for (unsigned int i = 0; i < m_DiseaseList.size(); ++i) {
findList.push_back(&m_DiseaseList[i]);
}
} else {
//添加有此症状的疾病到findList列表中
for (unsigned int i = 0; i < m_DiseaseList.size(); ++i) {
Disease *pDisease = &m_DiseaseList[i];
for (unsigned int j = 0; j < pDisease->symptomList.size(); ++j) {
if (symptomInput == pDisease->symptomList[j]) {
findList.push_back(pDisease);
}
}
}
//添加输入的症状到symptomHave列表中
symptomHave.push_back(symptomInput);
}
for (vector<Disease*>::iterator ite = findList.begin(); ite != findList.end();) {
bool remove = false;//是否从findList列表中排除本疾病
for (unsigned int j = 0; j < (*ite)->symptomList.size(); ++j) {
Disease *pDisease = *ite;
if (find(symptomNotHave.begin(), symptomNotHave.end(),
pDisease->symptomList[j]) != symptomNotHave.end()) {
//在symptomNotHave列表中找到此症状，直接排除
remove = true;
break;
} else if (find(symptomHave.begin(), symptomHave.end(),
pDisease->symptomList[j]) == symptomHave.end()) {
//在symptomHave，symptomNotHave列表中不存在这个症状，则询问
if (optionSelect("->是否有症状\"" + pDisease->symptomList[j] + "\"?\n(y/n): ")) {
//询问得知有此症状，添加症状到symptomHave列表中
symptomHave.push_back(pDisease->symptomList[j]);
} else {
//询问得知没有此症状，添加症状到symptomNotHave列表中，并排除此疾病
symptomNotHave.push_back(pDisease->symptomList[j]);
remove = true;
break;
}
}
}
if (remove) {
//需要排除此疾病
ite = findList.erase(ite);
} else {
//迭代器后移
++ite;
}
}
cout<<endl<<"【疾病诊断】"<<endl;
if (findList.size() == 0) {
cout<<endl<<"->知识库中未找到匹配的记录！"<<endl;
} else {
cout<<endl<<"->根据已有的知识库，可能的疾病为："<<endl;
//输出结果列表
for (unsigned int i = 0; i < findList.size(); ++i) { cout<<findList[i]->name;
if (i != findList.size() - 1)
cout<<", ";
if ((i+1) % 5 == 0)
cout<<endl;//5个换行
}
cout<<endl;
}
cout<<endl<<"【诊断结束】"<<endl<<endl;
}
//提示用户选择Y或N
bool Expert::optionSelect(const string &question)
{
cout<<endl<<question;
char option;
cin>>option;
switch (option) {
case'Y':
case'y':
return true;
case'N':
case'n':
return false;
}
return false;
}
Disease.txt [疾病1]
症状A
症状B
症状C
症状D
[疾病2]
症状A
症状B
症状C
[疾病3]
症状A
症状B
症状D
症状E
[疾病4]
症状A
症状C
症状D
[疾病5]
症状B
症状C
症状D
症状E
[疾病6]
症状A
症状B
[疾病7]
症状A
症状C
症状E
[疾病8]
症状A
症状D
[疾病9]
症状B
症状C
症状E
[疾病10]
症状B
症状D
[疾病11]
症状C
症状D
症状E 六、实验结果。
