东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2005, Vol. 26 ›› Issue (9): 844-847.DOI: -

• 论著 • 上一篇    下一篇

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

冯欣;唐立新;梁浩锋   

  1. 东北大学教育部暨辽宁省流程工业综合自动化重点实验室;东北大学教育部暨辽宁省流程工业综合自动化重点实验室;香港中文大学计算机科学与工程系 辽宁沈阳110004
  • 收稿日期:2013-06-24 修回日期:2013-06-24 出版日期:2005-09-15 发布日期:2013-06-24
  • 通讯作者: Feng, X.
  • 作者简介:-
  • 基金资助:
    国家杰出青年学者自然科学基金资助项目(70425003);;

Theory of solving of E-GENET for non-binary constraint satisfaction problems

Feng, Xin (1); Tang, Li-Xin (1); Leung, Ho-Fung (2)   

  1. (1) Key Laboratory of Process Industry Automation, Northeastern University, Shenyang 110004, China; (2) Department of Computer Science and Engineering, Chinese University of Hong Kong, Hong Kong, Hong Kong
  • Received:2013-06-24 Revised:2013-06-24 Online:2005-09-15 Published:2013-06-24
  • Contact: Feng, X.
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

709

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

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

Abstract: 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-based search scheme and algorithm with non-binary variable constraints (NB-LSDL) is proposed for such problems 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.

中图分类号: