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

利用全局搜索状态空间的动力学解决约束满足问题

• 批准号: 14580383
• 负责人: NAGAMATU Masahiro
• 金额: $ 1.28万
• 依托单位: Kyushu Institute Of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14580383/
• 关键词: satisfiability problem; constraint satisfaction problem; neural network; Lagrangian method; global state-space search

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.

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

项目成果

Masahiro Nagamatu, et al.: "Extensions of Lagrange Programming Neural Network for Satisfiability Problem and its Several Variations"Proceedings of 9th International Conference on Neural Information Processing. 1781-1785 (2002)

Masahiro Nagamatu 等人：“Extensions of LagrangeProgramming Neural Network for Satisfiability Problem及其几种变体”第九届国际神经信息处理会议论文集。

Masahiro Nagamatu, Takahiro Nakano: "Constraint Satisfaction Problems and Neurocomputing"Abstracts of International Symposium on Bio-inspired System. 27 (2004)

Masahiro Nagamatu、Takahiro Nakano：《约束满足问题与神经计算》仿生系统国际研讨会摘要。

張楷栄, 永松正博: "ニューラルネットワークの並列化による充足可能性問題の解放"日本ファジー学会ソフトサイエンス研究部会第14回ソフトサイエンス・ワークショップ講演論文集. 98-99 (2004)

Kairong Zhang，Masahiro Nagamatsu：“通过并行化神经网络释放可满足性问题”日本模糊学会软科学研究组第 14 届软科学研讨会论文集 98-99（2004）。

Takahiro Nakano, Masahiro Nagamatu: "Solving CSP by Lagrangian Method"Proceedings of the Third POSTECH-KY JTECH Joint Workshop on neuroinformatics. 26 (2003)

Takahiro Nakano、Masahiro Nagamatu：“通过拉格朗日方法求解 CSP”第三届 POSTECH-KY JTECH 神经信息学联合研讨会论文集。

Takahiro Nakano, Masahiro Nagamatu: "Solving CSP by Lagrangian Method"Proceedings of the Third POSTECH-KYUTECH Joint Workshop on neuroinformatics. (2003)

Takahiro Nakano、Masahiro Nagamatu：“通过拉格朗日方法求解 CSP”第三届 POSTECH-KYUTECH 神经信息学联合研讨会论文集。