« Constraint Satisfaction by Parallel Optimization of Local Evaluation Functions with Annealing | メイン | Web ページを自己再生産する JavaScript プログラム »

Methods of Parallel Processing of Constraint Satisfaction Using CCM -- A Model for Emergent Computation

Kanada, Y., SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996, Published by JSAI.

[ English page ]
[ 論文 PDF ファイル ] [ 論文ポストスクリプト・ファイル]
[ 論文 DVI ファイル (図をのぞく)] [ EPSF 形式の図 : 1, 2, 3, 4, 5, 6, 7, 8 ]

要旨 (英語のみ) : Two methods for solving large-scale constraint satisfaction problems using parallel processing are surveyed in the present paper. These methods are based on CCM, which is a model for emergent computation. The number of constraint violations is minimized in these methods. The minimization is performed by optimization of local functions. The computation is stochastic and no global information is used. An annealing method called FAM has been introduced to avoid ``local maxima.'' FAM also works only with local information. Two types of parallel processing of CCM-based constraint satisfaction using FAM has been tested. One is a parallel search and the other is a cooperative search. Our experiments has shown that both methods improve performance almost linearly in large-scale graph coloring problems when the number of processors is ten or so.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 創発的計算, 制約充足問題, 並列処理, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決



螺旋 3D 印刷技術を使用してつくったこのような「3D デザインランプ」を 3d-dl.com で売っています.


1996-02-01 00:00に投稿されたエントリーのページです。


(C) 2008 by Yasusi Kanada
Powered by Movable Type