« CCM: A Model Based on Analogies to Chemical Reaction System for Open and Complex Computation -- Its Relation to the Interlocked Neural Networks -- | Main | Fuzzy Constraint Satisfaction Using CCM -- A Local Information Based Computation Model »

Parallel Processing Method of Local-Information-Based Combinatorial Problem Solving Based on Implicit Stochastic Divide-and-Conquer

Kanada, Y., not yet published, 1995.

[日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]

Abstract: A method of solving combinatorial problems, such as the N queens problem or graph coloring problems using independent parallel processes, is proposed in the present paper. This method is stochastic (or randomized). Problems are decomposed for parallel processing implicitly and stochastically by this method. This method is based on CCM, which is a computational model proposed by the author. A program consists of production rules and local evaluation functions in CCM. Each process uses the same set of rules and functions, and it may use the same set of initial data in this method. However, the performance is approximately in proportion to the number of processors in average in certain cases. The theoretical reason of this linear acceleration is explained, and several results of experiments, some of which was successful but others were not, are also shown.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Parallel processing, Combinatorial optimization, Constraint satisfaction problem, Traveling salesperson problem, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving

Post a comment

About

This page contains a single entry from the blog posted on January 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