学步园

2个野人去，1个野人回
2个野人去，1个野人回
2个传教士去，1个野人与1个传教士回
2个传教士去，1个野人回
2个野人去，1个野人回
2个野人去，完成
-------------------------------------------------------------------------
一．【实验题目】
过河问题的求解：三个修道士和三个野人过河，船一次最多只能载两个人，在任何时候修道士的人数不能少于野人人数，否则野人会吃掉修道士。找出六个人顺利过河的所有方案。

二．【实验目的】
通过具体问题的编程求解，了解人工智能的基本解决方法；使用一种搜索策略，以加深理解。

三．【实验内容】
编制程序，使用一定的搜索策略，找出所有过河方法。

四．【设计思想】
1．编程工具
采用C++语言编制控制台程序；
2．整体思想
采用四元组（修道士人数[0~3]，会划船野人数[0~2]，不会划船野人数[0/1]，船所在岸[0/1]）描述结点状态，开始状态为（3，2，1，0），目标状态为（0，0，0，1）。采用带回溯的深度优先搜索策略，共定义了7种合法操作{2,0,0},{1,0,0},{1,1,0},{0,1,0},{0,2,0},{0,1,1},{1,0,1}代表上船的人数，根据船所在位置决定在状态上是加或者减操作。扩展结点时按顺序应用操作，知道回溯到初始状态且所有操作用完，程序结束。
3．类设计
state类：描述状态结点，包括描述状态的相关成员变量和操作变量的成员函数
river类：描述和解决过河问题

五．【算法和数据结构】
1．算法
采用带回溯的深度优先策略。
在每个合法结点上应用所有7种操作，生成所有结点，然后判断结点的合法与否，确定是否回溯。每找到一种方法只要没有生成所有结点则回溯继续搜索。直到回溯到初始结点并且初始结点的所有操作已经应用完毕，则整个搜索过程结束。
2.数据结构
采用链表结构，结点是生成的状态，当前结点在链表头。结点中包含状态信息和程序需要的相关控制信息。
新扩展生成的结点放在链表头，回溯时删除头结点并移动头指针。
当找到一种过河方案时，当前链表中的所有结点就是按顺序生成的状态结点，只要遍历链表输出状态就可以得到该种方法经过的状态和所用的操作。
七．【运行结果】
Find one method! the number is 1
(3,2,1,0)->(2,1,1,1)->(3,1,1,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,0,1,1)->(1,0,1,0)->(0,0,0,1)
Find one method! the number is 2
(3,2,1,0)->(2,1,1,1)->(3,1,1,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,0,1,1)->(0,1,1,0)->(0,0,0,1)
Find one method! the number is 3
(3,2,1,0)->(2,1,1,1)->(3,1,1,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,1,0,1)->(1,1,0,0)->(0,0,0,1)
Find one method! the number is 4
(3,2,1,0)->(2,1,1,1)->(3,1,1,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,1,0,1)->(0,2,0,0)->(0,0,0,1)
Find one method! the number is 5
(3,2,1,0)->(3,0,1,1)->(3,1,1,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,0,1,1)->(1,0,1,0)->(0,0,0,1)
Find one method! the number is 6
(3,2,1,0)->(3,0,1,1)->(3,1,1,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,0,1,1)->(0,1,1,0)->(0,0,0,1)
Find one method! the number is 7
(3,2,1,0)->(3,0,1,1)->(3,1,1,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,1,0,1)->(1,1,0,0)->(0,0,0,1)
Find one method! the number is 8
(3,2,1,0)->(3,0,1,1)->(3,1,1,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,1,0,1)->(0,2,0,0)->(0,0,0,1)
Find one method! the number is 9
(3,2,1,0)->(3,1,0,1)->(3,2,0,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,0,1,1)->(1,0,1,0)->(0,0,0,1)
Find one method! the number is 10
(3,2,1,0)->(3,1,0,1)->(3,2,0,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,0,1,1)->(0,1,1,0)->(0,0,0,1)
Find one method! the number is 11
(3,2,1,0)->(3,1,0,1)->(3,2,0,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,1,0,1)->(1,1,0,0)->(0,0,0,1)
Find one method! the number is 12
(3,2,1,0)->(3,1,0,1)->(3,2,0,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,1,0,1)->(0,2,0,0)->(0,0,0,1)
Find one method! the number is 13
(3,2,1,0)->(2,2,0,1)->(3,2,0,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,0,1,1)->(1,0,1,0)->(0,0,0,1)
Find one method! the number is 14
(3,2,1,0)->(2,2,0,1)->(3,2,0,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,0,1,1)->(0,1,1,0)->(0,0,0,1)
Find one method! the number is 15
(3,2,1,0)->(2,2,0,1)->(3,2,0,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,1,0,1)->(1,1,0,0)->(0,0,0,1)
Find one method! the number is 16
(3,2,1,0)->(2,2,0,1)->(3,2,0,0)->(3,0,0,1)->(3,1,0,0)->(1,1,0,1)->(2,1,1,0)->(0,1,1,1)->(0,2,1,0)->(0,1,0,1)->(0,2,0,0)->(0,0,0,1)
Complete!
16 methods have been found!

