A Method of Solving Constraint Satisfaction Problems using Production Rules and Local Evaluation Functions
Kanada, Y., and Hirokawa, M.: , SIG Notes of Symbol Processing, Information Processing Society of Japan, 93-SYM-68-2, 1993, Published by IPSJ.
[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF ファイル: Slides, Handout ]
Abstract: The authors have proposed the Chemical Casting Model (CCM), which is a computation model for self-organizing computation. In this model, "programs" consist of a few production rules and evaluation functions (or local order degrees), both of which only refer to local information. A method of solving certain constraint-satisfaction problems, based on this model, is presented in this paper. This method enables to solve constraint-satisfaction problems, such as the N-queens problems or map coloring problems, in a polynomial order time, without using deterministic and procedural constraint propagation, but using a stochastic method, and by a very simple "program." This paper also mentions to the characteristics of the computation by on this method, based on several measurements.
Introduction to this research theme: CCM: Chemical-Computation Model