通信学报 ›› 2013, Vol. 34 ›› Issue (6): 102-107.doi: 10.3969/j.issn.1000-436X.2013.06.012

• 学术论文 • 上一篇    下一篇

结合look-ahead值排序的自适应分支求解算法

王海燕1,欧阳丹彤1,张永刚1,张良1   

  1. 1 吉林大学 计算机科学与技术学院,吉林 长春 130012
    2 吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012
    3 吉林师范大学 计算机学院,吉林 四平 136000
  • 出版日期:2013-06-25 发布日期:2017-07-20
  • 基金资助:
    国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;吉林省科技发展计划基金资助项目;吉林省科技发展计划基金资助项目;吉林省科技发展计划基金资助项目;国家教育部博士点专项基金资助项目

Novel adaptive branching constraint solving algorithm with look-ahead strategy

Hai-yan WANG1,YANGDan-tong OU1,Yong-gang ZHANG1,Liang ZHANG1   

  1. 1 College of Computer Science and Technology, Jilin University, Changchun 130012,China
    2 Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education, Jilin University, Changchun 130012, China
    3 College of Computer, Jilin Normal University, Siping 136000, China
  • Online:2013-06-25 Published:2017-07-20
  • Supported by:
    The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;Jilin Province Science and Technology Development Plan;Jilin Province Science and Technology Development Plan;Jilin Province Science and Technology Development Plan;Doctoral Fund of Ministry of Education of China

摘要:

基于新近提出的自适应分支约束求解框架,结合 look-ahead 值启发式,提出一种新的约束求解算法AdaptBranchLVO。为验证算法效率,在标准测试库上进行了充分对比实验。结果表明,新提出算法在效率上明显优于已有的自适应分支求解算法。

关键词: 约束满足问题, 约束求解, 自适应分支, look-ahead值启发式

Abstract:

Based on the state-of-the-art scheme of adaptive branching constraint solving, a novel algorithm named AdaptBranchLVOwas proposed, combined with the look-ahead value ordering heuristics. To demonstrate the efficiency of AdaptBranchLVO, sufficient experiments on the wide range of the problem instances in Benchmark were carried out, and the experiment results show that AdaptBranchLVOoutperforms the existing adaptive branching constraint algorithm by a large margin.

Key words: constraint satisfaction problems, look-ahead value ordering heuristics, constraint solving, adaptive branching

No Suggested Reading articles found!