《传教士野人过河问题-两种解法思路》由会员分享，可在线阅读，更多相关《传教士野人过河问题-两种解法思路（24页珍藏版）》请在金锄头文库上搜索。
1、实验传教士野人过河问题37030602 王世婷一、实验问题传教士和食人者问题(The Missionaries and Cannibals Problem )。在河的左岸有 3 个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受 到以下条件的限制：(1)传教士和食人者都会划船，但船一次最多只能装运两个；(2)在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安 全过河的计划。、解答步骤(1) 设置状态变量并确定值域M为传教士人数，C为野人人数，B为船数，要求M=C 且M
2、+C 1)0, o)b 1)J =4 P2215 o)r 仁?LfluN I)2, 0)*=3 Pcsf=4 Pzck/AAMCM-(Of 缶 1)1，o)图1状态空间图箭头旁边所标的数字表示了P或Q操作的下标,即分别表示船载的传教士数和食人者数三、算法设计 方法一：树的遍历根据规则由根（初始状态）扩展出整颗树，检测每个结点的“可扩展标记”，为“-1的即目标结点。由目标结点上溯出路径 见源程序1。方法二：启发式搜索构造启发式函数为：6.01 ML CL满足规则时-其它选择较大值的结点先扩展。见源程序2四、实验结果 方法一的实验结果：传教士野人过河问题第1种方法：第1次：左岸到右岸，传教士过去1
3、人，野人过去1人第2次：右岸到左岸，传教士过去1人，野人过去0人第3次：左岸到右岸，传教士过去0人，野人过去2人第4次：右岸到左岸，传教士过去0人，野人过去1人第5次：左岸到右岸，传教士过去2人，野人过去0人第6次：右岸到左岸，传教士过去1人，野人过去1人第7次：左岸到右岸，传教士过去2人，野人过去0人第8次：右岸到左岸，传教士过去0人，野人过去1人第9次：左岸到右岸，传教士过去0人，野人过去2人第10次：右岸到左岸，传教士过去0人，野人过去1人第11次：左岸到右岸，传教士过去0人，野人过去2人第2种方法:第1次：左岸到右岸,传教士过去1人,野人过去第2次：右岸到左岸,传教士过去1人,野人过去
4、第3次：左岸到右岸,传教士过去0人,野人过去第4次：右岸到左岸,传教士过去0人,野人过去第5次：左岸到右岸,传教士过去2人,野人过去第6次：右岸到左岸,传教士过去1人,野人过去第7次：左岸到右岸,传教士过去2人,野人过去第8次：右岸到左岸,传教士过去0人,野人过去第9次：左岸到右岸,传教士过去0人,野人过去第10次：右岸到左岸，传教士过去1人，野人过去0人第11次：左岸到右岸，传教士过去1人，野人过去1人第3种方法:第1次：左岸到右岸,传教士过去0人,野人过去第2次：右岸到左岸,传教士过去0人,野人过去第3次：左岸到右岸,传教士过去0人,野人过去第4次：右岸到左岸,传教士过去0人,野人过去第5
5、次：左岸到右岸,传教士过去2人,野人过去第6次：右岸到左岸,传教士过去1人,野人过去第7次：左岸到右岸，传教士过去2人，野人过去0人第8次：右岸到左岸，传教士过去0人，野人过去1人第9次：左岸到右岸，传教士过去0人，野人过去2人第10次：右岸到左岸，传教士过去0人，野人过去1人第11次：左岸到右岸，传教士过去0人，野人过去2人第4种方法:第1次：左岸到右岸,传教士过去0人,野人过去第2次：右岸到左岸,传教士过去0人,野人过去第3次：左岸到右岸,传教士过去0人,野人过去第4次：右岸到左岸,传教士过去0人,野人过去第5次：左岸到右岸,传教士过去2人,野人过去第6次：右岸到左岸,传教士过去1人,野人
6、过去第7次：左岸到右岸,传教士过去2人,野人过去第8次：右岸到左岸,传教士过去0人,野人过去第9次：左岸到右岸,传教士过去0人,野人过去第10次：右岸到左岸，传教士过去1人，野人过去0人第11次：左岸到右岸，传教士过去1人，野人过去1人方法二的实验结果：传教士野人过河问题方法如下1人，野人过去1人l:2r,2yr:1r,1y1人，野人过去0人l:3r,2yr:0r,1y0人，野人过去2人l:3r,0yr:0r,3y0人，野人过去1人l:3r,1yr:0r,2y2人，野人过去0人l:1r,1yr:2r,2y1人，野人过去1人l:2r,2yr:1r,1y2人，野人过去0人l:0r,2yr:3r,1
7、y0人，野人过去1人l:0r,3yr:3r,0y0人，野人过去2人l:0r,1yr:3r,2y0人，野人过去1人l:0r,2yr:3r,1y0人，野人过去2人l:0r,0yr:3r,3y第1次：左岸到右岸，传教士过去 第2次：右岸到左岸，传教士过去 第3次：左岸到右岸，传教士过去 第4次：右岸到左岸，传教士过去 第5次：左岸到右岸，传教士过去 第6次：右岸到左岸，传教士过去 第7次：左岸到右岸，传教士过去 第8次：右岸到左岸，传教士过去 第9次：左岸到右岸，传教士过去 第10次：右岸到左岸，传教士过去 第11次：左岸到右岸，传教士过去 问题结束由结果可以看出，方法二的结果为方法一的第一种结果，
8、两者具有一致性。五、总结与教训：最开始时采用的方法为： 用向量A X,X1,X2,X3,X4,X5,X6表示状态，其中X。 X2表示三个传教士的位置，X3 X5表示三个野人的位置，X6表示船的位置。0表示在河左岸，1表示已渡过了河，在河右岸。设初始状态和目标状态分别为：S：So 0,0,0,0,0,0,0G：Sg 1,1,1,1,1,1,J但在描述规则时发现这样定义会造成规则麻烦、不清晰，原因在于此题并不关心是哪几个传教士和野人在船上，仅关心其人数，故没有必要将每个人都设置变量，分别将传教士、野人、船作为一类即可。四、源代码1.源程序1:树的遍历%野人和传教士过河问题%date:2010/12
9、/14%author:wang shi tingfunction =guohe()clear all;close all;global n no de;n=2;solveNum=1; % 问题的解法result=zeros(100,1);no de=zeros(300,5);node(1,:)=3,3,1,1,-1;% 初始化%1左岸传教士数2左岸野人数3船(1为左岸，0为右岸)%4是否可扩展（1为可扩展）5父节点号（-1表示无父节点，即为初始节点）j=1；% for j=1: nwhile if j nbreakendif node（j,4）=1 %判断结点是否可扩展if node( j,3
10、)=1 % 船在左岸if ( (node( j,1)=0) | (node( j,1)=3) )&(no de(j,2)=1)forward( j,0,1);endif(no de(j,1)=1&node( j,2)=1|node( j,1)=3&node( j,2)=2)forward( j,1,0);j,1)=node( j,2)endif (node( j,1)=1 & node( forward( j,1,1);endif (node( j,1)=0 | node( j,1)=3)& node(j,2)=2forward( j,0,2);endif(no de(j,1)=2&node( j,2)=2| node(j,1)=3&node(j,2)=1)forwar
