« June 1995 | Main | October 1995 »

August 1995 Archives

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

Keywords: CCM, Constraint satisfaction problem, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Local evaluation function

Last: June 1995

Next: October 1995

(C) Copyright 2007 by Yasusi Kanada
Powered by
Movable Type 3.36