学位论文 > 优秀研究生学位论文题录展示

约束相容性技术的研究

作　者: 杜会盈
导　师: 李占山
学　校: 吉林大学
专　业: 计算机软件与理论
关键词: 约束满足问题相容性技术求解算法启发式算法
分类号: TP181
类　型: 硕士论文
年　份: 2011年
下　载: 13次
引　用: 0次
阅　读: 论文下载

内容摘要

约束满足问题是人工智能研究领域中的一个重要分支。现实世界中的许多问题都可以有效地模拟为约束满足问题,进而通过约束求解技术来解决。本文的主要研究内容包括：基于图分割技术和singleton弧相容技术的研究,提出了将图分割技术应用到多值传播的相容性算法SAC-MP*;通过对具有最优有时间复杂性的AC-4算法的研究,提出了基于其中的两个数据的启发式算法MSV(Max_Support Value)和KVV(Key_Value Value),并将其嵌入BT算法框架中,形成新的启发式求解算法BT-MSV和BT-KVV;通过对MAC算法的研究,为了充分利用MAC算法在初始化阶段中的信息和求解过程中维持完全弧相容的特点,提出了算法Revised MAC,通过构建一个新的数据结构来记录那些在之后的搜索传播过程中有用的信息,通过对信息的操作和传播,能够快速地发现当前变量所选值的可行性,从而减少问题的约束传播次数,提高算法求解效率。对于上述提出的算法,分别证明了其空间复杂性和最坏时间复杂度。对所有的改进算法和技术,都通过实现、测试和比较,结果表明提出的新算法都明显优于之前的和当前流行的算法。

全文目录

提要  4-5
摘要  5-6
Abstract  6-10
第1章绪论  10-12
  1.1 研究背景和现状  10-11
  1.2 本文主要工作  11-12
第2章约束满足、求解算法和相容性技术  12-18
  2.1 约束满足  12-13
    2.1.1 随机约束满足问题  13
  2.2 约束求解算法  13-14
    2.2.1 基于回溯的搜索(BT-backtracking algorithm)  13
    2.2.2 相容性算法  13-14
  2.3 相容性技术  14-18
    2.3.1 弧相容性技术  14-16
    2.3.2 singleton弧相容性技术  16-18
第3章基于AC-4算法的启发式求解算法  18-29
  3.1 启发式求解的特性  18
  3.2 基于AC-4算法的启发式求解算法  18-29
    3.2.1 最大支持数启发式MSV(Max_Support Valaue)  18-24
      3.2.1.1 最大支持数启发式思想  18-21
      3.2.1.2 实验结果  21-24
    3.2.2 关键值启发式KVV(Max_Support Valaue)  24-29
      3.2.2.1 关键值启发式思想  24-26
      3.2.2.2 实验结果  26-29
第4章图分割在singleton弧相容算法中的应用  29-36
  4.1 图分割技术  29-30
  4.2 多值传播算法  30-31
  4.3 图分割技术与K值的确定  31-32
  4.4 实验结果  32-36
第5章 MAC算法的优化  36-44
  5.1 MAC算法的简介  36
  5.2 MAC算法的简介  36-39
  5.3 Revised MAC算法的复杂性和正确性分析  39-41
  5.4 实验结果  41-44
第6章总结与展望  44-45
参考文献  45-48
作者简介及在学期间所取得的科研成果  48-49
致谢  49

约束相容性技术的研究

内容摘要

全文目录

相似论文