制約充足問題における制約緩和法を用いた最適化

概要

論文の詳細を見る
近年、制約充足問題(Consraint Satisfaction Problem,以下CSP)が、AIにおける重要な問題として論じられている。CSPは、制約を満たすように、与えられた変数に対する値の割り当てを見つける問題である。CSPの目的は、制約を満たす解を1つ見つけることであるが、我々は、制約を満たす割り当ての中で、与えられた目的関数を最適化する解を求める問題を扱う。我々は、このような問題を制約充足最適化問題(Constraint Satisfying Optimization Problcm,以下CSOP)と呼ぶ。一般に、CSPはNP-completeであることが知られているので、ヒューリスティクが利用される。近年、最小制約違反ヒューリスティク(Min-conflict heuristic )とよばれる効率のよいヒューリスティクが提案されている。これは初期割り当てから開始して、制約違反している変数を選んで、最も制約違反を減らすように値の再割当を行ない、これを制約が完全に充足されるまで繰り返す。本論文では、我々は、最小制約違反ヒューリスティクの利点を生かした、CSOPに対するヒューリスティクな手法を提案する。まだ、典型的なCSPであるN-queen問題を拡張したCSOPを取り上げ、我々の手法が、特に制約が強い問題に対して有効であることを実証する。
一般社団法人情報処理学会の論文
1991-02-25

制約充足問題における制約緩和法を用いた最適化

スポンサーリンク

概要

著者

関連論文

スポンサーリンク