Help us understand the problem. What is going on with this article?

宣教師と人食い人種の問題をGolangで再帰するクロージャ使って書いてみた。

More than 1 year has passed since last update.

1.背景

 いま、プログラミング言語 Go を読んでいて、これの「5.6節 無名関数」でクロージャを
再帰させるコード例が出ていたのを見て、ふと、
「これと同じように、クロージャ使って、『宣教師と人食い人種問題』を再帰で解くのをGoで書いてみよう」
と思い立って書いてみました。
 今回書いたソースコードは、https://github.com/jun68ykt/m-and-c に上げてあります。

2.「宣教師と人食い人種」問題とは

2.1 初めて聞く人のために

「宣教師と人食い人種」問題を初めて聞く人のために説明すると、以下の(1)から(3)で設定される問題です。

  (1) 川岸の片側に宣教師が3人と人食い人種が3人いて、2人まで乗れるボートがある。
  

  (2) 宣教師も人食い人種もともにボートを漕ぐことができて、何往復かすることで6人全員が
    向こう岸に渡りたい。(川に入って歩いたり泳いだりして渡るのはナシで。)

   以下の図はこの様子を描いたもので、Mは宣教師(Missionary)、C は人食い人種(Cannibal)を表す。

スクリーンショット 2017-12-10 23.16.18.png

    なお上記の図で、矢印の先に「ボートを使って何往復かして、全員が向こう岸に行きたい。」と書いて
   あるけれども、「何往復」というのは間違いで、正しくは「ボートを使って何回か行き来して、全員が
   向こう岸に行きたい。」です。なぜなら最後に片道一回が必ずあるからです。

     以下、説明の便宜上、最初に6人がいる方の岸を、上の図にそって左岸といい、
   渡って行きたいほうの岸を右岸という。
 
  (3) 何回かボートを往復(+最後の片道一回)させて、彼らは右岸に渡ろうとするが、
   注意しなければならないのは、

    左岸、右岸どちらにおいても、もし、人食い人種の人数のほうが宣教師の人数よりも多くなると、
    宣教師は人食い人種に食われてしまう

   ということ。

    例えば、上記(2)の初期状態から、宣教師2名がボートに乗って右岸に行こうとすると、
   左岸において、宣教師が1人、人食い人種が3人の状況になり、左岸で一人残された宣教師は
   人食い人種に食われてしまう。以下の図では、左岸の宣教師が、3人の人食い人種に襲われて
   食われてしまうことを表している。

スクリーンショット 2017-12-10 23.28.28.png

   もうひとつの例として、以下のような状態の場合を考える。

   スクリーンショット 2017-12-10 23.34.38.png

   このときに、もし次に右岸から人食い人種が1人だけでボートに乗って、左岸に行ったとする。

スクリーンショット 2017-12-10 23.37.34.png

    すると、ボートが左岸に着いて、乗っていた人食い人種が岸に降りたとき、左岸では
   人食い人種が2人、宣教師が1人になり、人食い人種のほうが多いので宣教師が襲われる。

スクリーンショット 2017-12-10 23.42.39.png

    このように、ボートに乗った宣教師も人食い人種も、川を渡りきったら、いったんは
   全員がボートから降りて、降りた状態での人数によって、人食い人種が宣教師を襲うか
   どうかを判定するものとする。(つまり、ボートに2人乗って降りるのは1人だけに
   しておく、ということはできない。そういうルール)

 【問題】
  上記 (1)〜(3) で設定された状況とルールにそって、何回かボートを行き来させれば、全員が
 無事に右岸に渡れるだろうか?渡れるならば、毎回のボートの行き来で、宣教師が何人、
 人食い人種が何人乗ればよいのかを示せ。

・・・というのが、この問題になります。

2.2 補足

 なお、この問題は、WikipediaのMissionaries_and_cannibals_problem に、

a well-known toy problem in artificial intelligence

と書いてあるとおり、人工知能の勉強をしていると、どこかしらで目にするクイズだったりします。
 かくいう私も、第5世代コンピュータプロジェクト ※1 の終焉期に、システム科学を専攻する学生として Prolog の勉強をしていて、それ関係の書籍 ※2に出ていて知りました。

3. Golang で解いてみます。

 それでは、Golang で解を求めるアルゴリズムを書いていきます。

3.1 川岸の状態を表す構造体

 宣教師の人数を m 、人食い人種の人数を c として、以下の構造体 RiverSideを定義します。

type RiverSide struct {
    m, c int
}

