Chokudai search
- 2. Chokudai searchとは？ ? Beam searchの亜種 ? Colunさんに名前つけろって言われたから 適当に付けた – ぶっちゃけ名前つけるほどのアルゴリズム じゃないと思う – なんか名前あったらおしえてください
- 3. Beam search ? 幅優先探索の各階層において、評価が良 い順にd個のみを採用していく – この際のdをビーム幅と呼ぶ D=3のサンプル 4番以下からの頂点からは 探索を行わない ８ ７ ７ ９ ８ ７ ７ ７ ６ ８ ８ ８ ８ ８ ７ ６ ６ ３ ２ ７ ６ ４ ４ ３ ２
- 4. Beam search ? 幅優先探索の各階層において、評価が良 い順にd個のみを採用していく – この際のdをビーム幅と呼ぶ ８ ７ ７ ９ ８ ７ ７ ７ ６ ８ ８ ８ ８ ８ ７ ６ ６ ３ ２ ７ ６ ４ ４ ３ ２ D=3のサンプル 4番以下からの頂点からは 探索を行わない ビーム っぽい！
- 5. Chokudai search ? Beam Searchのビーム幅を小さく設定し、 反復しながら徐々にビーム幅を広げてい く ? こんな見た目なので昔はRainbow searchって呼んで た ８ ７ ７ ９ ８ ７ ３ ８ ７ ２ ８ ８ １ ８ ８ ６ ６ ６ ２ ８ ７ ７ ６ ３ ２
- 7. メリット ? 時間管理が極めて容易 ? 評価コスト０で多様性を生みやすい – スコアの安定性が生まれやすい
- 8. 時間管理 ? ビーム幅の厳密な設定が不要 – 時間いっぱいまで増やしていけばいいだけ ? 終了ターン数が解らない問題の場合も、 とりあえずの解がさっさと出るので予測 しやすい
- 10. デメリット ? メモリたくさん使う – 次の階層に移っても、前の結果を残さないと いけない ? 順位管理を動的にしないといけない – ビームサーチだと１回のソートで十分。大抵 は優先度付きキューで事足りるけど、ヒュー リスティックな枝刈入れたりすると大変 ? 上手いこと多様性生かせないと評価値低 いの選んでるだけになっちゃう