DevQuiz 2011
今年もDevQuizに参加しました。スライドパズルはいい問題でした。去年よりも盛り上がっていたように思います。 スライドパズルの結果は 4969/5000 残り31問で時間切れ。壁の本当の難しさに気づくことが遅れてしまったのが敗因です。 以下，考えたこと等をメモしておきます。 基本的な考え方は，盤面をノードとしたグラフの探索で良いはず。 ノード数は，6x6のボードで36! 不可能な盤面もあるので 36!/2 かも。どちらにしても広大な探索空間となることは間違いない。 いかに沢山の探索をこなせるかと，無駄な探索を排除できるかがカギになるはず。 とりあえず，参考文献をあたる。手元の「アルゴリズムクイックリファレンス」に，ずばりそのものスライドパズルが扱われている。 グラフの探索はA*で良さそうだ。 とりあえず，ヒューリスティック関数はマンハッタン距離(MD)で試してみる。h*=MD×2でサクサ
超覚えやすいグラフの探査アルゴリズム
グラフの経路探査で有名なダイクストラ法，A*探索を深さ優先探索(DFS)・幅優先探索(BFS)とのアナロジーで理解できることに気づきました。これを覚えておけば，スクラッチから何も参照せずにダイクストラ法，A*探索のコードを書けるようになります。 (以下の説明は，ある程度アルゴリズムを理解していることを前提としています。「超分かりやすい」でない点に注意ください) グラフ探査の抽象化コードグラフ探査を抽象化したコード(C++風擬似コード)は次のようになります。 Search() { Container que; // 抽象コンテナ ･･･(1) // スタート地点をキューに入れる Vertex s(スタート地点); que.push(s); while( !que.empty() ){ Vertex v = que.pop(); if( isGoal(v) ) // ゴールに到達したら終了 r
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
