« Fuzzy Constraint Satisfaction Using CCM -- A Local Information Based Computation Model | Main | Combinatorial Problem Solving Using Randomized Dynamic Tunneling on A Production System »

Large-scale Constraint Satisfaction Using Local-information-based Annealing and Its Parallel Processing -- An Application of Emergent Computation Model CCM --

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

Post a comment

About

This page contains a single entry from the blog posted on August 1, 1995 12:00 AM.

Many more can be found on the main index page or by looking through the archives.

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