传教士与野人过河问题实验报告

1 问题定义

河的两岸有三个传教士和三个野人需要过河，目前只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会被野人攻击，怎么找出一种安全的渡河方案呢？

2 算法分析

首先，先来看看问题的初始状态和目标状态，定义河的两岸分别为左岸和右岸，设定状态集合为（左岸传教士人数，右岸野人数，右岸传教士人数，右岸野人数，船的位置），船的位置：-1表示船在左岸，1表示船在右岸。 初始状态：（3,3,0,0,0，-1） 目标状态：（0，0，3，3，1）

然后，整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：

渡1野人、渡1传教士、渡1野人1传教士、渡2野人、渡2传教士

根据船的位置，向左移或向右移通过递归依次执行5种算符，判断是否找到所求，并排除不符合实际的状态，就可以找到所有可能的解，如图1所示为递归函数流程图。

数据结构方面采用如下所示的结构体存储当前传教士、野人、船三者的状态。

structriverSides{ };

intchurchL;//左岸传教士数 intwildL;//左岸野人数 intchurchR;//右岸传教士数 intwildR;//右岸野人数

int boat;//船的位置，-1在左岸，1在右岸

图 1 传教士与野人过河递归函数流程图

3 编程实现

程序使用C++实现，具体代码如下：

#include #include #include usingnamespacestd;

structriverSides { };

intmycount = 0;//统计成功过河次数

intCvsWdfs(riverSideslastcurrentState, vectorlastParameters, vectoroperation, intifboacurrentStatety) {

if (lastcurrentState.boat == lastParameters[i].boat)

return 0;

if (lastcurrentState.churchR == 3 &&lastcurrentState.wildR == 3) { }

//判断过河操作否重复，去除死循环

for (inti = 0; i

if (lastParameters[i].wildL == lastcurrentState.wildL&&lastParameters[i].churchL {

mycount++;

cout<<\第\<

cout<

cout<

intchurchL;//左岸传教士数 intwildL;//左岸野人数 intchurchR;//右岸传教士数 intwildR;//右岸野人数

int boat;//船的位置，-1在左岸，1在右岸

== lastcurrentState.churchL)

}

}

//检验人数数据合法性

if (lastcurrentState.churchL< 0 || lastcurrentState.wildL< 0 ||

return 0;

lastcurrentState.churchR< 0 || lastcurrentState.wildR< 0)

//传教士是否被吃

if ((lastcurrentState.churchL

return 0;

|| (lastcurrentState.churchR

//递归执行五类过河操作，boat=-1船在左岸，boat=1船在右岸，传入boat为上一次船位置 //下次应当取反

riverSidescurrentState; //两个传教士过河

if (lastcurrentState.boat == 1)

operation.push_back(\左岸->右岸\); operation.push_back(\右岸->左岸\); else

currentState.churchL = lastcurrentState.churchL - 2 * lastcurrentState.boat; currentState.wildL = lastcurrentState.wildL;

currentState.churchR = lastcurrentState.churchR + 2 * lastcurrentState.boat; currentState.wildR = lastcurrentState.wildR; currentState.boat = -lastcurrentState.boat; lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters,operation, 0); operation.pop_back(); lastParameters.pop_back(); //两个野人过河

if (lastcurrentState.boat == 1)

operation.push_back(\左岸->右岸\); operation.push_back(\右岸->左岸\); else

currentState.churchL = lastcurrentState.churchL;

currentState.wildL = lastcurrentState.wildL - 2 * lastcurrentState.boat; currentState.churchR = lastcurrentState.churchR;

currentState.wildR = lastcurrentState.wildR + 2 * lastcurrentState.boat; currentState.boat = -lastcurrentState.boat; lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters, operation, 0); lastParameters.pop_back(); operation.pop_back();

//一个野人，一个传教士

if (lastcurrentState.boat == 1)

operation.push_back(\左岸->右岸\); operation.push_back(\右岸->左岸\); else

currentState.churchL = lastcurrentState.churchL - 1 * lastcurrentState.boat; currentState.wildL = lastcurrentState.wildL - 1 * lastcurrentState.boat; currentState.churchR = lastcurrentState.churchR + 1 * lastcurrentState.boat; currentState.wildR = lastcurrentState.wildR + 1 * lastcurrentState.boat; currentState.boat = -lastcurrentState.boat; lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters,operation, 0); operation.pop_back(); lastParameters.pop_back(); //一个传教士过河

if (lastcurrentState.boat == 1)

operation.push_back(\左岸->右岸\); operation.push_back(\右岸->左岸\); else

currentState.churchL = lastcurrentState.churchL - 1 * lastcurrentState.boat; currentState.wildL = lastcurrentState.wildL;

currentState.churchR = lastcurrentState.churchR + 1 * lastcurrentState.boat; currentState.wildR = lastcurrentState.wildR; currentState.boat = -lastcurrentState.boat; lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters, operation, 0); operation.pop_back(); lastParameters.pop_back(); //一个野人过河

if (lastcurrentState.boat == 1)

operation.push_back(\左岸->右岸\); operation.push_back(\右岸->左岸\); else

currentState.churchL = lastcurrentState.churchL;

currentState.wildL = lastcurrentState.wildL - 1 * lastcurrentState.boat; currentState.churchR = lastcurrentState.churchR;

currentState.wildR = lastcurrentState.wildR + 1 * lastcurrentState.boat; currentState.boat = -lastcurrentState.boat; lastParameters.push_back(currentState);

CvsWdfs(currentState, lastParameters, operation, 0); operation.pop_back(); lastParameters.pop_back();