-
题名非二元条件约束满足问题求解
被引量：2
- 1
-
-
作者
袁际军
黄敏镁
-
机构
广东财经大学金融学院
华南师范大学管理科学系
-
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2014年第3期636-651,共16页
-
基金
国家自然科学基金资助项目(71272084
71102146)
+2 种基金
教育部人文社会科学研究青年基金资助项目(12YJC630278)
广东省普通高校人文社科研究资助项目(2012LYM_0065)
广东商学院校级一般资助项目(11YB63001)~~
-
文摘
非二元条件约束满足问题是二元条件约束满足问题的泛化。给出了非二元条件约束满足问题模型;针对求解过程中激活性约束引起的变量空间变化,分别采用"后看"策略和嵌入不同程度非二元弧一致性的"前看"策略思想,提出一种非二元条件回溯算法和两种非二元条件前向检查算法,以有效处理约束维数的非二元性及变量依条件参与求解的动态性等问题;分析了三种算法最坏情况下的时间复杂性;通过随机生成的测试实例仿真实验比较了三种算法的求解性能。实验结果表明:在处理难问题时,两种非二元条件前向检查算法的性能均显著优于非二元条件回溯算法;而在分别处理中小规模低动态性特征与大规模高动态性特征问题时,两种非二元条件前向检查算法性能存在显著差异。
-
关键词
非二元条件约束满足问题
非二元条件回溯算法
非二元条件前向检查算法
非二元弧一致性
-
Keywords
non-binary conditional constraint satisfaction problem
non-binary conditional backtracking algorithm
non-binary conditional forward checking algorithm
non-binary arc consistency
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名基于关联约束非二元弧一致性的约束满足问题求解
被引量：1
- 2
-
-
作者
袁际军
单汨源
王克喜
-
机构
湖南大学工商管理学院
-
出处
《计算机科学》
CSCD
北大核心
2008年第5期158-162,共5页
-
基金
国家自然科学基金项目(70671037)
高等学校博士学科点专项科研基金项目(20050532005)
-
文摘
弧一致性算法在二元约束满足问题中取得了成功的应用,但并不能被有效泛化至预处理非二元约束满足问题(NCSP)。本文提出了处理NCSP的关联约束非二元弧一致性算法。通过随机NCSP生成器产生问题实例,分别采用关联约束非二元孤一致性算法和非二元孤一致性算法进行预处理,并对预处理后的问题实例应用回溯算法进行求解。对比分析采用两种预处理算法和不采用预处理下回溯算法的求解性能,仿真实验结果表明关联约束非二元孤一致性算法可以有效地别除冗余的约束元组和变量域值,使关联约束非二元弧一致性回溯算法具有更良好的鲁棒性。
-
关键词
非二元约束满足问题
回溯算法
关联约束非二元弧一致性
随机NCSP生成器
-
Keywords
Non-binary constraint satisfaction problem, Backtracking, Associated constraint based non-binary arc-con-sistency, Random NCSP generator
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
TB21
[自动化与计算机技术—控制科学与工程]
-
