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）を表す。
なお上記の図で、矢印の先に「ボートを使って何往復かして、全員が向こう岸に行きたい。」と書いて
あるけれども、「何往復」というのは間違いで、正しくは「ボートを使って何回か行き来して、全員が
向こう岸に行きたい。」です。なぜなら最後に片道一回が必ずあるからです。
以下、説明の便宜上、最初に6人がいる方の岸を、上の図にそって左岸といい、
渡って行きたいほうの岸を右岸という。
(3) 何回かボートを往復（＋最後の片道一回）させて、彼らは右岸に渡ろうとするが、
注意しなければならないのは、
左岸、右岸どちらにおいても、もし、人食い人種の人数のほうが宣教師の人数よりも多くなると、
宣教師は人食い人種に食われてしまう
ということ。
例えば、上記(2)の初期状態から、宣教師2名がボートに乗って右岸に行こうとすると、
左岸において、宣教師が1人、人食い人種が3人の状況になり、左岸で一人残された宣教師は
人食い人種に食われてしまう。以下の図では、左岸の宣教師が、3人の人食い人種に襲われて
食われてしまうことを表している。
もうひとつの例として、以下のような状態の場合を考える。
このときに、もし次に右岸から人食い人種が1人だけでボートに乗って、左岸に行ったとする。
すると、ボートが左岸に着いて、乗っていた人食い人種が岸に降りたとき、左岸では
人食い人種が2人、宣教師が1人になり、人食い人種のほうが多いので宣教師が襲われる。
このように、ボートに乗った宣教師も人食い人種も、川を渡りきったら、いったんは
全員がボートから降りて、降りた状態での人数によって、人食い人種が宣教師を襲うか
どうかを判定するものとする。（つまり、ボートに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"
}
フィールド変数が何を表すかというと、
-
leftとrightは、それぞれ左岸、右岸を表します。 -
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は、いかなる状態でも、両岸の宣教師、人食い人種を表す m と c は負数に
なってはならないという自明な制約を表しています。
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 = ¤tState.left, ¤tState.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 = ¤tState.right, ¤tState.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パズルか、あるいはハノイの塔だったかもしれない。忘れた。なにせ、この本を修論のための副読本として読んだのは、四半世紀あまり昔の話だ。