3.2 両岸の状態と、ボートがどちらにあるかを表す構造体

 全体の状況を表す構造体 State を以下のように定義します。

type State struct {
    left, right RiverSide
    boat string // "left" or "right"
}

フィールド変数が何を表すかというと、

  • leftright は、それぞれ左岸、右岸を表します。
  • boatは文字列で、ボートが左岸にあるとき "left" 、右岸にあるとき"right"になるものとします。

3.3 初期状態と目標状態

 上記の State構造体のインスタンスとして、初期状態と目標(Goal)状態を構造体リテラルで
書くと、以下のようになります。

初期状態
var initialState State = State{
    left:  RiverSide{3, 3},
    right: RiverSide{0, 0},
    boat:  "left",
}
目標状態
var goalState State = State{
    left:  RiverSide{0, 0},
    right: RiverSide{3, 3},
    boat:  "right",
}

3.4 オペレータ

  この手の問題をAI分野では探索問題といい、探索問題において、ある状態から別の状態に
 変化させる手段のことをオペレータ(作用素)といいます。👉「探索問題 オペレータ」でググる
  では、この問題においてオペレータは何かといえば、ボートによる、宣教師または人食い人種の
 一回(片道)の移動です。この一回の移動を特徴づけるのは、そこに宣教師が何人、人食い人種が
 何人乗っているのかという人数ですので、オペレータを表す構造体 Operator を以下のように定義
 します。

オペレータ
type Operator struct {
    m, c int
}

  次に、実際に選択可能なオペレータの集合を考えます。
  この問題では、ボートには2人までしか乗ることができず、また、誰も乗らなければ移動はできないので、
 以下のように、選択可能なオペレータの集合は5個の要素を持つことになります。

 選択可能なオペレータの集合 =
 { 宣教師2人がボートに乗る, 
   宣教師1人だけでボートに乗る, 
   宣教師1人と人食い人種1人がボートに乗る, 
   人食い人種1人だけでボートに乗る,  
   人食い人種2人でボートに乗る }

  上記の集合をどうプログラムで書くかですが、Goでは、(Pythonのsetのような)集合を表す型が標準で
 用意されていないので、Operatorの配列で表すことにして、以下の Operatorsを定義します。

選択可能なオペレータの配列
var Operators = [5]Operator{
    {2, 0},
    {1, 0},
    {1, 1},
    {0, 1},
    {0, 2},
}

3.5 状態が妥当であるかの検証

 「どちらの岸でも、人食い人種の人数が宣教師の人数を上回ると、人食い人種が宣教師を
 食べてしまうので、このような状態は避けなければならない」
 というルールは、状態の妥当性を検証するバリデータとして、以下のように実装しました。

状態の妥当性を検証する関数
func valid(state State) bool {
    switch {
    case state.left.m < 0 || state.left.c < 0 || state.right.m < 0 || state.right.c < 0:
        return false
    case state.left.m > 0 && state.left.c > state.left.m:
        return false
    case state.right.m > 0 && state.right.c > state.right.m:
        return false
    default:
        return true
    }
}

  上記には3つの caseがありますが、2つ目と3つ目の caseで、
 「人食い人種が宣教師を食べてしまう状況が発生するときは、falseを返す」
 ようにしています。
  1つ目のcaseは、いかなる状態でも、両岸の宣教師、人食い人種を表す mc は負数に
 なってはならないという自明な制約を表しています。

3.6 状態遷移関数

 下準備の最後に重要なのは、この状態遷移関数です。これによって、この問題は有限オートマトン
構成することになるといえます。
 ここでは、現在の状態 currentState とオペレータ op を引数として、遷移先の状態を表す nextStateと、遷移が成功したことを示す bool値の okを返す関数を、以下のように定義しました。

状態遷移関数
func stateTransition(currentState State, op Operator) (nextState State, ok bool) {

    var from, to *RiverSide

    if currentState.boat == "left" {
        from, to = &currentState.left, &currentState.right
        nextState.boat = "right"
        nextState.right = RiverSide{ to.m + op.m, to.c + op.c }
        nextState.left = RiverSide{ from.m - op.m, from.c - op.c }
    } else {
        from, to = &currentState.right, &currentState.left
        nextState.boat = "left"
        nextState.left = RiverSide{ to.m + op.m, to.c + op.c }
        nextState.right = RiverSide{ from.m - op.m, from.c - op.c }
    }

    ok = valid(nextState)

    return
}

