Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

DevQuiz 2011

今年もDevQuizに参加しました。スライドパズルはいい問題でした。去年よりも盛り上がっていたように思います。

スライドパズルの結果は 4969/5000 残り31問で時間切れ。壁の本当の難しさに気づくことが遅れてしまったのが敗因です。DevQuiz2011


以下,考えたこと等をメモしておきます。

  • 基本的な考え方は,盤面をノードとしたグラフの探索で良いはず。
  • ノード数は,6x6のボードで36! 不可能な盤面もあるので 36!/2 かも。どちらにしても広大な探索空間となることは間違いない。
  • いかに沢山の探索をこなせるかと,無駄な探索を排除できるかがカギになるはず。
  • とりあえず,参考文献をあたる。手元の「アルゴリズムクイックリファレンス」に,ずばりそのものスライドパズルが扱われている。
  • グラフの探索はA*で良さそうだ。
  • とりあえず,ヒューリスティック関数はマンハッタン距離(MD)で試してみる。h*=MD×2でサクサクと解ける(もちろん解けない問題も多くある)。
  • 他も調査。下記のサイトが参考になりそう。
        15パズル自動解答プログラムの作り方
  • 反復深化(IDDFS,IDA*)という考え方があるらしい。 前述の参考書にもキーワードはあった。
  • 反復深化は評価値の閾値を変えながら何度も探索を実行するものらしい。
    • (理解が浅いだけかもしれないが)反復の度に同じ探索をやり直すので非効率では?
    • 局面数が多いので,いかに探索数を減らす or 多種の探索を行うかが至上命題。
    • 直前反復での閾値の際の局面を保存しておいて,次の反復はそこから始めれば速いかも?
      => これって A* そのものと変わらない気が・・・
    • 反復深化は,BFS,A*ではキューに溜めている局面情報を毎回探索基点からの探索を繰り返すことでオンデマンドに求めているものと考えればよいらしい。
    • 探索空間が大きい場合にはあまり実用的ではないような気がするので,今回の問題への適用はパスする。
  • とはいっても,単純にA*を用いてはメモリが足りなくなるのは明らか。
  • A*において評価値が悪い局面は,後で評価される(プライオリティキューの上位に浮上する)可能性が低いように思う。
  • スライドパズルはどちらかといえばグリーディな感じで手順が決まりそうで,一旦極端に評価値の悪い局面を経由しての最短手順はあり得そうにない。
  • プライオリティキューに最大サイズを設け,溢れた局面(悪い局面)は捨て去ることとする。
  • 忘却型プライオリティキューは set (STL)で簡単に実装できる。(処理効率には目を瞑る)
  • MDでは,壁に囲まれる部位で不利な方にタイルを動かしても評価値が向上してしまう。
    => 各点間の最短パスを事前に計算しておいて,その距離を評価値として用いることとする。
  • 他に評価値はないか? => 実際にスライドパズルで遊ぶ。
  • 自分が置かれる行,列で他のコマと順序が入れ替わっているケースは余計に手数がかかる。例えば,「12435」のようなケース。
    => このときは評価値+2としよう。
  • ヒューリスティック関数が「h* < 実際の残り手数」であれば,最短性が保障される。しかしながら,可能性のある盤面を丁寧に探しに行ってしまうので,探索時間が多くかかる。逆に「h*>実際の残り手数」であれば,最短性を犠牲にして評価値の良い局面をグリーディ的に探しに行くので早く解を見つけられる。
    => 探索時間のかかる問題は評価関数の係数を増やして求めていくこととしよう。
  • ゴール状態から逆向きに探索した状態を列挙しておいて,それらをゴールとすると効率が良さそう。
  • ゴールまで16手程度であれば,メモリ上に局面状態を展開できる。
  • これで,4750問程度
  • 現状,局面の探索では1手前の局面へ戻ることだけを抑止している。解けてない問題は,どこかでループが発生しているのかもしれない。
    => 探索先の局面でプライオリティキューにある局面へは(再)訪問しないようにしてみる。
        (キューには2百万局面保存)
  • これで,4830問
  • 解けない問題をトレース出力。壁が通路となっている問題が解けていないようだ。
  • 通路の場合,そこに入るタイルを連ねて移動させなければならない。
  • 評価関数に,各タイルの相対距離を使ってみよう。隣合うタイルが近くにあるほど評価値がよくなる。
  • これで,4969問。ここで時間切れ。残り31問なのが悔しい。

提出版のソースは下記の通りです。

続きを読む
スポンサーサイト

GDD2010 DevQuiz

会社の同僚に誘われてDevQuizに参加してみました。

Google Maps API

Google Maps APIのコードはJavaScriptという点がハードルでしたが,リファレンスを見ながらどうにかしました。
      「とほほのJavaScriptリファレンス

