探索問題復習シリーズその2。宣教師と人食い人種問題を幅優先探索で解いてみた。
一応ルールを張っとく
- 3人の宣教師と3人の人食い人種が本土から対岸に2人乗りのボートで渡ろうとしている。
- ボートの上や川岸で宣教師の数より人食い人種の数が多くなると，宣教師は人食い人種に食べられる。
- 宣教師が食べられることなく川を渡りきるにはどうしたら良いか？
以下、適当Java実装。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Cannibalism {
public static class State {
// 本土={宣教師の数、人食い人種の数}
int hondo[] = new int[2];
// 対岸={宣教師の数、人食い人種の数}
int taigan[] = new int[2];
// ボート(true = 本土側、false=対岸側)
boolean boat = true;
// 前状態
State prev;
// 手数
int depth = 0;
List<State> movableStatees() {
List<State> states = new ArrayList<State>();
// 移動する可能性のある組み合わせ(宣教師、人食い人種)
int[][] vv = { { 1, 0 }, { 2, 0 }, { 1, 1 }, { 0, 1 }, { 0, 2 } };
for (int[] v : vv) {
int[] h = hondo.clone();
int[] t = taigan.clone();
if (boat) {
// 本土側
h[0] -= v[0];
h[1] -= v[1];
t[0] += v[0];
t[1] += v[1];
} else {
// 対岸側
h[0] += v[0];
h[1] += v[1];
t[0] -= v[0];
t[1] -= v[1];
}
if (validState(h, t)) {
State s = new State();
s.hondo = h;
s.taigan = t;
s.boat = !boat;
s.prev = this;
s.depth = depth + 1;
states.add(s);
}
}
return states;
}
static boolean validState(int[] hondo, int[] taigan) {
// 負の数にはならない
if (hondo[0] < 0 || taigan[0] < 0 || hondo[1] < 0 || taigan[1] < 0) {
return false;
}
// 本土の宣教師数が人食い人種数より少なくなると不正
if (hondo[0] > 0 && hondo[0] < hondo[1]) {
return false;
}
// 対岸の宣教師数が人食い人種数より少なくなると不正
if (taigan[0] > 0 && taigan[0] < taigan[1]) {
return false;
}
return true;
}
public void printTrace() {
Deque<State> d = new ArrayDeque<State>();
State s = this;
while (s != null) {
d.addFirst(s);
s = s.prev;
}
System.out.println(d);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(System.getProperty("line.separator"));
for (int i = 0; i < 3; i++) {
if (hondo[0] > i) {
sb.append("M");
} else {
sb.append(" ");
}
if (hondo[1] > i) {
sb.append("C");
} else {
sb.append(" ");
}
sb.append("|");
if (i == 1) {
if (boat) {
sb.append("> ");
} else {
sb.append(" <");
}
} else {
sb.append(" ");
}
sb.append("|");
if (taigan[0] > i) {
sb.append("M");
} else {
sb.append(" ");
}
if (taigan[1] > i) {
sb.append("C");
} else {
sb.append(" ");
}
sb.append(System.getProperty("line.separator"));
}
return sb.toString();
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + (boat ? 1231 : 1237);
result = prime * result + Arrays.hashCode(hondo);
result = prime * result + Arrays.hashCode(taigan);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
State other = (State) obj;
if (boat != other.boat)
return false;
if (!Arrays.equals(hondo, other.hondo))
return false;
if (!Arrays.equals(taigan, other.taigan))
return false;
return true;
}
}
public static State breadthFirstSearch(State initial, State goal) {
Set<State> closed = new HashSet<State>();
Queue<State> open = new LinkedList<State>();
initial.depth = 0;
open.add(initial);
while (!open.isEmpty()) {
State s = open.poll();
closed.add(s);
for (State next : s.movableStatees()) {
if (closed.contains(next)) {
continue;
}
if (goal.equals(next)) {
System.out.println("goal");
System.out.println("depth=" + next.depth);
System.out.println("closed=" + closed.size());
return next;
}
open.add(next);
}
}
return null;
}
public static void main(String[] args) {
State initial = new State();
initial.hondo[0] = 3;
initial.hondo[1] = 3;
initial.taigan[0] = 0;
initial.taigan[1] = 0;
initial.boat = true;
State goal = new State();
goal.hondo[0] = 0;
goal.hondo[1] = 0;
goal.taigan[0] = 3;
goal.taigan[1] = 3;
goal.boat = false;
State result = breadthFirstSearch(initial, goal);
if (result != null) {
result.printTrace();
} else {
System.out.println("NG");
}
}
}
実行結果
goal
depth=11
closed=13
[
MC| |
MC|> |
MC| |
,
MC| |MC
MC| <|
| |
,
MC| | C
MC|> |
M | |
,
M | | C
M | <| C
M | | C
,
MC| | C
M |> | C
M | |
,
MC| |MC
| <|MC
| |
,
MC| |MC
MC|> |
| |
,
C| |MC
C| <|M
| |M
,
C| |M
C|> |M
C| |M
,
C| |MC
| <|MC
| |M
,
MC| |MC
|> |MC
| |
,
| |MC
| <|MC
| |MC
]