📄 macps.java
字号:
import java.io.*;
import java.util.*;
/*建立数据结构:RiverSide*/
class RiverSide {
int Cannibal;
int Missionary;
public RiverSide() {
}
public String toString() { //不会输出散列码
return " Cannibal " + Cannibal + " Missionary " + Missionary;
}
}
/*建立数据结构:Boat*/
class Boat {
int Cannibal;
int Missionary;
public Boat() {
}
public Boat( int Cannibal , int Missionary ) {
this.Cannibal = Cannibal;
this.Missionary = Missionary;
}
}
/*建立数据结构:Node*/
class Node {
int f , h , steps , id , parentid;
Boat boat;
RiverSide riverside1;
RiverSide riverside2;
int side;
public Node() {
}
public Node( int f , int h , int steps , Boat boat , RiverSide riverside1 , RiverSide riverside2 , int side , int id , int parentid ) {
this.f = f;
this.h = h;
this.steps = steps;
this.boat = boat;
this.riverside1 = riverside1;
this.riverside2 = riverside2;
this.side = side;
this.id = id;
this.parentid = parentid;
}
}
/*主类Missionary And Cannibal Pass Solution*/
class MACPS {
public Vector Open=new Vector();
public Vector Close=new Vector();
int id = 0;
public void getSolutionStep() {
Boat boat1 = new Boat();
Boat boat2 = new Boat();
RiverSide riverside1 = new RiverSide();
RiverSide riverside2 = new RiverSide();
RiverSide riverside3 = new RiverSide();
RiverSide riverside4 = new RiverSide();
boolean flag =true;
Node Source = new Node( 0 , 0 , 0 , boat1 , riverside1 , riverside2 , 0 , 0 , 0 ); //初始化起始节点
Source.riverside1.Cannibal = 3;
Source.riverside1.Missionary = 3;
Source.riverside2.Cannibal = 0;
Source.riverside2.Missionary = 0;
Source.boat.Cannibal = 0;
Source.boat.Missionary = 0;
Source.side = 1;
Source.id = 0;
Source.parentid = 0;
Source.h = 4;
Source.f = 4;
Source.steps = 0;
Node Target = new Node( 0 , 0 , 0 , boat2 , riverside3 , riverside4 , 0 , 0 , 0 ); //初始化目标节点
Target.riverside1.Cannibal=0;
Target.riverside1.Missionary=0;
Target.riverside2.Cannibal=3;
Target.riverside2.Missionary=3;
Target.boat.Cannibal=0;
Target.boat.Missionary=0;
push( Source , Open );
Node Current = Source;
while( flag == true ) {
if( Open.isEmpty() ) { //表头为空结束循环
flag = false;
break;
}
Current = pop( Open );
push( Current , Close );
if( isTarget( Current , Target ) ) //比较是否是目标节点
break;
extend( Current , Target , Open ); //扩展OPEN中的节点
atFirstOpen(); //将OPEN排序
}
Node Father; //从目标节点通过Father节点找出合法算符,继续扩展Father
Vector Result = new Vector();
if( flag == true ) {
Result.add( Current );
int m = Current.parentid;
int k = 0;
while( m > 0 ) {
Father = found( m , Close , Target );
Result.add( Father );
m = Father.parentid;
k++;
}
}
else {
System.out.print("solution isn't found");
}
Result.add(Source);
Stack aaa = new Stack();
Stack bbb = new Stack();
Stack ccc = new Stack();
for( int i = 0; i < Result.size(); i++ ) {
/*System.out.println( ( (Node)Result.get(i) ).riverside1 + " " + " withboat: " + ( (Node)Result.get(i) ).side
+ "--------" + ( (Node)Result.get(i) ).riverside2 ); */
aaa.push( ( (Node)Result.get(i) ).riverside1 );
bbb.push( ( (Node)Result.get(i) ).side );
ccc.push( ( (Node)Result.get(i) ).riverside2 );
}
for( int i = 0; i < Result.size(); i++ ) {
System.out.println("Left Side: " + aaa.pop() + " withboat: " + bbb.pop() + "\n" );
System.out.println("Right Side: " + ccc.pop() + "\n\n");
}
}
public void push( Node sour , Vector open ) {
open.add( sour );
}
public Node pop( Vector open ) { Node firstnode = (Node)open.get(0);
open.removeElementAt(0);
return firstnode;
}
public boolean isTarget( Node cur,Node tar ) {
if( cur.riverside1.Cannibal == tar.riverside1.Cannibal && cur.riverside1.Missionary == tar.riverside1.Missionary && cur.side == tar.side )
return true;
else
return false;
}
public void extend( Node current , Node tar , Vector open ) { //找出下一步合法操作，并扩展节点
int nCannibal1 = 0;
int nMissionary1 = 0;
int nCannibal2 = 0;
int nMissionary2 = 0;
int i;
Boat boatState[] = new Boat [5];
for( i = 0; i < 5;i++ )
boatState[i] = new Boat();
if(current.side==1) { //尽量多的去到目标河岸，运2个的操作符优先，野人优先
boatState[0].Cannibal = 2;
boatState[0].Missionary = 0;
boatState[1].Cannibal = 1;
boatState[1].Missionary = 1;
boatState[2].Cannibal = 0;
boatState[2].Missionary = 2;
boatState[3].Cannibal = 1;
boatState[3].Missionary = 0;
boatState[4].Cannibal = 0;
boatState[4].Missionary = 1;
}
else { //尽量少的回来，运1个的操作符优先
boatState[0].Cannibal = 0;
boatState[0].Missionary = 1;
boatState[1].Cannibal = 1;
boatState[1].Missionary = 0;
boatState[2].Cannibal = 0;
boatState[2].Missionary = 2;
boatState[3].Cannibal = 1;
boatState[3].Missionary = 1;
boatState[4].Cannibal = 2;
boatState[4].Missionary = 0;
}
boolean flag = true;
int j;
for( j = 0; j < 5; j++ ) {
if(current.side==1) { //船在岸就运人过去，就做“-”运算
nCannibal1 = current.riverside1.Cannibal - boatState[j].Cannibal;
nMissionary1 = current.riverside1.Missionary - boatState[j].Missionary;
}
else { //船不在岸运人过来，做“+”运算
nCannibal1 = current.riverside1.Cannibal + boatState[j].Cannibal;
nMissionary1 = current.riverside1.Missionary + boatState[j].Missionary;
}
//对岸的人数
nCannibal2 = 3 - nCannibal1;
nMissionary2 = 3 - nMissionary1;
if( ( nCannibal1 <= nMissionary1 || nMissionary1 == 0 ) && ( nCannibal2 <= nMissionary2 || nMissionary2 == 0 ) && nCannibal1 >= 0 && nMissionary1 >= 0 && nCannibal2 >= 0 && nMissionary2 >= 0 ) { //判断扩展的节点是否合法。即野人少于传教士
if(j<5) {
current.boat.Cannibal = boatState[j].Cannibal;
current.boat.Missionary = boatState[j].Missionary;
Boat boat = new Boat();
RiverSide riverside1 = new RiverSide();
RiverSide riverside2 = new RiverSide();
Node next = new Node( 0 , 0 , 0 , boat , riverside1 , riverside2 , 0 , 0 , 0 );
next.riverside1.Cannibal = nCannibal1;
next.riverside1.Missionary = nMissionary1;
next.riverside2.Cannibal = nCannibal2;
next.riverside2.Missionary = nMissionary2;
next.boat.Cannibal = 0;
next.boat.Missionary = 0;
next.id = ++id;
next.parentid = current.id;
next.steps = current.steps+1;
if( next.steps%2 == 0 )
next.side = 1;
else
next.side = 0;
next.h = next.riverside1.Cannibal+next.riverside1.Missionary - 2*next.side;
next.f = next.h + next.steps;
if( next.id != 0 ) { //判断扩展节点是否在Close中
int k = 0;
while( ( k<Close.size() ) ) {
if( ( next.riverside1.Cannibal != ( (Node)( Close.get(k) ) ).riverside1.Cannibal) ||
( next.riverside1.Missionary != ( (Node)( Close.get(k) ) ).riverside1.Missionary ) || ( next.side != ( (Node)(Close.get(k) ) ).side ) )
flag = false;
else
flag = true;
if( flag == true )
break;
k++;
}
}
if(flag == false)
push(next,Open); //把扩展点加入Open
}
}
}
}
public void atFirstOpen() { //把最小值放在Open表首位
int indexmin=0;
Node temp;
Node node0 = (Node)Open.get(0);
int minvalue = node0.f;
for( int i = 0; i < Open.size(); i++ ) {
Node opei = (Node)Open.get(i);
if( opei.f < minvalue ) {
minvalue = opei.f;
indexmin = i;
}
}
temp = (Node)Open.get(0);
Open.setElementAt( (Node)Open.elementAt(indexmin) , 0 );
Open.setElementAt( temp , indexmin );
}
public Node found( int k , Vector vec , Node source ) { //Close表中id相同的节点
Node result = source;
int i;
for( i = 0; i < vec.size(); i++ ) {
if( k == ( (Node)vec.get(i) ).id ) {
result = (Node)vec.get(i);
}
}
return result;
}
public static void main(String[] args){
MACPS a = new MACPS();
a.getSolutionStep();
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -