請用JAVA編寫牧師野人過河問題
时间: 2024-01-21 20:16:55 浏览: 28
以下是用 Java 语言实现的牧师野人过河问题:
```java
import java.util.*;
public class RiverBank {
private int missionaries;
private int cannibals;
private boolean boatOnLeftBank;
public RiverBank(int missionaries, int cannibals, boolean boatOnLeftBank) {
this.missionaries = missionaries;
this.cannibals = cannibals;
this.boatOnLeftBank = boatOnLeftBank;
}
public boolean isValidState() {
if (missionaries < 0 || cannibals < 0) {
return false;
}
if (missionaries > 3 || cannibals > 3) {
return false;
}
if (cannibals > missionaries && missionaries > 0) {
return false;
}
if (3 - cannibals > 3 - missionaries && 3 - missionaries > 0) {
return false;
}
return true;
}
public boolean isGoalState() {
return missionaries == 0 && cannibals == 0 && !boatOnLeftBank;
}
public List<RiverBank> getNextStates() {
List<RiverBank> nextStates = new ArrayList<>();
int direction = boatOnLeftBank ? 1 : -1;
for (int i = 1; i <= 2; i++) {
for (int j = 0; j <= i; j++) {
int nextMissionaries = missionaries + j * direction;
int nextCannibals = cannibals + (i - j) * direction;
RiverBank nextState = new RiverBank(nextMissionaries, nextCannibals, !boatOnLeftBank);
if (nextState.isValidState()) {
nextStates.add(nextState);
}
}
}
return nextStates;
}
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (!(obj instanceof RiverBank)) {
return false;
}
RiverBank other = (RiverBank) obj;
return missionaries == other.missionaries && cannibals == other.cannibals && boatOnLeftBank == other.boatOnLeftBank;
}
@Override
public int hashCode() {
return Objects.hash(missionaries, cannibals, boatOnLeftBank);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
sb.append(missionaries);
sb.append("M,");
sb.append(cannibals);
sb.append("C,");
sb.append(boatOnLeftBank ? "L" : "R");
sb.append("}");
return sb.toString();
}
}
```
```java
import java.util.*;
public class MissionariesAndCannibalsProblem {
public static void main(String[] args) {
RiverBank initialState = new RiverBank(3, 3, true);
RiverBank goalState = new RiverBank(0, 0, false);
List<RiverBank> path = bfs(initialState, goalState);
if (path != null) {
for (RiverBank state : path) {
System.out.println(state);
}
} else {
System.out.println("No solution found!");
}
}
private static List<RiverBank> bfs(RiverBank initialState, RiverBank goalState) {
Map<RiverBank, RiverBank> parentMap = new HashMap<>();
Queue<RiverBank> queue = new LinkedList<>();
Set<RiverBank> visited = new HashSet<>();
queue.add(initialState);
visited.add(initialState);
while (!queue.isEmpty()) {
RiverBank currentState = queue.poll();
if (currentState.equals(goalState)) {
return getPath(parentMap, currentState);
}
for (RiverBank nextState : currentState.getNextStates()) {
if (!visited.contains(nextState)) {
visited.add(nextState);
parentMap.put(nextState, currentState);
queue.add(nextState);
}
}
}
return null;
}
private static List<RiverBank> getPath(Map<RiverBank, RiverBank> parentMap, RiverBank currentState) {
List<RiverBank> path = new ArrayList<>();
path.add(currentState);
while (parentMap.containsKey(currentState)) {
currentState = parentMap.get(currentState);
path.add(0, currentState);
}
return path;
}
}
```
该程序使用广度优先搜索算法,通过遍历每个状态和状态的后继状态来寻找最短路径。在这里,状态是指河岸上的传教士数量、野人数量和船的位置。该算法使用一个队列来存储待处理的状态,并使用一个 Set 来避免重复访问相同的状态。在每一步中,程序会检查当前状态是否为目标状态,如果是则返回从初始状态到目标状态的路径。如果没有找到解决方案,则返回 null。