Kanada, Y., SWoPP '95 (SIG Note of Artificial Intelligence, Information Processing Society of Japan), AI95-16, pp. 17-24, 1995, Published by IPSJ
[ 日本語のページ ]
[ Paper postscript file]
Abstract: 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.
Introduction to this research theme: CCM: Chemical-Computation Model