WEKO3
アイテム
制約充足問題への近似解法の適用検討 -N-クイーン問題を中心として-
https://tuis.repo.nii.ac.jp/records/335
https://tuis.repo.nii.ac.jp/records/3359f5bba2f-167f-4d63-bea7-d53ada5668c0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00002362062 (281.1 kB)
|
TUIS
|
| Item type | 紀要論文(ELS) / Departmental Bulletin Paper(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2005-02-28 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 制約充足問題への近似解法の適用検討 -N-クイーン問題を中心として- | |||||||||||
| 言語 | ja | |||||||||||
| タイトル | ||||||||||||
| タイトル | Towards Local Search Methods for Constraint Satisfaction Problems,Focusing on N-queen Problem | |||||||||||
| 言語 | en | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| キーワード | ||||||||||||
| 主題 | 制約充足問題, 近似解法, 局所探索, アルゴリズム, 高速化 constraint satisfaction problem, approximate method, local search, algorithm, speed-up |
|||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
| 資源タイプ | departmental bulletin paper | |||||||||||
| ページ属性 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | P(論文) | |||||||||||
| 著者名(日) |
永井, 保夫
× 永井, 保夫
× Nagai, Yasuo
|
|||||||||||
| 著者所属(日) | ||||||||||||
| ja | ||||||||||||
| 東京情報大学 | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Tokyo University of Information Sciences | ||||||||||||
| 抄録(日) | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | 制約充足問題は人工知能や画像解析の分野をはじめ、グラフの問題やパズルなどの探索問題、いわゆる組み合わせ問題を対象として研究がおこなわれている。制約充足問題とは、変数の有限集合および各変数に対応する離散値の有限集合のドメインから値を選択し、すべての制約を満足するように各変数に対して値を割り当てる問題である。制約とは適用対象の構成要素およびその属性間で成立する関係を宣言的に記述したものである。 制約充足問題における従来の解法としては、バックトラックを基本とした探索による方法や整合化手法などに代表される前処理を用いる方法が代表的である。この場合には、解法としては探索空間の全域を対象としてすべての可能性を探索するもので、アルゴリズムの完全性を保証している。完全性とは、探索空間に解が存在すれば、必ず見つけられることと、解がなければ必ず存在しないことを保証するものである。 これに対して、局所探索法による解法はこのアルゴリズムの完全性を保証しないかわりに、解を高速で求めることを特徴とした近似解法である。本論文では、制約充足問題の解法である近似解法についてサーベイするとともに、パズルの代表例であるN-クイーン問題を対象として、局所探索法による解法である山登り探索と制約違反最小化ヒューリスティックに基づいた山登り探索の適用結果について説明する。 | |||||||||||
| 言語 | ja | |||||||||||
| 抄録(英) | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | This paper reports on local search methods for constraint satisfaction problems. Especially, it focuses on and specifies a survey of these methods and application of two local search methods to N-queen problem and shows its effectiveness. | |||||||||||
| 言語 | ja-Kana | |||||||||||
| 雑誌書誌ID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AA11155514 | |||||||||||
| 書誌情報 |
ja : 東京情報大学研究論集 巻 8, 号 2, p. 59-66, 発行日 2005-02-28 |
|||||||||||
| 出版者 | ||||||||||||
| 出版者 | 東京情報大学 | |||||||||||
| 言語 | ja | |||||||||||
