人工智能-实验报告.doc

实验一：知识表示方法
一、实验目的
状态空间表示法是人工智能领域最基本的知识表示方法之一，也是进一步学习状态空间搜索策略的基础，本实验通过牧师与野人渡河的问题，强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定基础。
二、问题描述
有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表示目的岸)。
要求：写出算法的设计思想和源程序，并以图形用户界面实现人机交互，进行输入和输出结果，如：
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;
}