package com.xxx;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class River {
// 栈，候选合法状态
private LinkedList<State> candidateLegalStates = new LinkedList<State>();
// 所有合法状态，避免重复搜索，只添加不删除
private List<State> allLegalStates = new ArrayList<State>();
private int totalMan;
private int totalSpook;
public River(int totalMan, int totalSpook) {
this.totalMan = totalMan;
this.totalSpook = totalSpook;
}
public void action() {
candidateLegalStates.clear();
allLegalStates.clear();
// 起始状态
State root = new State(totalMan, totalSpook, 1, null);
candidateLegalStates.add(root);
allLegalStates.add(root);
// 如果栈已空，将结束，并且说明没有合法解
while (!candidateLegalStates.isEmpty()) {
State currentState = candidateLegalStates.getLast();
int man = currentState.man;
int spook = currentState.spook;
int boat = currentState.boat;
// 如果到达目标状态，则退出
if (man == 0 && spook == 0 && boat == 0) {
break;
}
// 根据当前状态生成合法状态，并压入栈中
boolean atLeastOne = false;
if (boat == 1) {
// 1. 1鬼1人过
if (man >= 1 && spook >= 1) {
State newState = new State(man - 1, spook - 1, (boat ^ 1),
currentState);
boolean temp = push(newState);
if (temp == true) {
atLeastOne = temp;
}
}
// 2. 2鬼过,在此岸
if (spook >= 2) {
State newState = new State(man, spook - 2, (boat ^ 1),
currentState);
boolean temp = push(newState);
if (temp == true) {
atLeastOne = temp;
}
}
// 3. 2人过,在此岸
if (man >= 2) {
State newState = new State(man - 2, spook, (boat ^ 1),
currentState);
boolean temp = push(newState);
if (temp == true) {
atLeastOne = temp;
}
}
} else if (boat == 0) {
// 1. 1鬼1人回,在彼岸
if (totalMan - man >= 1 && totalSpook - spook >= 1) {
State newState = new State(man + 1, spook + 1, (boat ^ 1),
currentState);
boolean temp = push(newState);
if (temp == true) {
atLeastOne = temp;
}
}
// 2. 1鬼回,在彼岸
if (totalSpook - spook >= 1) {
State newState = new State(man, spook + 1, (boat ^ 1),
currentState);
boolean temp = push(newState);
if (temp == true) {
atLeastOne = temp;
}
}
// 3. 1人回,在彼岸
if (totalMan - man >= 1) {
State newState = new State(man + 1, spook, (boat ^ 1),
currentState);
boolean temp = push(newState);
if (temp == true) {
atLeastOne = temp;
}
}
}
// 如果没有生成一个合法状态，则将该节点弹出栈
if (!atLeastOne) {
candidateLegalStates.removeLast();
}
}
}
public void print() {
State target = candidateLegalStates.getLast();
System.out.print(target.toString() + " (" + (totalMan - target.man)
+ "," + (totalSpook - target.spook) + ")\n");
while (target.parent != null) {
target = target.parent;
System.out.print(target.toString() + " (" + (totalMan - target.man)
+ "," + (totalSpook - target.spook) + ")\n");
}
}
// 输出结果
public void printSteps() {
System.out.println("人鬼过河问题(本算法只找出其中一个解；而且不一定是动作最少的解)");
System.out.println("(左岸人数,左岸鬼数,船在左岸或右岸:=1表示船在左岸;=0表示船在右岸) (右岸人数,右岸鬼数)");
List<State> steps = steps();
for (State state : steps) {
System.out.print(state.toString() + " (" + (totalMan - state.man)
+ "," + (totalSpook - state.spook) + ")\n");
}
}
// 由叶节点向上查找目标解路径，直到根节点
private List<State> steps() {
LinkedList<State> steps = new LinkedList<State>();
if (!candidateLegalStates.isEmpty()) {
State target = candidateLegalStates.getLast();
steps.addFirst(target);
while (target.parent != null) {
target = target.parent;
steps.addFirst(target);
}
}
return steps;
}
// 判断新状态是否合法
private boolean isLegal(State state) {
int m = state.man;
int c = state.spook;
int MM = totalMan;
int CC = totalSpook;
if (m >= 0 && m <= MM && c >= 0 && c <= CC) {
// 首先判断是一个合法状态
if ((m == 0 && MM >= CC - c) || (m == MM && m >= c)
|| (m >= c && MM - m >= CC - c)) {
// 然后判断该状态是否已经加入到allLegalStates中，避免重复搜索
if (!allLegalStates.contains(state)) {
return true;
}
}
}
return false;
}
// 根据状态合法性决定是否放入candidateLegalStates和allLegalStates
private boolean push(State newState) {
if (isLegal(newState)) {
candidateLegalStates.addLast(newState);
allLegalStates.add(newState);
return true;
} else {
return false;
}
}
public static void main(String[] args) {
River river = new River(3, 3);
// 执行算法
river.action();
// river.print();
// 打印结果
river.printSteps();
}
static class State {
/**
* 此岸人数
*/
private int man;
/**
* 此岸鬼数
*/
private int spook;
/**
* 船的位置：1--船此左岸 0--船在彼岸
*/
private int boat;
/**
* 指向状态树中的父节点——对应着该状态的前一个状态
*/
private State parent;
public State(int man, int spook, int boat, State parent) {
this.man = man;
this.spook = spook;
this.boat = boat;
this.parent = parent;
}
@Override
public int hashCode() {
int result = 17;
result = 37 * result + man;
result = 37 * result + spook;
result = 37 * result + boat;
return result;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof State) {
State that = (State) obj;
if (that.man == man && that.spook == spook && that.boat == boat) {
return true;
}
}
return false;
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder();
buf.append("(").append(man).append(",").append(spook).append(",")
.append(boat).append(")");
return buf.toString();
}
}
}
评论0