Solving Constraint Satisfaction Problew by Using Dynamics Which Can Search State-Space Globally

点击翻译按钮获取中文摘要

For the satisfiability problem of propositional calculus (SAT), we have proposed a neural network dynamics called LPPH which is based on Lagrangian method. From experimental results it is known that this dynamics can find a solution more effectively than already proposed method. In this project, we investigate the following :1)The LPPH is extended from a solver of the SAT to a solver of the more general constraint satisfaction problems. By experiments we show that this extension is effective. We also show the LPPH is suitable for massively parallel processing and hardware implementation.2)To speedup the LPPH we proposed the following method : (1)reduction of the amount of computation based on the fact that at each time step only small number of variables change their values, and (2)giving different degree of importance for each type of constraint.3)Application for automatic layout of UML class diagram.4)Proposal of parallel execution of the LPPH.5)Implementation of the LPPH by interconnection networks or electronic circuits.