八．【程序清单】
1．state.h

class state
{
protected:
int iStateNumber;//状态编号
int iopNumber;//当前最大操作编号
public:
int iCenobite;//修道士数
int iWildManA;//会划船的野人数
int iWildManB;//不会划船的野人数
int iBank;//0表示此岸，1表示彼岸
state * pFather,* pChild;//指向父、子结点的指针
state(int,int,int,int);
~state();
int setNumber(int);
int getNumber();
void operate();
int isError();
int getOpNumber();
void setOpNumber(int);
int addOpNumber();
void getState(int *);
int isTarget();
int isStart();

static int opp[7][3];
static int Max[3];
};

2.state.cpp

#include "state.h"
#include "iostream.h"
#include "process.h"
//用四元组构造一个state结点
state::state(int cenobite,int wildManA,int wildManB,int bank)
{
iStateNumber=0;
iopNumber=0;
iCenobite=cenobite;
iWildManA=wildManA;
iWildManB=wildManB;
iBank=bank;
pFather=0;
pChild=0;
}
//设置状态编号
int state::setNumber(int stateNumber)
{
this->iStateNumber=stateNumber;
return stateNumber;
}
//获得状态编号
int state::getNumber()
{
return iStateNumber;
}
//获得当前操作编号
int state::getOpNumber()
{
return iopNumber;
}
//设置当前操作编号
void state::setOpNumber(int opNumber)
{
this->iopNumber=opNumber;
}
//当前操作编号加1
int state::addOpNumber()
{
if(iopNumber>6)
return iopNumber;
else{
iopNumber++;
return iopNumber;
}
}
//获取当前四元组状态，放在state里面
void state::getState(int * state)
{
state[0]=iCenobite;
state[1]=iWildManA;
state[2]=iWildManB;
state[3]=iBank;
}
//根据当前设置的操作编号进行操作
void state::operate()
{
if(iBank==0){
iCenobite=iCenobite-state::opp[iopNumber][0];
iWildManA=iWildManA-state::opp[iopNumber][1];
iWildManB=iWildManB-state::opp[iopNumber][2];
iBank=1;
}
else{
iCenobite=iCenobite+state::opp[iopNumber][0];
iWildManA=iWildManA+state::opp[iopNumber][1];
iWildManB=iWildManB+state::opp[iopNumber][2];
iBank=0;
}
}
//判断当前结点是否是非法结点
int state::isError()
{
if(iCenobite && iCenobite<iWildManA+iWildManB)
return 1;
if(3-iCenobite && 3-iCenobite<3-iWildManA-iWildManB)
return 1;
if(iCenobite<0||iWildManA<0||iWildManB<0)
return 1;
if(iCenobite>3||iWildManA>2||iWildManB>1)
return 1;
return 0;
}
//判断当前结点是否是目标结点
int state::isTarget()
{
if(!iCenobite && !iWildManA && !iWildManB && iBank)
return 1;
else
return 0;
}
//判断当前结点是否为初始结点
int state::isStart()
{
if(iCenobite==3&&iWildManA==2&&iWildManB==1&&iBank==0)
return 1;
return 0;
}

3.river.h

#include "state.h"

class river
{
int count;
public:
state * phead;//指向链表的第一个（最新生成的）结点
river();
void extend();
int isTwice();
void remount();
static int iSuccess;
};

4.river.cpp

#include "river.h"
#include <iostream.h>

