基于约束传播的约束求解方法研究

论文摘要

约束程序是人工智能的重要研究方向,约束推理是约束程序领域中一个重要的概念,它包括在求解一个约束满足时,为找到满足所有约束的解而用到的各种技术。而约束传播即为众多的约束推理技术之一,目前已经成为约束求解的核心技术。本文的主要工作是围绕约束传播而展开的,具体包括五个方面:（1）分析了当前流行的弧相容算法各自的优势和特点,并针对随机约束满足问题对系列弧相容算法性能进行了测试;（2）使用变量论域缩减比例对弧相容传播深度进行参数化描述,提出一个约束传播程度可以控制的弧相容传播算法,研究了在不同参数下约束求解算法的效率;（3）基于对现有技术的研究,提出一种在约束网络中确立双向singleton弧相容的新算法—BiSAC-2,并给出其正确性和完备性证明及随机约束满足问题的测试结果;（4）将本地动态变量启发式策略和展望策略与并发回溯搜索相结合,提出一个新的基于约束传播的并发搜索算法;（5）将研究成果嵌入我们已有的“明月”约束求解工具中,采用随机产生的约束问题来测试各个弧相容算法及其与多种智能回溯算法相结合的混合算法,实验表明,我们所提出的算法提高了“明月”约束求解工具的性能。

论文目录

• 内容提要
• 第1章 绪论
• 1.1 引言
• 1.2 研究背景与现状
• 1.3 约束满足问题
• 1.3.1 经典约束满足问题
• 1.3.2 软约束满足问题
• 1.3.3 随机约束满足问题
• 1.4 约束求解技术
• 1.4.1 基本搜索方法
• 1.4.2 约束推理与约束传播
• 1.5 本文工作
• 第2章 弧相容性算法与性能比较
• 2.1 引言
• 2.2 基本概念
• 2.3 算法与实现
• 2.3.1 AC-1 和AC-3
• 2.3.2 AC-4
• 2.3.3 AC-6
• 2.3.4 AC-7
• 2.3.5 AC-2000，AC-2001，AC-3.1
• 2.3.6 AC-3.2，AC-3.3
• 2.4 实验结果
• 2.5 小结
• 第3章 参数化弧相容性算法
• 3.1 引言
• 3.2 弧相容算法
• 3.3 参数化弧相容传播算法
• 3.4 实验结果
• 3.5 小结
• 第4章 改进的双向 singleton 弧相容算法
• 4.1 引言
• 4.2 相容性技术
• 4.3 BiSAC-2 算法
• 4.4 实验结果
• 4.5 小结
• 第5章 并发搜索中的约束传播算法
• 5.1 分布式约束满足求解
• 5.2 动态变量次序启发
• 5.3 基于动态变量次序的并发搜索
• 5.3.1 分布式动态变量次序计算
• 5.3.2 改进的并发搜索算法
• 5.4 实验结果
• 5.5 小结
• 第6章 系统实现
• 6.1 “明月”约束求解工具
• 6.2 问题生成
• 6.3 算法实现
• 6.4 实验结果
• 6.4.1 弧相容性算法的测试
• 6.4.2 混合算法的测试
• 第7章 结束语
• 7.1 总结
• 7.2 未来工作
• 参考文献
• 在读期间发表的论文和参与的项目
• 致谢
• 摘要
• ABSTRACT