アルゴリズムと聞いて、何を思い浮かべますか。「実際にプログラミングを行う上では何に役立つかよくわからない」と感じている方もおられるのではないでしょうか? この連載では、「アルゴリズム」を、具体的な問題に対して適用していく際の考え方を紹介します。今回は「川渡り問題」について解説します。
例題3
これは有名な川渡り問題です。これまでの解説を読んだ上でこの問題を見て、この問題をどう解いていくか想像がついたでしょうか? この問題をグラフに変換することはできたでしょうか?
もしできなくても、あまり気にすることはありません。この特別連載を読み終えるころには、あなたは幅優先探索を十分に使いこなせるようになっているはずです。
解き方が思いつかないときは、コンピュータを使わずに解くなら、どのように解いていくかを考えることが一番です。まず、最初の状態を図にしてみます。宣教師(赤)が3人、先住民(青)が3人、同じ川岸に居て、同じ岸にボートがあるという状態です(図9)。
次に、ボートで対岸に渡ってみましょう。ボートに乗る組み合わせにはいろいろあります。ここでは取りあえず、大人の先住民と子供の宣教師を乗せて移動させてみます(図10)。続いて、ボートを元の岸に移動させます。このとき2人でボートに乗って戻ると前と同じ状態になってしまいます。無限ループに陥るのを防ぐため、どちらか1人だけが戻るのですが、ボートを漕げるのは大人だけなので大人の先住民が戻ります。
この移動後、右岸が、先住民3人、宣教師2人になってしまい(図11)、先住民が宣教師に襲いかかってしまいます。従って、大人の先住民と子供の宣教師を最初に対岸に渡らせるのはだめであることがわかります。そこで、改めて最初の状態に戻って、別の組み合わせを試していく、…といった具合です。
さて、ここまで読んで、問題をどのようにグラフとして表せばいいのか、なんとなく想像がついたのではないでしょうか。「誰がどちらの岸にいて、ボートがどちらの岸にあるのか」といった状態を頂点として、その状態から1回のボートの移動で遷移できる状態を辺でつないだグラフを作れば良いのです(図12)。
グラフが作れてしまえば、あとは幅優先探索を行うだけです。答え(全員が無事に対岸に渡った状態)を見つけたら、そこから初期状態に向かって逆にたどれば、ボートでどのように移動させたかがわかります。