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

1、精选优质文档-倾情为你奉上人工智能实验报告班级：计研-12班学号：05姓名：孔德星实验二 知识表示方法1实验目的（1）了解知识表示相关技术；（2）掌握问题规约法或者状态空间法的分析方法。2实验内容（2个实验内容可以选择1个实现）（1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法；（2）状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。3实验报告要求（1）简述实验原理及方法，并请给出程序设计流程

2、图。实验原理：假设开始时传教士、野人和船都在右岸，用数组(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个传教士和野人,

3、每次返回一个野人和传教士,直到最终结果。程序流程图：（2）源程序清单：本程序用C+语言编写。#include "iostream"using namespace std;bool flag = false;/标记是否有解bool af = false;/标记a是否为0bool bf = false;/当b变为0后赋值为true;bool ef = false;/当a=b后赋值为truebool f = false;/判断n是否大于m/2int m;/传教士野人的个数int n;/船一次能装载的人数void mc(int a,int b,int c);int main()co

4、ut<<"传教士与野人过河问题。n假设最初时传教士与野人在河的右岸。n"cout<<"请输入传教士野人的个数：n"cin>>m;cout<<"请输入船一次能装载的人数: n"cin>>n;cout<<"右岸传教士人数t"<<"右岸野人个数t"<<"船的位置（1.右岸 0左岸）"<<endl;if(m<=3 && n<=m/2) | n=1)/

5、此种情况无解cout<<"No solution!n"system("pause");return 0;if(n > m/2)f = true;mc(m,m,1);if(flag = true)cout<<"Success!n"elsecout<<"No solution!n"system("pause");return 0; void mc(int a,int b,int c)if(flag=true) return;if(c = 1)cout<

6、<"t"<<a<<"tt"<<b<<"tt"<<c<<"tn"if(f=true)/如果n>m/2if(bf!=true)/b未达到过0if(a+b<=n)/如果a+b<=n,完全渡过mc(0,0,1-c);/递归elsefor(int j = n;j >= 0;j-)if(b >= j)mc(a,b-j,1-c);/递归if(flag=true) return;else if(ef!=true&&a

7、mp; af=false)for(int i = n;i>=0;i-)if(a>=i)mc(a-i,b,1-c);/递归if(flag=true) return;if(ef = true && af=false)if(a>=n)mc(a-n,b,1-c);/递归else if(a+b<n)mc(0,0,1-c);elsemc(0,b-(n-a),1-c);if(af=true)if(b>=n)mc(a,b-n,1-c);/递归elsemc(a,0,1-c);else mc(a-n/2,b-n/2,1-c); /递归if(c = 0)cout<

8、<"t"<<a<<"tt"<<b<<"tt"<<c<<"tn"if(a = b && b = c && a = 0)flag = true;return;if(f=true)/如果n>m/2if(b=0)bf = true;if(m <= n)mc(a,b+1,1-c);/递归elsemc(a,b+m-n,1-c);if(a=b)ef = true;mc(a+1,b+1,1-c);/递归if(a = 0)af = true;mc(a,b+1,1-c);/递归while(bf!=true)mc(a,b+1,1-c);/递归else/k<=n/2&&k>3mc(a+1,b+1,1-c);/递归 （3）实验结果及分析。程序实验结果如下图。当然，传教士与野人个数为3，船一次能载两个人，这是最经典的例子。本程序也可输入其它数据，同样可以得到正确结果。本程序主要采用状态空间法和递归调用来解决问题。程序在一开始就排除了不可能会成功的状态空间，也对剩下的状态空间也进行了分类，这样直接减少了问题的复杂程度