首页> 中文期刊> 《计算机集成制造系统》 >基于动态值启发式的约束满足求解算法

基于动态值启发式的约束满足求解算法

         

摘要

为提高约束满足问题的求解效率,提出了一种基于动态值启发式的约束满足问题求解算法.该算法在求解过程中吸收了以往启发式算法的优点,充分利用了预处理和弧相容检查阶段的信息.不但加入了变量启发式,而且在实例化变量时,对所有值的优先级进行动态的改变,从而实现了动态值启发式.比较了静态值启发式和动态值启发式的效率,分析了该算法的优缺点.通过随机问题标准库用例测试表明,该算法比经典主流算法具有更好的效率优势.%To improve the efficiency of solving constraint satisfaction problems, an algorithm for constraint satisfaction problems based on dynamic value ordering heuristics named Backtrack Dynamic Value ordering Heuristic algorithm (BT-DVH) was proposed.In the solving process, this algorithm absorbed the advantages of the previous heuristics, and made full use of the information generated in preprocess and arc consistency checking.To achieve dynamic value ordering heuristic, variable ordering heuristic was used, and the priorities of the values were changed dynamically to instantiate the variables.The efficiencies of the static and dynamic value ordering heuristics were compared, the advantages and shortcomings of the BT-DVH were analyzed.Tested by random problems and benchmark, the result showed this algorithm had a higher efficiency than classic mainstream algorithm.

著录项

  • 来源
    《计算机集成制造系统》 |2011年第4期|832-837|共6页
  • 作者单位

    吉林大学符号计算与知识工程教育部重点实验室;

    吉林长春;

    130012;

    吉林大学计算机科学与技术学院;

    吉林长春;

    130012;

    吉林大学符号计算与知识工程教育部重点实验室;

    吉林长春;

    130012;

    吉林大学计算机科学与技术学院;

    吉林长春;

    130012;

    吉林大学符号计算与知识工程教育部重点实验室;

    吉林长春;

    130012;

    吉林大学计算机科学与技术学院;

    吉林长春;

    130012;

    吉林大学符号计算与知识工程教育部重点实验室;

    吉林长春;

    130012;

    吉林大学计算机科学与技术学院;

    吉林长春;

    130012;

  • 原文格式 PDF
  • 正文语种 chi
  • 中图分类 人工智能理论;
  • 关键词

    动态值启发式; 值排序; 约束满足问题; 弧相容技术; 启发式算法;

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号