• BPnet
  • ビジネス
  • IT
  • テクノロジー
  • 医療
  • 建設・不動産
  • TRENDY
  • WOMAN
  • ショッピング
  • 転職
  • ナショジオ
  • 日経電子版
  • PR

  • PR

  • PR

  • PR

  • PR

高橋 直大 2012/09/04 日経ソフトウエア
出典:日経ソフトウエア 2012年7月号
(記事は執筆時の情報に基づいており、現在では異なる場合があります)
目次一覧

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

例題3

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

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

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

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

図9●川渡り問題の初期状態
図9●川渡り問題の初期状態
図10●大人の先住民と子供の宣教師が左岸に渡った
図10●大人の先住民と子供の宣教師が左岸に渡った
図11●大人の先住民が右岸に渡った。右岸で先住民の数が宣教師の数より多くなるのでNG!
図11●大人の先住民が右岸に渡った。右岸で先住民の数が宣教師の数より多くなるのでNG!

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

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

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

図12●川渡り問題を幅優先探索で解く際に用いるグラフ
図12●川渡り問題を幅優先探索で解く際に用いるグラフ

 グラフが作れてしまえば、あとは幅優先探索を行うだけです。答え(全員が無事に対岸に渡った状態)を見つけたら、そこから初期状態に向かって逆にたどれば、ボートでどのように移動させたかがわかります。

ここから先はITpro会員(無料)の登録が必要です。

次ページ 実装を考える
  • 1
  • 2

あなたにお薦め

連載新着

連載目次を見る

今のおすすめ記事

  • 【夏休みスペシャル 2017】

    屋内トレで夏を乗り切る、無料ヨガアプリの実力

     いよいよ夏休み。ひと息ついて、秋から年末にかけての忙しい時期に備えて、エネルギーチャージをしておきたいところだ。それに向けて大事になってくるのが、体のメンテナンスである。そこで今回は、ストレッチやヨガを自宅で実施するための無料iPhoneアプリから、3つを厳選して紹介したい。

ITpro SPECIALPR

経営

アプリケーション/DB/ミドルウエア

クラウド

運用管理

設計/開発

サーバー/ストレージ

ネットワーク/通信サービス

セキュリティ

もっと見る