08-1-037-0022 奥川史樹情報論理工学研究室       背景問題提起研究内容結果考察今後の課題  モンテカルロ法 ◦ 活用分野  金融  科学  ゲームの解探索    非常に便利！簡単なシミュレーションのみ！組み合わせ最適解問題に対して近似最適解を求められる  バックトラック法 ◦ 探索範囲が大きく最後まで調べられない・・・ゲーム途中での最適解ここまで  モンテカルロ法 ◦ 最後まで調べることができるそこから最適解最後まで  囲碁や将棋で最善手を探索する方法  ある局面において、最善手が複数存在する場合、どの程度の最善手を調べられているのか？  複数の最適解が存在する場合、探索能力はどの程度か？  複数の最適解をもつ問題 ◦ NQueen問題をとりあげる  Nが大きくなると解の数が爆発的に増える Nの数全解数 4 2 5 10 6 4 7 40 8 92 9 352 10 724    ランダムに駒を配置判定繰り返す   N=8の場合シミュレート回数50万試行回数1000回 ◦ 発見できた最適解  0~2個  あまり発見できなかった  解の探索能力を向上させるため探索範囲を狭めることが考えられる部分解合成法を用いる  部分解を合成し全体解を作成する分割統治法の一種  解の探索範囲を分割することで問題空間を縮小できる  参考文献 ◦ 萩野谷一二, “NQueen問題への新しいアプローチ(部分解合成法)について,” 情報処理学会報告書, Vol.2011-GI-26, No.11, 2011.   NQueen問題の解は反転回転して別解を求めることができる NQueenの解には3つのパターンがある ◦ TypeA ◦ TypeB ◦ TypeC 対称性なし 180°の対称性 90°の対称性  回転、反転操作により7 個の別解がある  回転、反転操作により3 個の別解がある  反転操作により1個の別解がある     シミュレート回数50万試行回数1000回 N=8の場合 0~2 → 全92解すべての解を求めることができた N=10の場合 0 → 644~660  改善点 ◦ 解の生成数増加  問題点 ◦ シミュレーションにかかる時間の増加  従来のモンテカルロ法を上回る解探索を実現  バックトラック法と比べると… ◦ 別の最適解が発生する可能性 →単純比較はできない  並列化による高速化  奇数の問題サイズを扱えるように  部分解を更に細分化する  ご清聴ありがとうございました。