实验一：知识表示方法
一、实验目的
状态空间表示法是人工智能领域最基本的知识表示方法之一，也是进一步学习状态空间搜索策略的基础，本实验通过牧师与野人渡河的问题，强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定基础。
二、问题描述
有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。
三、基本要求
输入：牧师人数(即野人人数)：n；小船一次最多载人量：c。
输出：若问题无解，则显示Failed，否则，显示Succeed输出一组最佳方案。用三元组(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 Succeed or Failed?: Succeed Optimal Procedure: 221->110->211->010->021->000
四、实验组织运行要求
本实验采用集中授课形式，每个同学独立完成上述实验要求。
五、实验条件
每人一台计算机独立完成实验。
六、实验代码
Main.cpp #include #include \"RiverCroing.h\" using namespace std;
//主函数 void main() {
} system(\"pause\"); RiverCroing riverCroing(n, c); riverCroing.solve(); int n, c; cout>n; cout>c; RiverCroing::ShowInfo();
RiverCroing.h #pragma once #include
//船 cla Boat { public:
};
//河岸状态 cla State Boat(int pastor, int savage); static int c; int pastor;//牧师 int savage;//野人
{ public:
};
//过河问题
cla RiverCroing { private:
}; bool move(State *nowState, Boat *boat);//进行一次决策
State* findInList(std::list &listToCheck, State &state);//检查某状态节void print(State *endState);//打印结果 static void ShowInfo(); RiverCroing(int n, int c); bool solve();//求解问题 std::list openList, closeList; State endState; State(int pastor, int savage, int boatAtSide); int getTotalCount();//获得此岸总人数 bool check();//检查人数是否符合实际 bool isSafe();//检查是否安全
State operator + (Boat &boat); State operatorboat.pastor, iSavage1); ret.pPrevious = this; return ret; State ret(iPastor + boat.pastor, iSavage + boat.savage, iBoatAtSide + 1); ret.pPrevious = this; return ret;
} openList.push_back(new State(State::n, State::n, 1)); while(!openList.empty()) {
} print(NULL); return false; //获取一个状态为当前状态
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 capticy = 1; capticy
} for (int i = 0; i
} Boat boat(capticyi); if (move(nowState, &boat))
return true; } else if (nowState->iBoatAtSide == 0) {//船在彼岸
//实施一步决策，将得到的新状态添加到列表，返回是否达到目标状态 bool RiverCroing::move(State *nowState, Boat *boat) {
//获得下一个状态 State *destState; if (nowState->iBoatAtSide == 1) {
} destState = new State(*nowState1iPastoriSavageiBoatAtSide; if (st.size() > 0) cout \"; cout
cout
七、实验结果
实验二：九宫重排
一、实验目的
A*算法是人工智能领域最重要的启发式搜索算法之一，本实验通过九宫重排问题，强化学生对A*算法的理解与应用，为人工智能后续环节的课程奠定基础。
二、问题描述
给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)。如：
三、基本要求
输入：九宫格的初始状态和目标状态 输出：重排的过程，即途径的状态
四、实验组织运行要求
本实验采用集中授课形式，每个同学独立完成上述实验要求。
五、实验条件
每人一台计算机独立完成实验。
六、实验代码
Main.cpp #include #include \"NineGrid.h\" using namespace std;
//主函数 void main() { NineGrid::ShowInfo();
} string start, end; cout>start; cout>end; NineGrid nineGrid(start, end); nineGrid.solve(); system(\"pause\");
NineGrid.h #pragma once #include #include #include using namespace std;
#define SPACE \'0\'
#define AT(s, x, y) (s)[(x) * 3 + (y)]
enum Move { };
//九宫格状态 cla State { public:
int moves;//到此状态的移动次数 int value;//价值
State *pPrevious;//前一个状态
State(string &grid, State *pPrevious = NULL); int getReversedCount();//获取逆序数 void evaluate();//评价函数
bool check(Move move);//检查是否可以移动 string grid;//用字符串保存当前棋盘状态 int x, y;//空格所在位置 static State *pEndState;//指向目标状态，用于评价h的值 UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3
}; State takeMove(Move move);//实施移动，生成子状态 //重载==运算符，判断两个状态是否相等
inline bool operator == (State &state) { return grid == state.grid; } //九宫重排问题 cla NineGrid { private:
};
NineGrid.cpp #include \"NineGrid.h\" #include #include #include using namespace std;
State* State::pEndState = NULL;
/*=======================Methods for cla \"State\"=======================*/ //构造函数
State::State(string &grid, State *pPrevious) { this->grid = grid; NineGrid(string &start, string &dest); bool solve();//求解问题 //用于排序
static bool greater_than(const State *state1, const State *state2); static void ShowInfo();//显示信息 bool compareReversed();//比较逆序数奇偶性是否相同
bool takeMove(State *nowState, Move move);//进行一次决策
State* findInList(vector &listToCheck, State &State);//检查某状态void print(State *endState);//打印结果 vector openList, closeList; State startState, endState; clock_t startTime; 节点是否在列表中
public:
} this->pPrevious = pPrevious; if (this->pPrevious) this->moves = pPrevious->moves + 1; this->moves = 0; else
this->value = 0; evaluate(); for (int i = 0; i
} for(int j = 0; j
} if (AT(grid, i, j) == SPACE) {
} x = i; y = j; return; bool State::check(Move move) {
}
State State::takeMove(Move move) { switch (move) { case UP:
} return true; if (x1 = 3) return false; break; case DOWN: case LEFT: case RIGHT:
} int destX, destY; switch (move) { case UP:
} 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); destX = x1; break; destX = x; destY = y + 1; break; case DOWN: case LEFT: case RIGHT: void State::evaluate() {
for (int ii = 0; ii
for (int jj = 0; jj grid, ii, jj)) {
h += abs(ijj); int g = moves, h = 0; for (int i = 0; i
for (int j = 0; j
//if (AT(grid, i, j) != AT(pEndState->grid, i, j)) // ++h;
if(AT(grid, i, j) == SPACE) continue; if (!pEndState) return;
}
}
}
} } } this->value = g + h; //求该状态的逆序数 //逆序数定义为：
//
不计空格，将棋盘按顺序排列，
//
对于grid[i]，存在jgrid[i]，即为逆序。 //
所有棋子的逆序总数为逆序数。 int State::getReversedCount() {
}
/*=====================Methods for cla \"NineGrid\"=====================*/ //显示信息
void NineGrid::ShowInfo() {
}
//构造函数
NineGrid::NineGrid(string &start, string &dest) : startState(start), endState(dest) cout
} return count;
} if (grid[i] > grid[j]) ++count; int count = 0; for (int i = 0; i
if(grid[i] == SPACE)
continue; if (grid[j] == SPACE) continue; for (int j = 0; j
{
}
//当初始状态和目标状态的逆序数的奇偶性相同时，问题才有解 bool NineGrid::compareReversed() { 2; }
//解决问题
bool NineGrid::solve() {
}
//实施一步决策，将得到的新状态添加到列表，返回是否达到目标状态
} print(NULL); return false;
} //从当前状态开始决策
for (int i = 0; i
} Move move = (Move)i; if (nowState->check(move)) {
} if (takeMove(nowState, move))
return true;
openList.push_back(new State(startState)); while(!openList.empty()) {
//获取一个状态为当前状态
State *nowState = openList.back(); openList.pop_back(); closeList.push_back(nowState); cout
cout
bool NineGrid::takeMove(State *nowState, Move move) {
}
//检查给定状态是否存在于列表中
State* NineGrid::findInList(vector &listToCheck, State &state) {
}
//根据达到的目标状态，回溯打印出求解过程 void NineGrid::print(State *endState) {
cout
addSymptom(pDisease, strInput); } else { ioFile.close(); return true; //添加一个疾病，返回此疾病信息的指针
Disease* Expert::addDisease(const string &name) {
}
//添加疾病的症状
void Expert::addSymptom(Disease *disease,const string &symptom) { }
//诊断函数
void Expert::diagnosis() {
cout请输入症状: （或\"不确定\"以开始模糊搜索）\">symptomInput; //用户输入的第一个症状 string symptomInput; //用户有的症状和没有的症状
vector symptomHave, symptomNotHave; //搜索的结果列表
vector findList; disease->symptomList.push_back(symptom); Disease disease; disease.name = name; m_DiseaseList.push_back(disease); return &m_DiseaseList.back();
for (vector::iterator ite = findList.begin(); ite !=
bool remove = false;//是否从findList列表中排除本疾病
for (unsigned int j = 0; j symptomList.size(); ++j) {
Disease *pDisease = *ite; if (find(symptomNotHave.begin(), symptomNotHave.end(),
//在symptomNotHave列表中找到此症状，直接排除 remove = true; break; findList.end();) { if (symptomInput == \"不确定\") {
} //添加所有疾病到findList列表中
for (unsigned int i = 0; i
for (unsigned int i = 0; i
} //添加输入的症状到symptomHave列表中 symptomHave.push_back(symptomInput); Disease *pDisease = &m_DiseaseList[i]; for (unsigned int j = 0; j symptomList.size(); ++j) {
} if (symptomInput == pDisease->symptomList[j]) { } findList.push_back(pDisease); findList.push_back(&m_DiseaseList[i]); } else { pDisease->symptomList[j]) != symptomNotHave.end()) { } else if (find(symptomHave.begin(), symptomHave.end(),
//在symptomHave，symptomNotHave列表中不存在这个症状，则询问 if (optionSelect(\"->是否有症状\"\" + pDisease->symptomList[j] +
} //询问得知有此症状，添加症状到symptomHave列表中 symptomHave.push_back(pDisease->symptomList[j]); //询问得知没有此症状，添加症状到symptomNotHave列表中，并排除symptomNotHave.push_back(pDisease->symptomList[j]); remove = true; break; pDisease->symptomList[j]) == symptomHave.end()) { \"\"?\\n(y/n): \")) { } else { 此疾病
}
} } } if (remove) {
} //需要排除此疾病
ite = findList.erase(ite); //迭代器后移 ++ite; } else { cout
} cout知识库中未找到匹配的记录！\"根据已有的知识库，可能的疾病为：\"
for (unsigned int i = 0; i
} coutname; if (i != findList.size() - 1) cout
bool Expert::optionSelect(const string &question) {
cout>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
六、实验结果
