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

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

作　　者：冯欣[1] 唐立新[1] 梁浩锋[2] 

机构地区：[1]东北大学教育部暨辽宁省流程工业综合自动化重点实验室,辽宁沈阳110004 [2]香港中文大学计算机科学与工程系

出　　处：《东北大学学报（自然科学版）》2005年第9期844-847,共4页Journal of Northeastern University(Natural Science)

基　　金：国家杰出青年学者自然科学基金资助项目(70425003);国家自然科学基金资助项目(70171030;60274049)

摘　　要：通过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.

关 键 词：约束满足问题 E-GENET网 离散拉格朗日方法 启发式修补方法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]