拘束条件の構造を考慮した整合ラベリング問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
整合ラベリング問題は,複数個の構成要素から成る対象を解釈するのに,まず,各構成要素に対して局所的解釈の候補を求め,それらの中から対象物全体の矛盾のない解釈を求める問題である.このような問題は,画像処理や人工知能など多くの分野に見いだされる.この問題に対しては,従来より,大別して,バックトラッキングを用いた木探索による解法,弛緩操作や拘束伝播を用いたフィルタリングによる前処理を含む解法の二つが示されている.本稿で示す解法は,これらの方法とは異なり,動的計画法の手法に基づくものである.すなわち,まず,拘束条件の構造に注目して,与えられた問題をより小さなサイズの問題に分解する.そして,そちらより得られる複数個の部分解を矛盾なく結合することによって全体の解を得ようというものである.ここでは,分解された小問題のサイズを表すfront指数を導入し,与えられた個々の問題に固有のfront指数をもとに計算量を評価した.さらに,与えられた問題の分解とfront指数に関する幾つかの性質について述べ,front指数が下限をとるような最適分解を求めるアルゴリズムを与えた.
- 一般社団法人情報処理学会の論文
- 1986-10-15
著者
関連論文
- 事例・ルール間変換による知識編成方式と日本語点字翻訳の分かち書き問題への適用
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- 知識べースに基づく対話型点字翻訳システム
- 筑波大学における電子図書館システムの実現と運用
- 時間変化する仮想都市における道路網の自動生成
- 図面理解システムにおける制約充足に基づくプロトタイピング
- グラフ3彩色問題におけるEHIの組織的生成(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
- 非常に難しいグラフ3彩色問題の組織的生成法と考察
- 事例ベース推論と制約充足に基づく室内レイアウト変更計画(自動推論 : 演繹, 帰納, モデル検査/生成, 仮説推論アブダクション, 論理プログラム, プランニング, 時相論理, etc.)
- 確率的制約充足アルゴリズムにおける局所最適構造