权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Study of State Space Search by Lagrangian Method for Combinatorial Problems

组合问题的拉格朗日法状态空间搜索研究

基本信息

批准号：
11680363
负责人：
NAGAMATU Masahiro
金额：
$ 0.77万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11680363/
关键词：
combinatorial problem propositional calculus satisfiability problem Lagrangian method neural network state space search ambiguity routing problem 探索タブ探索

项目摘要

We have proposed a neural network called LPPH which solves the satisfiability problem of propositional calculus (SAT) more efficiently than the conventional methods. The LPPH is based on Lagrangian method, and its dynamics is represented by a set of continuous differential equations. In this project, we investigate the following.(1) The LPPH dynamics has a parameter called "decay factor". We discusse the relationship between the decay factor and the global convergence property. From the result of the discussion we proposed the LPPH dynamics which has two types of decay factor. They are called long and short term memory, respectively. By experiment their effectiveness is proved.(2) Another improvement of the dynamics is proposed. The dynamics has parameters called "coefficients of attention". By controlling the coefficients, sets of clauses of the CNF which are hard to satisfy are found and satisfied by priority. Experimental results show the dynamics is effective especially for difficult problems.(3) A routing algorithm which is based on Lagrangian method is proposed. Some small but congested routing problems are solved more effectively then the conventional methods.(4) We investigate the cases where some preliminary solution is given with a CNF.The preliminary solution comes from the background knowledge, the preliminary search, the heuristics, or the additional constraint such that the solution to be found must be similar to the given one. We introduce "bias" to the LPPH dynamics to deal with the preliminary solution. Experimental results show that the proposed dynamics can effectively find the nearest or approximately nearest solution to the given preliminary solution even if it includes some uncertainties and/or errors.

我们提出了一种称为LPPH的神经网络，它比传统的方法更有效地解决了命题演算的可满足性问题。LPPH基于拉格朗日方法，其动力学由一组连续的微分方程组表示。在本课题中，我们主要研究了以下几个方面：(1)LPPH动力学中有一个称为“衰变因子”的参数。讨论了衰减因子与全局收敛性质之间的关系。根据讨论的结果，我们提出了具有两种衰变因子的LPPH动力学。它们分别被称为长期记忆和短期记忆。通过实验证明了它们的有效性。(2)提出了对动力学的另一种改进。动力学中的参数被称为“注意系数”。通过对系数的控制，找到CNF中难以满足的子句集合，并优先满足。实验结果证明了该算法的有效性。(3)提出了一种基于拉格朗日方法的布线算法。与传统方法相比，该方法能更有效地解决一些较小但拥塞的路径问题。(4)我们研究了使用CNF给出一些初步解的情况，这些初步解来自背景知识、初步搜索、启发式算法或附加约束，使得所要找到的解必须与给定的解相似。我们将“偏差”引入到LPPH动力学中来处理初步解。实验结果表明，即使存在一定的不确定性和/或误差，所提出的动力学方法也能有效地找到与给定初始解最接近或近似最接近的解。