java.txt

用java实现传教士野人过河问题的求解

野人过河问题  
 
　　一、问题描述：
　　有M个传教士和N个野人来到河边渡河, 河岸有Q条船, 每次至多可供K人乘渡。问传教士为了安全起见, 应如何规划摆渡方案, 使得任何时刻, 河两岸以及船上的野人数目总是不超过传教士的数目(否则不安全, 传教士有可能被野人吃掉)。即求解传教士和野人从左岸全部摆渡到右岸的过程中, 任何时刻满足M(传教士数)≥C(野人数)和M+C≤k的摆渡方案。 
　　只讨论N＝M为3、k为2 Q＝1乘渡问题, 这样传教士和野人问题的描述就具体为如下: 
　　三个传教士与三个野人来到河边, 有一条船可供一人或两人乘渡, 问题是如何用这条船渡河才能使得河的任一岸上野人的数目总不超过传教士的数目(当然, 如果某一岸上只有野人而没有传教士是允许的，野人也可以自己开船渡河)? 
　　用一个三元组(a.b,c)来表示河岸上的状态, 其中a,b分别代表某一岸上传教士与野人的数目, c=1表示船在左岸, c=0则表示船不在左岸。 
　　两岸上a>=b ,3-a>=3-b。
　　在船上的时候不需要比较因为是通过坐船的方法来制定个规则集的，所以自然符合题目要求。如果a＝0情况下可以不考虑M>=C这个条件
　　因而问题的初始状态是(3 3 1), 目标状态是(0 0 0)。
　　二、 规则集合: 
　　根据船摆渡的情况可能出现的规则为a传教士人数 b野人人数 c船在左岸与否
　　1 if (a,b.1) then(a-1,b-1,0); 
　　2 if (a,b,1) then (a-2,b,0); 
　　3 if (a,b,1) then (a-1,b,0); 
　　4 if(a,b,1) then (a,b-2,0); 
　　5 if (a,b,1) then (a,b-1,0); 
　　6 if (a,b,0) then (a+1,b+1,1); 
　　7 if (a,b,0) then (a+2,b,1); 
　　8 if (a,b,0) then (a+1,b,1); 
　　9 if (a,b,0) then (a,b+1,1); 
　　10 if (a,b.0) then (a,b+2,1); 
　　
　　在这些已经存在的规则中有些是不会出现的 或者说他们的出现只会更大程度上增加死循环出现的几率。比如规则7和10一般情况下不会出现。
　　再有这些规则本身是存在优先级的所以进行判断的时候应该加以分析。
　　三 程序实现（java）：
　　class PassRiver
　　{
　　 public static void main(String[] args)
　　 {
　　 int a=3,b=3,c=1,a0=3,b0=3;//a:churchman b savage
　　 //a0,b0 beginning state
　　 System.out.println("("+a+","+b+","+c+")");
　　 while(!((a==0)&&(b==0)&&(c==0)))
　　 {
　　 
　　 if(c==1)
　　 {
　　 if((b==3||b==2)&&((a0-a>=b0-b+2)||a==3))
　　 {
　　 b=b-2;c=0;
　　 System.out.println("("+a+","+b+","+c+")");
　　 }
　　 else if(((a-2>=b)&&(a0-a+2)>=(b0-b))||a==2)
　　 {
　　 a=a-2;c=0;
　　 System.out.println("("+a+","+b+","+c+")");
　　
　　 } 
　　 else if((a>=b)&&(b>=1)&&(a0-a+1)>=(b0-b+1))
　　 {
　　 a=a-1; b=b-1; c=c-1;
　　 System.out.println("("+a+","+b+","+c+")");
　　 }
　　 else if(((a-1>=b)&&(a0-a+1>=b0-b))||(a==1)&&(b0-b)<=2)
　　 {
　　 a=a-1;c=c-1;
　　 System.out.println("("+a+","+b+","+c+")");
　　 }
　　 else 
　　 {
　　 b=b-1; c=c-1;
　　 System.out.println("("+a+","+b+","+c+")");
　　 }
　　 }
　　 else
　　 {
　　 if((a>=b+1)||(a==0))
　　 {
　　 b=b+1;c=c+1;
　　 System.out.println("("+a+","+b+","+c+")"); 
　　 }
　　 else if(((a+1>=b)&&(a0-a-1>=b)||(a0-a-1)==0)&&(a!=b))
　　 {
　　 a=a+1; c=c+1;
　　 System.out.println("("+a+","+b+","+c+")"); 
　　 }
　　 else if((a==b)&&a!=3)
　　 {
　　 a=a+1;b=b+1;c=c+1;
　　 System.out.println("("+a+","+b+","+c+")"); 
　　 }
　　 else 
　　 {
　　 //System.out.println("error");
　　 }
　　 }
　　 }
　　 System.out.println("success");
　　}
　　}
　　 
　　
　　
　　结果 
　　
　　四延伸
　　 如果问题如开始所述有有M个传教士和N个野人来到河边渡河, 河岸有Q条船, 每次至多可供K人乘渡。那么可以把每个船作为一个线程单独考虑于一个船的时候情况类似（忽略了过河的时间），但是非常麻烦的是对规则的制定。
　　五存在问题
　　 1规则集内的各个规则的优先级有一点混乱， 不能清晰的划分。而且有些规则的优先级是相同的，没能在程序中没能实现
　　 2 还不能够很好的用人工智能的思维方法来思考问题，导致开始的时候仍然用以前的思想来思考问题。