| 講演名 | 1995/8/22 局所情報によるアニーリングをつかった大規模制約充足とその並列処理 : 創発的計算のためのモデルCCMの応用 金田 泰, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | この報告では,創発的計算のためのモデルCCM(化学的キャスティング・モデル)にもとづいて大規模な制約充足問題をとくための方法を提案する.また,その並列処理の方法をしめす.CCMにもとづく方法ではこれまで大規模な問題をとくことができなかったが,FAM(フラストレーション蓄積法)という一種のアニーリングを導入し,さらにパラメタをうまく調整することによって,大規模なグラフ彩色問題をGSATやシミュレーテッド・アニーリングと同程度の計算時間で逐次処理でとくことができるようになった.さらに,かぎられた量の相互排斥だけをつかって,比較的容易に並列処理できることがわかった.ある条件のもとではほぼプロセッサ数に比例する性能がえられた. |
| 抄録(英) | A method for solving large-scale constraint satisfaction problems based on CCM (Chemical Casting Model), which is a model for emergent computation, is proposed in this report. A parallelized version of this method is also shown. Large-scale problems could not be solved using CCM. However, this report shows that, by introducing a method of annealing called FAM (Frustration Accumulation Method) and by adjusting the parameters appropriately, several large-scale graph coloring problems has become solvable with spending the same order of time as GSAT or simulated annealing by sequential processing using CCM. This report also shows that this method can easily be parallelized with restricted amount of mutual exclusion. The performance is almost proportional to the number of processors under certain conditions. |
| キーワード(和) | 創発的計算 / 制約充足 / 並列処理 / アニーリング / 彩色問題 / グラフ彩色 |
| キーワード(英) | Emergent computation / Constraint satisfaction / Parallel processing / Annealing / Coloring Problem / Graph coloring |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 1995/8/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 局所情報によるアニーリングをつかった大規模制約充足とその並列処理 : 創発的計算のためのモデルCCMの応用 |
| サブタイトル（和） | |
| タイトル（英） | Large-scale Constraint Satisfaction Using Local-information-based Annealing and Its Parallel Processing : An Application of Emergent Computation Model CCM |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 創発的計算 / Emergent computation |
| キーワード(2)（和/英） | 制約充足 / Constraint satisfaction |
| キーワード(3)（和/英） | 並列処理 / Parallel processing |
| キーワード(4)（和/英） | アニーリング / Annealing |
| キーワード(5)（和/英） | 彩色問題 / Coloring Problem |
| キーワード(6)（和/英） | グラフ彩色 / Graph coloring |
| 第 1 著者 氏名（和/英） | 金田 泰 / Yasusi Kanada |
| 第 1 著者 所属（和/英） | 新情報処理開発機構(RWCP)つくば研究センタ Tsukuba Research Center, Real-World Computing Partnership |
| 発表年月日 | 1995/8/22 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 211 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |