WEKO3
アイテム
制約充足問題における体系的探索手法の効率化についての検討
https://tuis.repo.nii.ac.jp/records/336
https://tuis.repo.nii.ac.jp/records/336cab3d630-9881-44a9-8391-f2b6a4290ffe
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00002362072 (441.8 kB)
|
TUIS
|
| Item type | 紀要論文(ELS) / Departmental Bulletin Paper(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2005-02-28 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 制約充足問題における体系的探索手法の効率化についての検討 | |||||||||||
| 言語 | ja | |||||||||||
| タイトル | ||||||||||||
| タイトル | Towards an Improvement of Systematic Search Methods for Constraint Satisfaction Problems | |||||||||||
| 言語 | en | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| キーワード | ||||||||||||
| 主題 | 制約充足問題, 探索, バックトラック, アルゴリズム, 効率化 constraint satisfaction problem, search, backtrack, algorithm, efficiency |
|||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
| 資源タイプ | departmental bulletin paper | |||||||||||
| ページ属性 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | P(論文) | |||||||||||
| 著者名(日) |
永井, 保夫
× 永井, 保夫
× Nagai, Yasuo
|
|||||||||||
| 著者所属(日) | ||||||||||||
| ja | ||||||||||||
| 東京情報大学 | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Tokyo University of Information Sciences | ||||||||||||
| 抄録(日) | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | 制約充足問題は人工知能や画像解析の分野をはじめ、グラフの問題やパズルなどの探索問題、いわゆる組み合わせ問題を対象として研究がおこなわれている。制約充足問題とは、変数の有限集合および各変数に対応する離散値の有限集合のドメインから値を選択し、すべての制約を満足するように各変数に対して値を割り当てる問題である。制約とは適用対象の構成要素およびその属性間で成立する関係を宣言的に記述したものである。 制約充足問題における従来の解法としては、バックトラックを基本とした探索による方法や整合化手法などに代表される前処理を用いる方法が代表的である。この場合には、解法としては探索空間の全域を対象としてすべての可能性を探索するもので、アルゴリズムの完全性を保証している。完全性とは、探索空間に解が存在すれば、必ず見つけられることと、解がなければ必ず存在しないことを保証するものである。 このような体系的探索法を用いる解法では、生成検査法やバックトラック法などに基づき解が求められる。特に、すべての解を求める場合には、探索木全体の探査が要求される。バックトラックに基づいた探索では、無駄なバックトラックが頻発してしまい効率が悪い。特に、全解を求めたい場合には、探索木全体をたどることになってしまうので、無駄な分岐を避けることが望ましい。 本論文では、まず、バックトラックによる効率改善手法として、知的バックトラックの一種であるバックジャンピングやバックトラックと整合化手法を組み合わせたフォワードチェッキングといった無駄な探索枝を刈り込む手法について説明する。次に、制約充足問題の代表例である地図の色塗り問題へ適用し、その結果について示す。 | |||||||||||
| 言語 | ja-Kana | |||||||||||
| 抄録(英) | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | In this paper, we describe and discuss improvement methods of systematic search for constraint satisfaction problems. Effectiveness of these improvement methods is shown using application of these methods to map coloring problem. | |||||||||||
| 言語 | en | |||||||||||
| 雑誌書誌ID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AA11155514 | |||||||||||
| 書誌情報 |
ja : 東京情報大学研究論集 巻 8, 号 2, p. 67-78, 発行日 2005-02-28 |
|||||||||||
| 出版者 | ||||||||||||
| 出版者 | 東京情報大学 | |||||||||||
| 言語 | ja | |||||||||||
