野人和传教士渡河问题是计算机算法的入门课。河的左岸有三个野人和三个传教士，他们都要过河到达右岸，只有一个船，没有船夫，最多可以容纳两个人。任何一岸野人的数目都不能多余传教士的数目。求所有渡河方案。
此问题可以抽象为图搜索问题。可以用深度优先搜索来做。图里的每一个结点代表了一个状态。从一个状态出发，每次通过可达状态最后到达最后状态，可以有几种走法。当然最优解就是最短路径。
本问题的状态应该如何描述呢？
我们可以把原先岸上的野人和传教士数目，和船停靠的位置作为状态参数，(3，3，0)表示原来左边岸上有3个传教士，3个野人，0表示船在左岸。最后我们要到达的状态是(0,0,1)野人和传教士都已经过河。
那么怎么求这一状态之后的可能状态呢？
每次可以渡过一个或者两个人，并且要使两边传教士人数多于野人人数。分别用i,j,k代表左岸传教士人数，野人人数，和船在哪里。
(i,j,k)如果k=0,下一个状态可能是(i-1,j,1)(i-2,j,1),(i,j-1,1),(i,j-2,1)(i-1,j-1,1)并且i'>j',3-i'>3-j'
如果k=1则下一状态可能是(i+1,j,0)(i+1,j+1,0)(i,j+1,0)(i,j+2,0)(i+2,j,0)
采用递归深度搜索，每次去掉已经经过的状态，直到最后状态.
注意每次递归调用之后都要回溯，以找到所有可行解
以下为java源码：
import java.util.ArrayList;
import java.util.List;
class state{
int i;
int j;
int k;
public state(int i,int j,int k){this.i=i;this.j=j;this.k=k;}
public String toString(){
return (i+" "+j+" "+k);
}
}
public class CrossRiver {
static int a[][][];
static List list=new ArrayList();
publicstatic void robot(int i,int j,int k){
if(i==0&&j==0){
System.out.println(list);
return ;}
if(k==0){
for(int t=0;t<=2;t++)
for(int q=0;q<=2-t;q++){
if(t!=0||q!=0)
if(i-t>=0&&j-q>=0&&a[i-t][j-q][1]==-1){
a[i-t][j-q][1]=0;
state s=new state(i-t,j-q,1);
list.add(s);
robot(i-t,j-q,1);
a[i-t][j-q][1]=-1;
list.remove(s);}
}
}
else {
for(int t=0;t<=2;t++)
for(int q=0;q<=2-t;q++){
if(t!=0||q!=0){//System.out.println(i+" "+j+" "+k);
if(i+t<=3&&j+q<=3){
if(a[i+t][j+q][0]==-1){
a[i+t][j+q][0]=0;
state s=new state(i+t,j+q,0);
list.add(s);
robot(i+t,j+q,0);
a[i+t][j+q][0]=-1;//回溯
list.remove(s);//回溯}}}}}return;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
a=new int[4][4][2];
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
for(int k=0;k<2;k++){
a[i][j][k]=-1;}
a[3][3][0]=0;
state s=new state(3,3,0);
list.add(s);
robot(3,3,0);
return;
}
}
如果觉得《传教士过河java_野人和传教士渡河问题的java实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
