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

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

2、图。实验原理：假设开始时传教士、野人和船都在右岸，用数组(a,b,c)分别表示右岸传教士个数、右岸野人个数、船的位置，则可分为三种情况讨论:A 、nm/2 。此种情况下，先把所有的野人度过去，每次返回一个野人，当出现(m,0,0)情况时， 返回 m-n 个野人 (若 m=n,返回 1 个野人 )。然后渡 n 个传教士， 此时野人 =传教士，然后返回一个野人和传教士，再开始最大限度的渡传教士，每次返回一个野人,最终直到a=b=c=0 ；B 、n=3&n=4&nm/2N递归执行Y右岸传教士递归执行载的人数 n个数是否为 0YN是否 (m=3船是否在右是否已经成分情况递归执& nm/2Y岸功行| n

3、=1YYN失败结束成功结束递归执行（ 2）源程序清单：本程序用C+ 语言编写。#includeiostreamusingnamespace std;boolflag =false ;/标记是否有解boolaf =false;/标记 a是否为 0boolbf =false;/当 b变为 0后赋值为 true;boolef =false;/ 当 a=b后赋值为 trueboolf =false ;/判断 n是否大于 m/2intm; /传教士野人的个数intn; /船一次能装载的人数voidmc( inta, int b, int c);intmain()cout 传教士与野人过河问题。n 假设最

4、初时传教士与野人在河的右岸。 n ;coutm;coutn;cout 右岸传教士人数 t 右岸野人个数 t 船的位置（ 1. 右岸 0 左岸） endl;if (m=3 & n=m/2) | n=1)/ 此种情况无解cout m/2)f = true ;mc(m,m,1);if (flag =true )cout Success!n;else cout No solution!n;system( pause );return0;void mc( inta, intb, intc)if (flag= true )return ;if ( c = 1)cout tattif (f= true )b

5、ttcm/2if (bf!= true )/b未达到过 0if ( a+b=n)/ 如果 a+b= 0;j-)if ( b = j)mc(a, b-j,1-c);if (flag= true )return ;/ 递归elseif (ef!= true & af= false )for ( inti = 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);/ 递归elseif ( a+b=n)elseelse mc(a-n/

6、2, b-n/2,1-c);mc(a,mc(a,0,1-/ 递归b-n,1- c); c);/ 递归if ( c = 0)cout tattbttcm/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/k3mc(a+1, b+1,1- c);/ 递归（ 3）实验结果及分析。程序实验结果如下图。当然，传教士与野人个数为3，船一次能载两个人，这是最经典的例子。本程序也可输入其它数据，同样可以得到正确结果。本程序主要采用状态空间法和递归调用来解决问题。程序在一开始就排除了不可能会成功的状态空间， 也对剩下的状态空间也进行了分类，这样直接减少了问题的复杂程度。另外，本程序大量采用递归调用的思想，减少了编程代码的工作