設問は最大で10地点の巡回セールスマン問題なので,解法は総当りで。順列の生成が必要となりますが,C++ではないのでnext_permutation()が使えない・・・ということで検索。
      「C#でSTLのnext_permutation的なものを

ラウンド2のもう一方の選択問題「2-legged OAuth」は,Rubyでやろうと「初めてのRuby」を買ってまで意気込んでいたのですが,結局は時間がとれずパスとなりました。後で読んでおこう。

Shiritori

単語セットが与えられた「しりとり」ゲーム。player側とcpu側の選択パターンをツリーで表せばOK。ツリーを辿るのはAND/OR木の考え方になります。辿るパスは,CPUの選択は全て負けパターン(AND),Playerの選択は一つでも勝ちがあればよい(OR)ことになります。

ツリーは,再帰を使ってこんな感じで。(実行効率は考慮せず)

int tree( set& words, char head, int bCPU )
{
    set selectable;
    set::iterator it;

    // next selection
    for( it = words.begin(); it != words.end(); it++ ){
        if( (*it)[0] == head ){
            selectable.insert(*it);
        }
    }
    if( selectable.empty() ){
        return bCPU;
    }

    int ret;
    int i = 0;
    for( it = selectable.begin(); it != selectable.end(); it++ ){
        char tail = (*it)[it->size()-1];
        words.erase(*it);
        ret = tree( words, tail, 1-bCPU );
        words.insert(*it);
        if( bCPU ){
            if( ret == 0 ) // 一つでも0なら0を返す
                return 0;
        }else{
            if( ret == 1 ) // 一つでも1なら1を返す
                return 1;
        }
        i++;
    }
    return bCPU;
}

単語セットが多い小問3はツリーが大きくなりすぎるため(処理が終わらない),twitterで流れていたこの論文を参照し,先頭文字と終端文字が巡回しているペア(例 axxxxb,bxxxa)を削除しました。
これだけで大きく処理時間が改善しました。設問の趣旨としてこの事に気づけるかが含まれていたのではないかなとも思います。

PAC-MAN

今回の一番の難敵であったPAC-MANは,Mrathon Match的な問題でかなり楽しめました。拠り所とした解法の考え方があまり宜しくなかったため,結果はあまり振るわず「41.0, 174.0, 358.0」でした。twitterを見てると,小問2は200点,小問3は500点越えが標準な感じで,若干敗北感が・・・

本問はプログラムで自動で解くものだろうと思い込んでましたが,期間途中で「手動による解法でも良い」と公式アナウンスが入り,若干気抜け。「Super Hacker」という名前であれば,自動解法に拘って欲しかったなぁと思います。例えば,Marathon Mathch的にサーバ側で隠された評価用問題を実行して得点を出すなど。

解法としては,局面の探索問題であるためDFSかBFSを基に考えることとしました。敵が移動することで局面の数が膨大となるため,BFSではメモリが足りなくなることは容易に想像つきます(ちょっと試してみましたが,すごい勢いでメモリ使用量が増えていきます)。そんなわけでDFSで進めます。

さらに局面を減らすため(これがまずかったのですが・・・),局面を自機が交差点にいる点だけに絞り込みました。通路では,次の交差点を一目散に目指す形となります。後ほど,手動で試して分かったことですが,敵V,Hを誘導するために通路では行ったり来たり・停止する等のトリッキーな動きが必要なようでした。

局面の数が膨大なためDFSでも全探索は無理だろうと,交差点で行き先の優先順位を決めて,良さそうな手から探索することとしています。(貪欲アルゴリズムで突き進み,ダメだったときに一手戻るという形です)

評価関数は次のような形にしてみました。(かなり場当たり的ですが)

int evaluate(移動先交差点)
{
    bonus = 0;
    if( ここまでの移動が初訪問 ){
        if(ここからの通路に未訪問が残っている)
            bonus = 100;
        eval = 0x40000000 + 交差点番号 + bonus;
    }else{
        moves    = 未訪問が残る通路への移動手数(何交差点先か)。 // 15手先まで見る
        dot_path = moves手先の交差点で,未訪問通路の数
        if(2手以内の範囲で,未訪問通路が単独で存在する)
            bonus = 100;
        eval = (1 << (15-moves)) + dot_path + bonus + 交差点番号*3;
    }
    return eval;
}

未訪問通路の通過が評価値最大,訪問済み通路の場合はここから周辺の未訪問通路への移動手数が少ない方が評価値大となります。交差点番号は,左上を0とし右下へ行くほど増える値です。行ったり来たりを繰り返さないように,右下方向を優先させるバイアスをかけてみました。

最終的には,小問1は手動で解いてしまい,小問2は自動,小問3は1個目の行き止まりまでは手動(50手弱)でその後は自動という半手動の形でやってみました。

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。