制約充足問題における体系的探索手法の効率化についての検討
スポンサーリンク
概要
- 論文の詳細を見る
制約充足問題は人工知能や画像解析の分野をはじめ、グラフの問題やパズルなどの探索問題、いわゆる組み合わせ問題を対象として研究がおこなわれている。制約充足問題とは、変数の有限集合および各変数に対応する離散値の有限集合のドメインから値を選択し、すべての制約を満足するように各変数に対して値を割り当てる問題である。制約とは適用対象の構成要素およびその属性間で成立する関係を宣言的に記述したものである。 制約充足問題における従来の解法としては、バックトラックを基本とした探索による方法や整合化手法などに代表される前処理を用いる方法が代表的である。この場合には、解法としては探索空間の全域を対象としてすべての可能性を探索するもので、アルゴリズムの完全性を保証している。完全性とは、探索空間に解が存在すれば、必ず見つけられることと、解がなければ必ず存在しないことを保証するものである。 このような体系的探索法を用いる解法では、生成検査法やバックトラック法などに基づき解が求められる。特に、すべての解を求める場合には、探索木全体の探査が要求される。バックトラックに基づいた探索では、無駄なバックトラックが頻発してしまい効率が悪い。特に、全解を求めたい場合には、探索木全体をたどることになってしまうので、無駄な分岐を避けることが望ましい。 本論文では、まず、バックトラックによる効率改善手法として、知的バックトラックの一種であるバックジャンピングやバックトラックと整合化手法を組み合わせたフォワードチェッキングといった無駄な探索枝を刈り込む手法について説明する。次に、制約充足問題の代表例である地図の色塗り問題へ適用し、その結果について示す。
- 東京情報大学の論文
- 2005-02-28
著者
関連論文
- D-8-13 ベイジアンフィルタを利用したWeb 推薦システムの試作と評価(D-8. 人工知能と知識処理,一般セッション)
- F-029 ベイジアンフィルタを利用したWeb推薦システム(人工知能・ゲーム,一般論文)
- ベイジアンフィルタを利用したWebページランキングシステムの提案とADMによる評価
- 適合率と再現率を用いたWebページランキングシステムの性能評価
- ベイジアンフィルタを利用したWebページランキングシステム(社会システムと情報技術研究ウィーク)
- O-004 ニューラルネットワークを用いたTUR-BT術後の膀胱癌の再発予測(情報システム,一般論文)
- F-032 対戦型ビデオゲーム用ゲームAIにおけるチューリングテストの有効性検証(F分野:人工知能・ゲーム,一般論文)
- A-030 摂動を用いた近傍解を記録した評価表に基づく局所探索手法の提案(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- O-030 アンサンブル学習型ニューラルネットワークを用いた衛星画像の水田抽出モデル(O分野:情報システム,一般論文)
- F-046 コストの変動する重み付きグラフにおけるヒューリスティック経路探索手法の評価(F分野:人工知能・ゲーム,一般論文)
- M-004 異なるソーシャルネットワークサービスにおける統一的なタグを利用したフレームワークの評価(ユビキタス・モバイルコンピューティング,一般論文)
- F-051 クラスタリング手法を用いたソーシャルブックマークからの時間的変化の抽出(人工知能・ゲーム,一般論文)
- F-004 コストの変動する重み付きグラフにおける経路探索の為のグラフ分割手法の提案(人工知能・ゲーム,一般論文)
- O-009 看護計画作成業務の分析(情報システム,一般論文)
- B-023 エージェント向け探索ライブラリ : 遺伝的アルゴリズムおよびニューラルネットワークの実装報告(ソフトウェア,一般論文)
- 5G-3 オブジェクト指向プログラムの静的・動的側面を視覚化するプログラミング教育支援システム(プログラミング教育,一般セッション,コンピュータと人間社会)
- D-15-7 オブジェクト指向プログラム視覚化教育システムにおけるデザインパターンの視覚化サポート(D-15.教育工学,一般セッション)
- D-15-26 オブジェクト指向プログラムの視覚化によるプログラミング教育システムの改良(D-15.教育工学,一般セッション)
- 5G-4 オブジェクト指向教育のためのモデリングならびにプログラミング教材の検討(プログラミング教育,一般セッション,コンピュータと人間社会)
- D-15-6 オブジェクト指向ソフトウエア教育のためのモデリング教材の検討(D-15.教育工学,一般セッション)
- オブジェクト指向プログラムの静的・動的側面を視覚化するプログラミング教育支援システム
- D-15-33 オブジェクト指向プログラムの視覚化によるプログラミング教育システム(D-15. 教育工学,一般セッション)
- コストの変動するグラフにおける経路探索手法:AntNetの適用と改良
- 情報視覚化を活用したオブジェクト指向プログラミング教育支援システムの提案(エンタテインメントを活用した学習環境/一般)
- D-15-25 モデリングを考慮したソフトウエア教育のためのオブジェクト指向プログラミング教材の検討(D-15.教育工学,一般セッション)
- D-15-34 ソフトウエア教育のためのオブジェクト指向モデリングならびにプログラミング教材の検討(D-15. 教育工学,一般セッション)
- 制約充足問題への近似解法の適用検討 -N-クイーン問題を中心として-
- Particle Swarm Optimizationによる転移学習を適用した衛星画像の類似画像検索
- モバイルエージェントのためのセキュリティ機能についての検討
- 離散組み合わせ問題の制約充足問題による定式化ならびに整合化手法の適用検討
- 項書き換え系に基づく制約プログラミング言語システムの実現方式について
- チューリングテストによるゲームAIの客観的評価
- 多様な学習形態を可能とするLED照明向けプログラミング教材の開発
- 制約充足問題における体系的探索手法の効率化についての検討
- ルーチン設計問題向け知識システムへの制御指向技術の適用についての検討
- 制約論理型言語のための制約集合の依存性解析手法の制約アプリケーションへの適用
- 制約論理型言語における制約集合の構造解析による代数制約ソルバーの効率化についての検討
- 探索解の広範囲分布を維持するParticle Swarm Optimizationの提案と評価
- 項書き換え系に基づく制約プログラミング言語システムの実現方式について
- F-044 ゲームAIにおけるチューリングテストの適用評価(学習とゲーム,F分野:人工知能・ゲーム)
- F-025 動的問題のためのParticle Swarm Optimizationにおける共生モデルの適用(複雑系及び一般,F分野:人工知能・ゲーム)
- Eclipseを用いたオブジェクト指向プログラミング教育支援視覚化システムの設計と実装(学習データの蓄積と利活用支援/一般)
- D-15-11 受講者対応支援システムにおける教員のためのタスク割り当て(D-15.教育工学)
- F-005 Support Vector Machineによるジャイロセンサー搭載車両の路線分類(F分野:人工知能・ゲーム)