//构造函数
river::river()
{
count=0;
phead=new state(3,2,1,0);//生成初始结点
}
//扩展当前结点
void river::extend()
{
int temp[4];
phead->getState(temp);
phead->pChild=new state(temp[0],temp[1],temp[2],temp[3]);
phead->pChild->pFather=phead;
phead=phead->pChild;
phead->setOpNumber(phead->pFather->getOpNumber());
phead->setNumber(this->phead->pFather->getNumber()+1);
phead->operate();
phead->setOpNumber(0);
}
//判断头指针所指结点是否已经生成
int river::isTwice()
{
state * current=phead->pFather;
while(current){
if(current->iCenobite==phead->iCenobite &&
current->iWildManA==phead->iWildManA &&
current->iWildManB==phead->iWildManB &&
current->iBank==phead->iBank )
return 1;
current=current->pFather;
}
return 0;
}
//回溯到上一结点
void river::remount()
{
phead=phead->pFather;
phead->addOpNumber();
}
//在main函数之前初始化静态成员变量
int state::opp[7][3]={{2,0,0},{1,0,0},{1,1,0},{0,1,0},
{0,2,0},{0,1,1},{1,0,1}};
int state::Max[3]={3,2,1};
int river::iSuccess=0;
int state::total=0;
void main(void)
{
river River;
for(;;)
{
River.extend();//扩展结点
//判断是否保留此结点
if(River.phead->isError() || River.isTwice())
River.remount();//回溯
//判断是否需要继续回溯
while(River.phead->getOpNumber()>6 && !River.phead->isStart())
River.remount();
if(River.phead->isTarget()){//搜索到一种方法
river::iSuccess++;
cout<<"/nFind one method! the number is "
<<river::iSuccess <<"/n";
state * temp;
temp=River.phead;
while(temp->pFather){
temp=temp->pFather;
}
while(temp){
cout<<"("<<temp->iCenobite<<","<<
temp->iWildManA<<","<<
temp->iWildManB<<","<<
temp->iBank<<")->";
temp=temp->pChild;
}
River.remount();//回溯以继续搜索其他方法
}
//搜索完所有结点
if(River.phead->isStart() && River.phead->getOpNumber()==7){
cout<<"/nComplete!/n";
cout<<"/n"<<river::iSuccess
<<" methods have been found!/n";
break;
}
}
}

对N＝5、k≤3时，求解传教士和野人问题的产生式系统各组成部分进行描述（给出综合数据库、规则集合的形式化描述，给出初始状态和目标条件的描述），并画出状态空间图。

　　答： 1，综合数据库
定义三元组：（m, c, b）
其中：0=<m<=5，表示传教士在河左岸的人数。
0=<c<=5，表示野人在河左岸的认输。
b属于集合(0,1)，b=1，表示船在左岸，b=0，表示船在右岸。
2，规则集
规则集可以用两种方式表示，两种方法均可。
第一种方法： 按每次渡河的人数分别写出每一个规则，共(3 0)、(0 3)、(2 1)、(1 1)、(1 0)、(0 1)、(2 0)、(0 2)八种渡河的可能（其中(x y)表示x个传教士和y个野人上船渡河），因此共有16个规则（从左岸到右岸、右岸到左岸各八个）。注意：这里没有(1 2)，因为该组合在船上的传教士人数少于野人人数。
规则集如下：
r1：IF (m, c, 1) THEN (m-3, c, 0)
r2：IF (m, c, 1) THEN (m, c-3, 0)
r3：IF (m, c, 1) THEN (m-2, c-1, 0)
r4：IF (m, c, 1) THEN (m-1, c-1, 0)
r5：IF (m, c, 1) THEN (m-1, c, 0)
r6：IF (m, c, 1) THEN (m, c-1, 0)
r7：IF (m, c, 1) THEN (m-2, c, 0)
r8：IF (m, c, 1) THEN (m, c-2, 0)

r9 ：IF (m, c, 0) THEN (m+3, c, 1)
r10：IF (m, c, 0) THEN (m, c+3, 1)
r11：IF (m, c, 0) THEN (m+2, c+1, 1)
r12：IF (m, c, 0) THEN (m+1, c+1, 1)
r13：IF (m, c, 0) THEN (m+1, c, 1)
r14：IF (m, c, 0) THEN (m, c+1, 1)
r15：IF (m, c, 0) THEN (m+2, c, 1)
r16：IF (m, c, 0) THEN (m, c+2, 1)

第二种方法： 将规则集综合在一起，简化表示。规则集如下：
r1：IF (m, c, 1) and 0< i+j〈=3 and (i>= j or i=0) THEN (m-i, c-j, 0)
r2：IF (m, c, 0) and 0< i+j〈=3 and (i>= j or i=0) THEN (m+i, c+j, 1)

3，初始状态：(5, 5, 1)