トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター最強最速アルゴリズマー養成講座(2/4 ページ)

» 2010年02月06日 00時00分 公開
[高橋直大,ITmedia]

君は探索をイメージできているか? セルフチェック

 ここまで漠然と読み進めてきた方には、まだ探索のイメージが十分ではないかもしれません。そこで、実際どのようにグラフを構築して、どのように探索をすればよいかをイメージする実践的な機会を設けようと思います。

 以下では、少し抽象的な、探索で解決できるであろう練習問題を提示しました。これらに対して、どのようなグラフを構築すればよいか、どんな枝刈りができるのかを考えてみてください。もしあなたがプログラマーであれば、9問中5問程度はすぐにイメージできてほしいところです。もしこれがイメージできない場合、厳しい言い方となってしまいますが、非常に狭い世界に閉じこもって、プログラムが十分に組める“つもり”になってしまっているだけではないでしょうか?

  • 将棋盤と駒の状態が与えられる。5手以内の詰みがあるかを調べ、ある場合はそれの1つを出力しなさい。
  • 1から1000までの数字のうち、1つが答えとなっている数当てゲームがある。数字を入力すると、正解がその数より「大きい」「小さい」、または「正解」の3通りの出力が得られる。これを12回以内に確実に正解できるように補助をするプログラムを作りなさい。
  • 数独(ナンバープレース)が未完成な状態で与えられる。これを完成させるプログラムを作りなさい。
  • ある迷路が与えられた時、これに対する最短のゴールまでの経路を出力しなさい。
  • 3人の宣教師と、3人の先住民が川岸にいる。2人まで乗れるボートがあり、ボートをこげるのはある先住民1人と宣教師1人だけである。どちらかの岸で先住民が宣教師より多くなってしまうと、先住民が宣教師を襲ってしまう。無事全員で渡り切るにはどうすればよいかを出力しなさい。
  • 宝が無限にある宝島1つを含む島々と、それらをつなぐ崩れそうな橋がある。おのおのの橋の重量制限が与えられたとき、ある特定の島へ宝を持ち帰りたい時、最大幾つの重さまでの宝を持ち帰ることが可能か? ただし、宝を持ち帰れるのは1回までとする。
  • 50ほどの駅の時刻表が与えられる。出発する駅と目的の駅と出発時間が与えられたとき、最も高速に目的の駅に到着できる乗り継ぎ方を出力しなさい。
  • ある広場に、花が300本程度バラバラに植えられている。スプリンクラーを使うと、半径rの範囲の円に対して均一に水が撒けるものとする。おのおのの花の座標が与えられたとして、rを最小にしたい。この時、rの値とスプリンクラーの座標を出力しなさい。
  • 国語辞典が与えられる。プログラムを通してユーザーから日本語で話しかけられた時、最適な返答を返すプログラムを作りなさい。

 さて、幾つの問題に対してイメージできたでしょうか? ここではじっくりと考えてもらいたいため、あえて答えは明記しません。前半は簡単な問題が並んでいますが、後半になると慣れていない人には難しいかもしれません。ほかの問題に当たって慣れてきたころにでも、もう一度考えてみるのもよいでしょう。

 それでは、次のページから、今回のメインとなるTopCoderの問題に移りたいと思います。2回に渡って紹介した探索の考え方が身についていれば、恐れることもない問題です。ぜひ挑戦してみてください。

Copyright © ITmedia, Inc. All Rights Reserved.

注目のテーマ