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