---
title: 宣教師と人食い人種問題
tags: []
categories: ["Programming", "Algorithm", "Search", "Cannibalism"]
date: 2011-07-19T17:25:51Z
updated: 2011-07-19T17:25:51Z
---

探索問題復習シリーズその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
    ]