人工智能实验2传教士过河问题

.

人工智能实验报告

.

班级：计研-12班 学号：2012312120105 姓名：孔德星

.

实验二 知识表示方法

1．实验目的

（1）了解知识表示相关技术；

（2）掌握问题规约法或者状态空间法的分析方法。

2．实验内容（2个实验内容可以选择1个实现）

（1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法；

（2）状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。

3．实验报告要求

（1）简述实验原理及方法，并请给出程序设计流程图。

实验原理：假设开始时传教士、野人和船都在右岸，用数组(a,b,c)分别表示右岸传教士个数、右岸野人个数、船的位置，则可分为三种情况讨论:

A、n>m/2。此种情况下，先把所有的野人度过去，每次返回一个野人，当出现(m,0,0)情况时，返回m-n个野人(若m==n,返回1个野人)。然后渡n个传教士，此时野人==传教士，然后返回一个野人和传教士，再开始最大限度的渡传教士，每次返回一个野人,最终直到a==b==c==0；

B、n<=3&&n<=m/2 || n==1，显然此时无解；

C、n>=4&&n<=m/2，此时只能每次传n/2个传教士和野人,每次返回一个野人和传教士,直到最终结果。

程序流程图：

.

.

N开始递归执行Y输入传教士和野人的个数m右岸野人个数是否为0Y输入船一次能载的人数n是否n>m/2NY是否(m<=3 && n<=m/2) || n==1Y失败结束N船是否在右岸N是否已经成功Y成功结束N是否n>m/2N递归执行Y分情况递归执行NN船是否能一次把右岸的人载完N递归执行Y右岸传教士个数是否为0Y是否右岸传教士和接人个数不相等并且不为0Y递归执行N成功结束N是否右岸传教士和接人个数相等并且不为0Y递归执行N是否右岸传教士人数为0Y递归执行

（2）源程序清单： 本程序用C++语言编写。

#include \ using namespace std; bool flag = false; bool af = false; bool bf = false; bool ef = false; bool f = false;

//标记是否有解 //标记a是否为0

//当b变为0后赋值为true; //当a==b后赋值为true //判断n是否大于m/2

int m;//传教士野人的个数 int n;//船一次能装载的人数 void mc(int a,int b,int c); int main() {

.

cout<<\传教士与野人过河问题。\\n假设最初时传教士与野人在河的右岸。\\n\; cout<<\请输入传教士野人的个数：\\n\; cin>>m;

cout<<\请输入船一次能装载的人数: \\n\; cin>>n;

cout<<\右岸传教士人数\\t\<<\右岸野人个数\\t\<<\船的位置（1.右岸 0左岸）\<

{cout<<\;

system(\); return 0;

}

//此种情况无解

if(n > m/2) f = true; mc(m,m,1);

.

}

if(flag == true){ cout<<\; else{

cout<<\;

system(\); return 0;

}

}

void mc(int a,int b,int c) {

if(flag==true) if(c == 1)

{

//如果n>m/2

return;

cout<<\<

if(bf!=true) { }

else if(ef!=true&& af==false) { }

if(ef == true && af==false) {

if(a>=n)

mc(a-n,b,1-c);

//递归

for(int i = n;i>=0;i--) { }

if(a>=i) { }

mc(a-i,b,1-c);

//递归

if(flag==true) return;

if(a+b<=n) { }

for(int j = n;j >= 0;j--) { }

if(b >= j) { }

mc(a,b-j,1-c); if(flag==true)

return;

//递归

else

//如果a+b<=n,完全渡过

mc(0,0,1-c);

//递归 //b未达到过0

.