非二元约束满足问题的E-GENET求解原理

Theory of Solving of E-GENET for Non-Binary Constraint Satisfaction Problems

通过E-GENET的重定义,将非二元约束满足问题(NB-CSPs)转化为整数最小化问题,提出一类非二元变量约束关系的离散拉格朗日搜索模式(NB-LSDL)与算法,实现了基于NB-LSDL的E-GENET重构,为求解一般约束CSPs的最小冲突启发式修补方法提供新的理论依据,扩展了E-GENET处理问题的技术与手段.实验结果显示了方法的可行性与有效性.

Non-binary constraint satisfaction problems （NB-CSPs） are transformed into the integer constrained minimization problems by extending correlative definitions of E-GENET. Then, a class of discrete Lagrangian-hased search scheme and algorithm with non-binary variable constraints （NB-LSDL） is proposed for such probllems to restructure E-GENET from NB- LSDL. It is useful to gain important insights into the heuristic repair method to minimize conflicts and improve variant of E- GENET for the CSPs with general constraints in a new theoretical perspective. The experimental results show that it is effective and feasible to re-extend E-GENET by using NB-LSDL.