第2回川渡り問題

高橋　直大

2012.09.04

　アルゴリズムと聞いて、何を思い浮かべますか。「実際にプログラミングを行う上では何に役立つかよくわからない」と感じている方もおられるのではないでしょうか？この連載では、「アルゴリズム」を、具体的な問題に対して適用していく際の考え方を紹介します。今回は「川渡り問題」について解説します。

例題3

3人の宣教師（うち2人は子供）と3人の先住民（同）が川岸にいます。川には2人まで乗れるボートが一艘（そう）あります。ボートを漕げるのは、大人だけで、子供はボートを漕ぐことが出来ません。また、どちらかの岸で、先住民の数が宣教師の数より多くなると、先住民は反旗を翻して宣教師に襲いかかってしまいます。全員が無事に対岸に渡るには、どうしたら良いでしょうか？

　これは有名な川渡り問題です。これまでの解説を読んだ上でこの問題を見て、この問題をどう解いていくか想像がついたでしょうか？　この問題をグラフに変換することはできたでしょうか？

　もしできなくても、あまり気にすることはありません。この特別連載を読み終えるころには、あなたは幅優先探索を十分に使いこなせるようになっているはずです。

　解き方が思いつかないときは、コンピュータを使わずに解くなら、どのように解いていくかを考えることが一番です。まず、最初の状態を図にしてみます。宣教師（赤）が3人、先住民（青）が3人、同じ川岸に居て、同じ岸にボートがあるという状態です（図9）。

図9●川渡り問題の初期状態

図10●大人の先住民と子供の宣教師が左岸に渡った

図11●大人の先住民が右岸に渡った。右岸で先住民の数が宣教師の数より多くなるのでNG！

　次に、ボートで対岸に渡ってみましょう。ボートに乗る組み合わせにはいろいろあります。ここでは取りあえず、大人の先住民と子供の宣教師を乗せて移動させてみます（図10）。続いて、ボートを元の岸に移動させます。このとき2人でボートに乗って戻ると前と同じ状態になってしまいます。無限ループに陥るのを防ぐため、どちらか1人だけが戻るのですが、ボートを漕げるのは大人だけなので大人の先住民が戻ります。

　この移動後、右岸が、先住民3人、宣教師2人になってしまい（図11）、先住民が宣教師に襲いかかってしまいます。従って、大人の先住民と子供の宣教師を最初に対岸に渡らせるのはだめであることがわかります。そこで、改めて最初の状態に戻って、別の組み合わせを試していく、…といった具合です。

　さて、ここまで読んで、問題をどのようにグラフとして表せばいいのか、なんとなく想像がついたのではないでしょうか。「誰がどちらの岸にいて、ボートがどちらの岸にあるのか」といった状態を頂点として、その状態から1回のボートの移動で遷移できる状態を辺でつないだグラフを作れば良いのです（図12）。