人鬼过河问题

Question

河的一边有三个人和三个鬼，河中有一小船，每次最多能乘坐2个人或鬼，而且至少要有一个人或鬼船才能行驶。请设计一种算法，把人和鬼都送到对岸。注：不论是在河边、船上，如果人鬼数量相同，则鬼和人能和谐相处，鬼不吃人，否则，鬼吃掉人。要求算法能给出整个运送过程，包括每次船行驶的方向（是驶向对岸还是返回），船上的人和鬼数量。
  
相信大家都接触过这个问题，我在论坛也参考过一些算法，但是觉得效率不是很高
  
我自己有个想法就是把所有过河的策略都列出来，形成一棵树（每个方法代表一个结点），然后通过搜索找出符合要求的结点，可以通过广度搜索和深度搜索，最后符合的结点为最后方法。但是想法是有，如何用JAVA语言编写该算法，符合题目要求不知道从何如何入手，请大家发表下意见帮帮忙，最好有些代码参考下，谢谢

Answer 1

可以用回溯法..但是发现也挺麻烦的...
由于是边想边写的,可能有些混乱..
凑活看看吧,希望能给你些思路
public class Test { public static void main(String[] args) {
Game game = new Game();
game.cycle();
for (int i = 0; i < game.getList().size(); i++) {
System.out.println(game.getList().get(i).toString());
}
}}public class Side implements Cloneable { public final static int PERSON = 0; public final static int GHOST = 1; public final static int NO = 0; public final static int YES = 1; private int presonQty = 0; private int ghostQty = 0; private int hasBoat = 0; Side() {
} Side(int preson, int ghost, int boat) {
this.presonQty = preson;
this.ghostQty = ghost;
this.hasBoat = boat;
} public int getHasBoat() {
return hasBoat;
} public void setHasBoat(int boat) {
this.hasBoat = boat;
} public int getGhostQty() {
return ghostQty;
} public void setGhostQty(int ghost) {
this.ghostQty = ghost;
} public int getPresonQty() {
return presonQty;
} public void setPresonQty(int preson) {
this.presonQty = preson;
} public boolean addOneObject(int presonOrGhost) {
boolean forReturn = true;
if (presonOrGhost == 0) {
this.setPresonQty(this.getPresonQty() + 1);
}
if (presonOrGhost == 1) {
this.setGhostQty(this.getGhostQty() + 1);
}
return forReturn;
} public boolean removeOneObject(int presonOrGhost) {
boolean forReturn = true;
if (presonOrGhost == Side.PERSON) {
this.setPresonQty(this.getPresonQty() - 1);
if (this.getPresonQty() < 0) {
forReturn = false;
}
}
if (presonOrGhost == Side.GHOST) {
this.setGhostQty(this.getGhostQty() - 1);
if (this.getGhostQty() < 0) {
forReturn = false;
}
}
return forReturn;
} public void changeBoat() {
this.setHasBoat((this.getHasBoat() + 1) % 2);
} public Object clone() {
Side side = null;
try {
side = (Side) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return side;
} public String toString() {
return "{preson:" + presonQty + ",ghost:" + ghostQty + ",isHasBoat:"
+ (hasBoat == Side.YES ? "Y" : "N") + "}";
} public boolean isSafe() {
if (this.getPresonQty() * (this.getPresonQty() - this.getGhostQty()) < 0) {
return false;
}
return true;
} public boolean equals(Object side) {
return this.getPresonQty() == ((Side) side).getPresonQty()
&& this.getGhostQty() == ((Side) side).getGhostQty()
&& this.getHasBoat() == ((Side) side).getHasBoat();
}
}

Answer 2

public class Cross implements Cloneable { private Side sideA = new Side(3, 3, 1); private Side sideB = new Side(0, 0, 0); private int[] presonOrGhosts = null; public boolean cross(int[] presonOrGhosts) {
this.setPresonOrGhosts(presonOrGhosts);
int presonQty = 0;
int ghostQty = 0;
boolean forReturn = true;
for (int i = 0; i < presonOrGhosts.length; i++) {
if (presonOrGhosts[i] == Side.PERSON) {
presonQty++;
}
if (presonOrGhosts[i] == Side.GHOST) {
ghostQty++;
}
forReturn = this.crossOneObject(presonOrGhosts[i]) && forReturn;
}
this.changeSide();
forReturn = sideA.isSafe() && forReturn;
forReturn = sideB.isSafe() && forReturn;
forReturn = isSafeOnBoat(presonQty, ghostQty) && forReturn;
return forReturn;
} public boolean crossOneObject(int presonOrGhost) {
boolean forReturn = true;
if (this.sideA.getHasBoat() == Side.YES) {
forReturn = this.getSideA().removeOneObject(presonOrGhost)
&& forReturn;
forReturn = this.getSideB().addOneObject(presonOrGhost)
&& forReturn;
}
if (this.sideB.getHasBoat() == Side.YES) {
forReturn = this.getSideB().removeOneObject(presonOrGhost)
&& forReturn;
forReturn = this.getSideA().addOneObject(presonOrGhost)
&& forReturn;
}
return forReturn;
} public boolean isSafeOnBoat(int presonQty, int ghostQty) {
if (presonQty * (presonQty - ghostQty) < 0) {
return false;
}
return true;
} public String toString() {
String forReturn = "";
String way1 = "";
String way2 = "";
if (sideA.getHasBoat() == Side.YES) {
way1 = "               <<<-------";
way2 = "<<<-------               ";
} else {
way1 = "               ------->>>";
way2 = "------->>>               ";
}
forReturn = forReturn + "sideA:" + sideA.toString() + ";sideB:"
+ sideB.toString();
int presonQty = 0;
int ghostQty = 0;
if (this.getPresonOrGhosts() != null) {
for (int i = 0; i < this.getPresonOrGhosts().length; i++) {
if (this.getPresonOrGhosts()[i] == Side.PERSON) {
presonQty++;
}
if (this.getPresonOrGhosts()[i] == Side.GHOST) {
ghostQty++;
}
}
forReturn = way1 + "boat{preson:" + presonQty + ",ghost:" + ghostQty
+ "}" + way2 + " \n" + forReturn;
}
return forReturn;
} public void changeSide() {
this.getSideA().changeBoat();
this.getSideB().changeBoat();
} public Side getSideA() {
return sideA;
} public void setSideA(Side sideA) {
this.sideA = sideA;
} public Side getSideB() {
return sideB;
} public void setSideB(Side sideB) {
this.sideB = sideB;
} public int[] getPresonOrGhosts() {
return presonOrGhosts;
} public void setPresonOrGhosts(int[] presonOrGhosts) {
this.presonOrGhosts = presonOrGhosts;
} public Object clone() {
Cross cross = null;
try {
cross = (Cross) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
cross.setSideA((Side) cross.getSideA().clone());
cross.setSideB((Side) cross.getSideB().clone());
if (cross.getPresonOrGhosts() == null) {
cross.setPresonOrGhosts(null);
} else {
int[] presonOrGhostsCopy = new int[cross.getPresonOrGhosts().length];
System.arraycopy(cross.getPresonOrGhosts(), 0, presonOrGhostsCopy,
0, presonOrGhostsCopy.length);
cross.setPresonOrGhosts(presonOrGhostsCopy);
}
return cross;
} public boolean equals(Object cross) {
return this.getSideA().equals(((Cross) cross).getSideA())
&& this.getSideB().equals(((Cross) cross).getSideB());
}
}import java.util.LinkedList;public class Game {
private LinkedList list = new LinkedList(); private int[] presonOrGhosts = null; private Cross cross = new Cross(); Game() {
list.add(this.cross.clone());
} public int[] combination(int qty, int[] previousArray) {
int temp = 0; int[] forReturn = null;
if (previousArray != null) {
forReturn = new int[previousArray.length];
System.arraycopy(previousArray, 0, forReturn, 0, forReturn.length);
}
for (int i = 0; previousArray != null && i < previousArray.length; i++) {
if (previousArray[i] == Side.PERSON) {
forReturn[i] = Side.GHOST;
temp = 1;
break;
}
}
if (temp == 0) {
if (previousArray == null) {
forReturn = new int[] { Side.PERSON };
} else if (previousArray.length == qty) {
forReturn = null;
} else {
forReturn = new int[previousArray.length + 1];
for (int i = 0; i < forReturn.length; i++) {
forReturn[i] = Side.PERSON;
}
}
}
return forReturn;
} public void cycle() {
presonOrGhosts = combination(2, presonOrGhosts);
if (presonOrGhosts != null) {
if (!cross.cross(presonOrGhosts)) {
cross.cross(presonOrGhosts);
// System.out.println("" + list.size() + ",NO");
} else {
int sign = 0;
for(int i=0;i<list.size();i++)
{
if(this.cross.equals(list.get(i)))
{
cross.cross(presonOrGhosts);
sign = 1;
// System.out.println("" + list.size() + ",NO");
break;
}
}
if(sign==0)
{
list.add(cross.clone());
presonOrGhosts = null;
// System.out.println("" + list.size() + ",YES");
}
}
} else {
presonOrGhosts = ((Cross) list.getLast()).getPresonOrGhosts();
list.removeLast();
cross = (Cross) ((Cross) list.getLast()).clone();
// System.out.println("" + list.size() + ",BACK");
}
if (!isOver()) {
this.cycle();
}
} public boolean isOver() {
if (this.cross.getSideA().getPresonQty() == 0
&& this.cross.getSideA().getGhostQty() == 0
&& this.cross.getSideA().getHasBoat() == Side.NO) {
return true;
} else {
return false;
}
} public LinkedList getList() {
return list;
} public void setList(LinkedList list) {
this.list = list;
}
}