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

针对命题微积分的可满足性问题，提出了一种基于拉格朗日方法的LPPH神经网络动力学方法。实验结果表明，该方法比现有方法更能有效地求解问题。在本项目中，我们研究了以下几点：1)将LPPH从SAT的求解器扩展到更一般的约束满足问题的求解器。实验表明，这种扩展是有效的。我们还证明了LPPH适用于大规模并行处理和硬件实现。2)为了加速LPPH，我们提出了以下方法：(1)基于每个时间步只有少量变量改变其值的事实来减少计算量，(2)对每种约束类型赋予不同的重要程度。3) UML类图自动布局的应用。4)并行执行LPPH的建议5)通过互连网络或电子电路实现LPPH。

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.