直大2012.09.04コピーしましたPRアルゴリズムと聞いて、何を思い浮かべますか。この連載では、「アルゴリズム」を、具体的な問題に対して適用していく際の考え方を紹介します。今回は「川渡り問題」について解説します。例題33人の宣教師(うち2人は子供)と3人の先住民(同)が川岸にいます。川には2人まで乗れるボートが一艘(そう)あります。ボートを漕げるのは、大人だけで、子供はボートを漕ぐことが出来ません。どちらかの岸で、先住民の数が宣教師の数より多くなると、先住民は反旗を翻して宣教師に襲いかかってしまいます。全員が無事に対岸に渡るには、どうしたら良いでしょうか?これは有名な川渡り問題です。この問題をグラフに変換することはできたでしょうか?もしできなくても、あまり気にすることはありません。この特別連載を読み終えるころには、あなたは幅優先探索を十分に使いこなせるようになっているはずです。解き方が思いつかないときは、コンピュータを使わずに解くなら、どのように解いていくかを考えることが一番です。最初の状態を図にしてみます。宣教師(赤)が3人、先住民(青)が3人、同じ川岸に居て、同じ岸にボートがあるという状態です(図9)。図10●大人の先住民と子供の宣教師が左岸に渡った図11●大人の先住民が右岸に渡った。右岸で先住民の数が宣教師の数より多くなるのでNG!次に、ボートで対岸に渡ってみましょう。ボートに乗る組み合わせにはいろいろあります。ここでは取りあえず、大人の先住民と子供の宣教師を乗せて移動させてみます(図10)。続いて、ボートを元の岸に移動させます。このとき2人でボートに乗って戻ると前と同じ状態になってしまいます。無限ループに陥るのを防ぐため、どちらか1人だけが戻るのですが、ボートを漕げるのは大人だけなので大人の先住民が戻ります。この移動後、右岸が、先住民3人、宣教師2人になってしまい(図11)、先住民が宣教師に襲いかかってしまいます。従って、大人の先住民と子供の宣教師を最初に対岸に渡らせるのはだめであることがわかります。そこで、改めて最初の状態に戻って、別の組み合わせを試していく、...といった具合です。ここまで読んで、問題をどのようにグラフとして表せばいいのか、なんとなく想像がついたのではないでしょうか。「誰がどちらの岸にいて、ボートがどちらの岸にあるのか」といった状態を頂点として、その状態から1回のボートの移動で遷移できる状態を辺でつないだグラフを作れば良いのです(図12)。図12●川渡り問題を幅優先探索で解く際に用いるグラフグラフが作れてしまえば、あとは幅優先探索を行うだけです。答え(全員が無事に対岸に渡った状態)を見つけたら、そこから初期状態に向かって逆にたどれば、ボートでどのように移動させたかがわかります。現場の負担軽減を!医療界でのAWS活用法500万社が導入。情報銀行の成り立ち、事例、現状課題やその行方を網羅。経営戦略である以上、「会計」の知識やスキルが欠かせません。