制約充足問題の解探索アルゴリズムおよび効率評価に関する研究(問題解決手法)(<特集>人工知能分野における博士論文)
スポンサーリンク
概要
- 論文の詳細を見る
制約充足問題(CSP)は, 新しい知識表現のモデルおよび問題解決の方法として人工知能やパターン解析など幅広い分野に応用されている基盤的技術である.本論文は, CSPの解探索アルゴリズムの開発および効率評価について論じたものであり, 6章からなる.第1章の序論に続いて, 第2章では, 研究分野の概要として, CSPの定義, 従来より研究されている解探索アルゴリズム, およびCSPの相転移現象について概説している.第3章では, CSPの解探索効率が極端に低下してしまういわゆる相転移現象について, その発生原因を問題の制約構造に注目して解析している.第4章では, 確率的解探索は局所最適解に捕捉される危険性があるという問題点に対して, 局所最適解に陥る可能性がある制約グラフの局所的構造を提示し, これが, 解探索効率, すなわち問題の難しさと相関があるということを示している.第5章では, 確率的解探索に関して, 局所最適解からの脱出のための新たなメタ戦略を提案している.具体的には代表的なメタ戦略の一つであるシミュレーテッドアニーリング(SA)の問題点である温度スケジューリングの困難さに注目して, 空間並列型のメタ戦略を提案している.また, 本戦略が, 相転移が発生する領域を解くのに手間のかかる難しい問題に対しても, 従来手法より効率的な解探索を行えているということを詳細な実験により示している.第6章の結論で研究結果をまとめ, 今後の課題について論じている.
- 社団法人人工知能学会の論文
- 2001-11-01
著者
関連論文
- 3V-1 マルチエージェント型交通シミュレータと歩行者エージェントの導入(マルチエージェント(1),学生セッション,人工知能と認知科学)
- 極小非可解構造に基づく3COLインスタンスの組織的生成(人工知能,認知科学)
- 制約充足問題の解探索アルゴリズムおよび効率評価に関する研究(問題解決手法)(人工知能分野における博士論文)