Study of State Space Search by Lagrangian Method for Combinatorial Problems

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

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.