3.7 解を得るアルゴリズムを書く

 3.6 までに書いた構造体や関数を使って、解を得るアルゴリズムを書いていきます。
なお、これから示すコードは、

func main() {

}

の中に書いていくものとします。
 

3.7.1 得られた解を保存しておくオペレータのスライス

 以下のように、空のスライスを用意しておきます。

solution := []Operator{}

 

3.7.2 探索時に一度たどった状態を記録しておくマップ

 Stateをキーとして boolを値とするマップで、一度たどったStateを記録するものとします。

history := map[State]bool{ initialState: true }

 
  Go の構造体は、そのすべてのフィールドが比較可能であれば、その構造体自体も比較可能です。これに沿えば、先に定義したRiverSideは比較可能であり、したがってStateも比較可能なので、(JAVAの equals()メソッドのような同値メソッドを別途作らなくても)そのままマップのキーに使える。これはなかなかイイ。
 

3.7.3 与えられた状態から目標状態に到達する解を探す関数

 これを書くのが、冒頭の 1.背景 に書いた、そもそもの動機でした。
色々な書き方があると思いますが、以下のようにしてみました。

探索関数(クロージャ)
    var solve func(currentState State) bool

    solve = func(currentState State) bool {

        // もし、currentStateが目標状態と等しいなら、trueを返す。
        if currentState == goalState {
            return true
        }

        // 深さ優先探索(Depth-first search)で目標状態に至る解を探す。
        for _, op := range Operators {
            if nextState, ok := stateTransition(currentState, op); ok {
                if !history[nextState] {
                    history[nextState] = true
                    solution = append(solution, op)
                    if solve(nextState) {
                        return true
                    } else {
                        solution = solution[0 : len(solution)-1]
                    }
                }
            }
        }
        return false
    }

   ところで、上記の

    var solve func(currentState State) bool

    solve = func(currentState State) bool {
        // 関数本体・・・
    }
      

 のところは、なんとなく冗長に思えて、一行で

    var solve = func(currentState State) bool {
        // 関数本体・・・
    }

 と書けたら、ちょっとうれしいのだけれど、このように書いて実行すると、

undefined: solve

 と叱られますね。

3.7.4 結果の出力

 もし、solve が問題を解くことができたら、解となるOperatorの列を保存してある
solutionを表示するようにします。

    if solve(initialState) {
        fmt.Printf("%+v\n", solution)
    }

4. 実行結果と解になっていることの確認

 以下は、上記のコードをGoファイル main.goに保存して、実行してみたところです。

$ go version
go version go1.9.2 darwin/amd64
$ go run main.go
[{m:1 c:1} {m:1 c:0} {m:0 c:2} {m:0 c:1} {m:2 c:0} {m:1 c:1} {m:2 c:0} {m:0 c:1} {m:0 c:2} {m:1 c:0} {m:1 c:1}]

 解として表示された、Operator のスライス [{m:1 c:1} ・・・ ] が本当に正解になっているかは、
手作業で絵を描いていけば確認できます。
 あるいは、Wikipedia Missionaries_and_cannibals_problem  のページ中ほどの右側に出ている、解を図示したものと、上記のOperatorのスライス内容とが同じになっていることでも確認できます。
(図のキャプションには、Graphic of solution to Jealous Husbands River Crossing Problem とありますが
実質、同じことを問う問題です。)

5. ソースコード

 
  今回書いたソースコードは、以下

 https://github.com/jun68ykt/m-and-c

 に上げておきましたので、この手の問題がお好きな方はご自由に手を入れて頂き、
 たとえば
 「深さ優先探索ではなく、幅優先探索にしてやんよ」
 みたいな感じで遊んでみてください。

脚注

※1:第5世代コンピュータ
 このプロジェクトがどういうもので、予算規模はどのくらいで、結果としてどういう経緯をたどったのかについては、池田信夫氏のブログエントリ「第5世代コンピュータ」の解説が分かりやすい。

※2:それ関係の書籍
 うろ覚えだが、その本はDEC-10 Prologの開発者R・コワルスキによる Logic for Problem Solvingの訳本「論理による問題の解法」培風館(1987/3/1) だった気がする。あ、いや。違うかもしれない。この本に出ていたのは、15パズルか、あるいはハノイの塔だったかもしれない。忘れた。なにせ、この本を修論のための副読本として読んだのは、四半世紀あまり昔の話だ。

 

jun68ykt
ときどき teratail で回答してます。
https://teratail.com/users/jun68ykt
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした