制約充足問題の並列化効率に基づく分類

IR IPSJ HANDLE 2 Citations 8 References Open Access

Bibliographic Information

Other Title
  • Classifying CSPs on the Basis of Parallelism
  • 人工知能

Search this article

Abstract

制約充足問題（CSP）とは複数の構成要素に関する局所的解釈の候補が与えられたときに対象物全体の矛盾のない解釈を求める問題である。このような問題は人工知能の分野における線画理解などの問題、N一クィーン問題等のパズル、さらに同型部分ネットワークの探索など極めて幅広い分野に広がっている。CSPはNP完全な探索問題の一種であり，効率の良い汎用解法は存在しない、したがって、具体的な応用問題ごとにその特徴を活かした解法を開発する必要があると予測される。本論文ではその解法の1つである併合法と呼ばれる横型探索法について考察する。併合法とは制約条件をグラフの頂点に対応させた制約ネットワークを生成し、その頂点同士の併合操作を順次進めて最終解を求める方法である、この方法の特徴として、各頂点併合操作を独立に行うことができるため処理の並列化が容易である点が挙げられる。しかしCSPの種類によっては並列処理する頂点をどのように選んでも逐次で処理した方が処理時間が少ない場合が存在する。本論文では併合法における並列処理の効率悪化の原因を明らかにするために、併合処理が3種類に分類されることを示し、分類された各処理の性質を明らかにする。さらに並列処理可能な基本的な構成である4頂点の制約ネットワークをその位相構造に着目して分類し、実験によりCSPの位相構造と並列処理の効率の関係について解析する。

Journal

Citations (2)*help

See more

References(8)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top