制約充足問題の計算複雑さについて(1)
スポンサーリンク
概要
- 論文の詳細を見る
'制約充足問題'は,'整合ラベリング問題'ともいい,人工知能の各分野,とくに組合せ問題において注目されつつある.前者はCSP(Constraint Satisfaction Problem)と略称する.後者はCLP(Consistent Labeling Problem)と略称する.一般に,問題対象がなんであれ,それがいくつかの構成要素から成っていて,しかも,対象全体の性質が,構成要素間において成り立つ局所的条件,すなわち'制約(拘束とも.Constraint)'の集合によって定義できるような場合に適用することができる.例えば,連立方程式も,CSPと見なすことができるが,このとき各等式に現われる変数は局所的制約を受けているといえる.このように,CSPとして表現したり,CSPと見なしたりすることのできる問題は非常に多く見られる.CSPにおける制約は,知識と考えることができ,問題対象を過不足なく記述できることが要請される.任意のCSPは等価なPrologプログラムに機械的に変換することができるが,CSPの方がPrologや関数型言語よりさらに非手続き的性質が明瞭になっている.この点において,CSPが,将来、プログラミングやプランニングの問題に有力なパラダイムを提供する可能性があるものと期待される.そのためには,CSPに関して,(1)制約の表現のための記述言語の開発,(2)CSPアルゴリズムの開発と効率評価,(3)CSPの応用分野の開拓,の3つが不可避の課題である.最初の課題は,制約論理プログラミングの主要なテーマの一つである.CSPは基本的に,組合せ探索の問題であり,一般に,NP完全である.したがって,第2の課題については,現実の問題に適用可能なレベルを保ちつつ,より簡単なCSPの部分クラスを見いだしてゆくことが重要である.本稿は,この課題を考察し,計算複雑さに関する新しい結果について報告するものである.
- 一般社団法人情報処理学会の論文
- 1991-02-25
著者
関連論文
- 事例・ルール間変換による知識編成方式と日本語点字翻訳の分かち書き問題への適用
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- 知識べースに基づく対話型点字翻訳システム
- 筑波大学における電子図書館システムの実現と運用
- 時間変化する仮想都市における道路網の自動生成
- 図面理解システムにおける制約充足に基づくプロトタイピング
- グラフ3彩色問題におけるEHIの組織的生成(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
- 非常に難しいグラフ3彩色問題の組織的生成法と考察
- 事例ベース推論と制約充足に基づく室内レイアウト変更計画(自動推論 : 演繹, 帰納, モデル検査/生成, 仮説推論アブダクション, 論理プログラム, プランニング, 時相論理, etc.)
- 確率的制約充足アルゴリズムにおける局所最適構造
- 1N-3 制約充足問題における制約構造に注目した計算複雑さの考察
- 制約充足問題研究支援システム
- 併合法による制約充足の並列化効果について
- FFDを用いた3次元足部モデルの解剖学的特徴点抽出(コンピュータグラフィックス)
- 確率的制約充足アルゴリズムにおける局所最適構造
- 制約グラフの局所性を用いた併合法の並列化について
- バックトラック無しアルゴリズムの実験評価
- あいまいな三面図の概略理解手法
- プリミティブ合成による概略三面図からの3次元モデルの復元
- L-systemを用いた仮想都市のための道路網生成手法
- 遺伝的アルゴリズムを用いた仮想都市のための建物配置方式 (知能情報メディア論文特集)
- セルの相互作用とGAを用いた仮想都市の生成
- 3S-8 セルの相互作用に基づく仮想都市の創発
- 仮想都市生成システムのための建物配置手法の検討
- 4M-1 点字用分かち書きへの表層解析と形態素解析による事例ベース推論の導入
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- ヒューマンインタフェースのための2点入力による相対運動認識方法
- 「感情」を直接制御できないシステムの一考察
- 制約充足問題の多項式時間全解探索について
- 制約充足問題の多項式時間全解探索について
- 制約充足問題の計算複雑さについて(1)
- 曲線形状を含む部品図面の解釈
- 超並列ビジュアライゼーションマシーンの検討
- 拘束条件の構造を考慮した整合ラベリング問題の解法
- 制約に基づく対話型時間割編成システム
- 制約違反最少化戦略による対話型時間割編成システム
- 制約違反最少化戦略による対話型時間割編成システム
- 面の組合せ探索による三面図の解釈
- 曲げ加工機能を有する板金図面生成システム
- 曲げ加工機能を有する対話型図面生成システム
- 制約違反最少化戦略に基づくハイブリッドGAによる制約充足問題の解法
- ウイルス感染を用いたハイブリッドGAによるリアルタイム経路探索
- 遺伝的アルゴリズムによる制約充足問題の解法
- 遺伝的アルゴリズムによる制約充足問題の解法
- 仮想都市のためのL-systemによる道路網生成手法の検討
- 拡張制約表現による時間割編成システム
- 整合ラベリングのための改良拘束伝播法
- 局所的手続きによる画像の偽輪郭の除去
- 三面図を対象とした知的CADシステム
- 制約充足問題の並列化効率に基づく分類
- 制約条件の構造に着目したCSPの分類方法
- 制約充足問題の併合解法における並列化の効率解析
- ニューラルネットワークの集団を用いた制約充足問題の解法
- 制約充足に基づく三面図理解システム
- 高速化の知識を取り入れた制約充足問題の一般解法
- 図面の直線形状による細線化歪みの除去
- 動的環境を対象とした遺伝的アルゴリズムによる実時間径路探索
- 対話的図形描画のための幾何制約ソルバ
- 特徴的幾何パターンに基づく不完全三面図の概略理解
- ニューラルネットワークを用いたオンラインハングル文字の適応認識
- あいまいな三面図の概略理解手法
- 面間の局所的拘束関係を用いた三面図解釈
- ハッシュ技術を用いた集合関数の処理法
- 制約知識ベースに基づく三面図理解
- 制約充足に基づく三面図理解
- 省略のある板金三面図からの3次元モデルの復元
- 省略の含まれる三面図からの3次元モデルの復元
- 省略の含まれる三面図からの3次元モデルの復元
- 地形を考慮したLシステムに基づく仮想都市のための道路網の生成
- 角運動量変化を利用した力覚提示デバイス(ウエアラブルVR)
- 板金向き三面図入力システムの開発曲げ加工におけるコーナーの自動生成
- 知識ベースにもとづく三面図の矛盾解消
- 図面の生成・理解によるモデリングのためのCADシステム : 画面理解および一般 : 画像処理・コンピュータビジョン
- 曲面を含む三面図の矛盾の検出と理解
- 図面の生成・理解によるモデリングのためのCADシステム
- 整合ラベリング問題における併合解法の並列化について
- 概整合ラベリング問題における併合法の最適化と効率評価
- 曲げ加工機能を有する板金図面生成システム
- 適応型確率探索による制約充足問題の解法
- 補助線を用いない三面図からの曲面物体の復元
- DLを使いこなそう:電子図書館のススメ