制約充足問題の並列化効率に基づく分類
スポンサーリンク
概要
- 論文の詳細を見る
制約充足間題(CSP)とは複数の構成要素に関する局所的解釈の侯補が与えられたときに対象物全体の矛盾のない解釈を求める問題である. このような問題は人工知能の分野における線画理解などの問題, N-クイーン問題等のパズル, さらに同型部分ネットワークの探索など極めて幅広い分野に広がっている. CSPはNP完全な探索間題の一種であり, 効率の良い汎用解法は存在しない. したがって, 具体的な応用問題ごとにその特徴を活かした解法を開発する必要があると予測される. 本論文ではその解法の1つである併合法と呼ぱれる横型探索法について考察する. 併合法とは制約条件をグラフの頂点に対応させた制約ネットワークを生成し, その頂点同士の併合操作を順次進めて最終解を求める方法である. この方法のと特徴して, 各頂点併合操作を独立に行うことができるため処理の並列化が容易である点が挙げられる. しかしCSPの種類によっては並列処理する頂点をどのように選んでも逐次で処理した方が処理時間が少ない場合が存在する. 本論文では併合法における並列処理の効率悪化の原因を明らかにするために, 併合処理が3種類に分類されることを示し, 分類された各処理の性質を明らかにする. さらに並列処理可能な基本的な構成である4頂点の制約ネットワークをその位相構造に着目して分類し, 実験によりCSPの位相構造と並列処理の効率の関係について解析する.
- 一般社団法人情報処理学会の論文
- 1994-12-15
著者
-
西原 清一
筑波大学電子・情報工学系
-
狩野 均
筑波大学電子・情報工学系
-
窪田 信一郎
筑波大学電子情報工学系
-
窪田 信一郎
筑波大学電子・情報工学系
-
内野 寛治
筑波大学電子・情報工学系
-
内野 寛治
(株)富士通研究所
関連論文
- 事例・ルール間変換による知識編成方式と日本語点字翻訳の分かち書き問題への適用
- 点字翻訳ボランティアのための対話型分かち書き支援システム
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- 知識べースに基づく対話型点字翻訳システム
- 筑波大学における電子図書館システムの実現と運用
- ファジィクラスタリングに基づく道路交通量の予測方式に関する研究(セッション2)
- 遺伝的アルゴリズムによるルール変化型一次元セルオートマトンの進化
- CA法による広域道路交通シミュレータを用いた経路案内方式の評価(第2セッション)
- セルオートマトンとGAを用いた仮想都市の時系列的生成手法
- 時間変化する仮想都市における道路網の自動生成
- 図面理解システムにおける制約充足に基づくプロトタイピング
- グラフ3彩色問題におけるEHIの組織的生成(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
- 非常に難しいグラフ3彩色問題の組織的生成法と考察
- 事例ベース推論と制約充足に基づく室内レイアウト変更計画(自動推論 : 演繹, 帰納, モデル検査/生成, 仮説推論アブダクション, 論理プログラム, プランニング, 時相論理, etc.)
- 確率的制約充足アルゴリズムにおける局所最適構造
- 1N-3 制約充足問題における制約構造に注目した計算複雑さの考察
- 「使いながら学ぶ」検索エンジンのインタフェースデザイン : 0件ヒット対策を事例として
- 制約充足問題研究支援システム
- 併合法による制約充足の並列化効果について
- FFDを用いた3次元足部モデルの解剖学的特徴点抽出(コンピュータグラフィックス)
- 確率的制約充足アルゴリズムにおける局所最適構造
- 対話型進化計算によるポスター制作支援システムの開発
- 対話型進化計算によるポスター制作支援システムの開発
- 多目的遺伝的アルゴリズムを用いたカーナビゲーションのための予測経路探索(セッション2)
- 制約グラフの局所性を用いた併合法の並列化について
- バックトラック無しアルゴリズムの実験評価
- プリミティブ合成による概略三面図からの3次元モデルの復元
- ウイルス感染を用いた遺伝的アルゴリズムによる ニューラルネットワークの学習
- 遺伝的アルゴリズムを用いたカーナビのための経路案内方式(ITS情報処理・一般)
- 遺伝的アルゴリズムを用いたカーナビのための経路案内方式
- セルオートマトンとGAを用いた仮想都市の時系列的生成手法
- 集団の再利用に基づくGAによるカーナビゲーションのための動的経路探索
- L-systemを用いた仮想都市のための道路網生成手法
- 高度道路交通システム(ITS)とAI(高度道路交通システム(ITS)とAI)
- 遺伝的アルゴリズムを用いた仮想都市のための建物配置方式 (知能情報メディア論文特集)
- セルの相互作用とGAを用いた仮想都市の生成
- 3S-8 セルの相互作用に基づく仮想都市の創発
- 5L-5 ウイルス感染を用いたGAによるカーナビのための動的経路探索
- 仮想都市生成システムのための建物配置手法の検討
- 4M-1 点字用分かち書きへの表層解析と形態素解析による事例ベース推論の導入
- 新聞記事の検索支援システム(新聞情報)
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- ヒューマンインタフェースのための2点入力による相対運動認識方法
- 制約充足問題の多項式時間全解探索について
- 制約充足問題の多項式時間全解探索について
- 制約充足問題の計算複雑さについて(1)
- 曲線形状を含む部品図面の解釈
- 超並列ビジュアライゼーションマシーンの検討
- 拘束条件の構造を考慮した整合ラベリング問題の解法
- 制約に基づく対話型時間割編成システム
- 制約違反最少化戦略による対話型時間割編成システム
- 制約違反最少化戦略による対話型時間割編成システム
- 事前処理に k-means 法を利用したスパムフィルタの開発
- 事前処理に k-means 法を利用したスパムフィルタの開発
- 面の組合せ探索による三面図の解釈
- 曲げ加工機能を有する板金図面生成システム
- 曲げ加工機能を有する対話型図面生成システム
- 制約違反最少化戦略に基づくハイブリッドGAによる制約充足問題の解法
- ウイルス感染を用いたハイブリッドGAによるリアルタイム経路探索
- 遺伝的アルゴリズムによる制約充足問題の解法
- 遺伝的アルゴリズムによる制約充足問題の解法
- 行動ルールが変化する人工社会の進化的設計手法(進化的計算I)
- 仮想都市のためのL-systemによる道路網生成手法の検討
- 拡張制約表現による時間割編成システム
- 整合ラベリングのための改良拘束伝播法
- 局所的手続きによる画像の偽輪郭の除去
- 三面図を対象とした知的CADシステム
- 制約充足問題の並列化効率に基づく分類
- 制約条件の構造に着目したCSPの分類方法
- 制約充足問題の併合解法における並列化の効率解析
- ニューラルネットワークの集団を用いた制約充足問題の解法
- 制約充足に基づく三面図理解システム
- 高速化の知識を取り入れた制約充足問題の一般解法
- 図面の直線形状による細線化歪みの除去
- 動的環境を対象とした遺伝的アルゴリズムによる実時間径路探索
- 対話的図形描画のための幾何制約ソルバ
- 特徴的幾何パターンに基づく不完全三面図の概略理解
- ニューラルネットワークを用いたオンラインハングル文字の適応認識
- あいまいな三面図の概略理解手法
- 面間の局所的拘束関係を用いた三面図解釈
- ハッシュ技術を用いた集合関数の処理法
- 制約知識ベースに基づく三面図理解
- 制約充足に基づく三面図理解
- 省略のある板金三面図からの3次元モデルの復元
- 省略の含まれる三面図からの3次元モデルの復元
- 省略の含まれる三面図からの3次元モデルの復元
- 地形を考慮したLシステムに基づく仮想都市のための道路網の生成
- 角運動量変化を利用した力覚提示デバイス(ウエアラブルVR)
- 板金向き三面図入力システムの開発曲げ加工におけるコーナーの自動生成
- 知識ベースにもとづく三面図の矛盾解消
- 曲面を含む三面図の矛盾の検出と理解 : 画面理解および一般 : 画像処理・コンピュータビジョン
- 図面の生成・理解によるモデリングのためのCADシステム : 画面理解および一般 : 画像処理・コンピュータビジョン
- 曲面を含む三面図の矛盾の検出と理解
- 図面の生成・理解によるモデリングのためのCADシステム
- 整合ラベリング問題における併合解法の並列化について
- 概整合ラベリング問題における併合法の最適化と効率評価
- 曲げ加工機能を有する板金図面生成システム
- 適応型確率探索による制約充足問題の解法
- 補助線を用いない三面図からの曲面物体の復元
- DLを使いこなそう:電子図書館のススメ