WEKO3
アイテム
制約充足問題の並列化効率に基づく分類
https://ipsj.ixsq.nii.ac.jp/records/14051
https://ipsj.ixsq.nii.ac.jp/records/140518dfcdf29-a92b-4ca5-9e38-f99c5e9f8392
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL3512015.pdf (889.9 kB)
|
Copyright (c) 1994 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1994-12-15 | |||||||
| タイトル | ||||||||
| タイトル | 制約充足問題の並列化効率に基づく分類 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Classifying CSPs on the Basis of Parallelism | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| その他タイトル | ||||||||
| その他のタイトル | 人工知能 | |||||||
| 著者所属 | ||||||||
| 筑波大学電子・情報工学系 | ||||||||
| 著者所属 | ||||||||
| 筑波大学電子・情報工学系 | ||||||||
| 著者所属 | ||||||||
| 筑波大学電子・情報工学系 | ||||||||
| 著者所属 | ||||||||
| 筑波大学電子・情報工学系 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Institute of Information Sciences and Electronics, University of Tsukuba | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Institute of Information Sciences and Electronics, University of Tsukuba | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Institute of Information Sciences and Electronics, University of Tsukuba | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Institute of Information Sciences and Electronics, University of Tsukuba | ||||||||
| 著者名 |
内野, 寛治
× 内野, 寛治
|
|||||||
| 著者名(英) |
Kanji, Uchino
× Kanji, Uchino
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 制約充足問題（CSP）とは複数の構成要素に関する局所的解釈の候補が与えられたときに対象物全体の矛盾のない解釈を求める問題である。このような問題は人工知能の分野における線画理解などの問題、N一クィーン問題等のパズル、さらに同型部分ネットワークの探索など極めて幅広い分野に広がっている。CSPはNP完全な探索問題の一種であり，効率の良い汎用解法は存在しない、したがって、具体的な応用問題ごとにその特徴を活かした解法を開発する必要があると予測される。本論文ではその解法の1つである併合法と呼ばれる横型探索法について考察する。併合法とは制約条件をグラフの頂点に対応させた制約ネットワークを生成し、その頂点同士の併合操作を順次進めて最終解を求める方法である、この方法の特徴として、各頂点併合操作を独立に行うことができるため処理の並列化が容易である点が挙げられる。しかしCSPの種類によっては並列処理する頂点をどのように選んでも逐次で処理した方が処理時間が少ない場合が存在する。本論文では併合法における並列処理の効率悪化の原因を明らかにするために、併合処理が3種類に分類されることを示し、分類された各処理の性質を明らかにする。さらに並列処理可能な基本的な構成である4頂点の制約ネットワークをその位相構造に着目して分類し、実験によりCSPの位相構造と並列処理の効率の関係について解析する。 | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 35, 号 12, p. 2676-2684, 発行日 1994-12-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
