WEKO3
アイテム
バックトラック無しアルゴリズムの実験評価
https://ipsj.ixsq.nii.ac.jp/records/123350
https://ipsj.ixsq.nii.ac.jp/records/123350c28355e7-f516-4daf-a9d5-98900a5dc580
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00001337182.pdf (195.2 kB)
|
|
| Item type | National Convention(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 1993-03-01 | |||||
| タイトル | ||||||
| タイトル | バックトラック無しアルゴリズムの実験評価 | |||||
| タイトル | ||||||
| 言語 | en | |||||
| タイトル | Experimental Evaluation On Backtrack -free Algorithm | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||
| 資源タイプ | conference paper | |||||
| 著者所属 | ||||||
| 筑波大学 電子・情報工学系 | ||||||
| 著者所属 | ||||||
| 筑波大学 電子・情報工学系 | ||||||
| 著者所属 | ||||||
| 筑波大学 電子・情報工学系 | ||||||
| 著者所属 | ||||||
| 筑波大学 電子・情報工学系 | ||||||
| 著者所属 | ||||||
| 筑波大学 電子・情報工学系 | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Inst.Inf.Sci.& Electr.,University of TSUKUBA | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Inst.Inf.Sci.& Electr.,University of TSUKUBA | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Inst.Inf.Sci.& Electr.,University of TSUKUBA | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Inst.Inf.Sci.& Electr.,University of TSUKUBA | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Inst.Inf.Sci.& Electr.,University of TSUKUBA | ||||||
| 論文抄録 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 制約充足問題(CSP)は問題の対象の構成要素の局所的な構造に基づいて可能な局所解の侯補を求め、それらの中から対象全体について矛盾のない局所解の組合せを求める問題である。CSPを解くとは、制約を充足するような局所解すなわち変数への値の割り付けの組合せを探索していく処理である。この処理はバックトラックを基本とした縦型探索が主流である。これは、矛盾が起こらない限り中間解を拡張していく方法であり、矛盾が生じると探索木を遡り、別の局所解の候補を調べる。したがって、もし探索の過程が常に最終解に至る探索路に乗っていることが保証されるならば、バックトラックは発生しないはずである。このような探索を、'バックトラック無し'としいう。我々は先に、バックトラックによって探索木を遡る範囲がある一定サイズk(「幅」という、後述)以内に限られるようなCSPの部分クラスに注目して、バックトラック無しアルゴリズムを提案した。本稿はバックトラック無しアルゴリズムの計算時問量について実験で評価ま平価したものである。 | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AN00349328 | |||||
| 書誌情報 |
全国大会講演論文集 巻 第46回, 号 人工知能及び認知科学, p. 5-6, 発行日 1993-03-01 |
|||||
| 出版者 | ||||||
| 言語 | ja | |||||
| 出版者 | 情報処理学会 | |||||
