CSP中的约束传播策略及启发式的研究

发布时间：2020-03-19 06:14

【摘要】：约束满足问题(Constraint Satisfaction Problem,CSP)是人工智能领域的一个重要分支,也是当前国际上人工智能领域研究的热点。CSP可以模拟各种复杂的组合问题,涵盖人工智能、运筹学、编程语言、数据库等广泛的技术。CSP现已成功应用于资源分配,生产调度,产品配置,物流规划,路由选择,生物信息学等领域。解决约束满足问题(CSP)首先要进行约束建模。建模过程是通过指定变量、论域和约束来完成的。然后再使用约束求解器进行求解。约束求解器通常是启发式引导回溯搜索和推理方法的组合,通过将值分配给满足给定约束集的给定变量集来寻找解。回溯搜索算法是解决CSP问题的主要搜索算法。在使用回溯搜索来解决CSP问题时,必须对哪个变量进行分支或实例化以及将哪个值赋予变量等问题进行一系列的决策,这些决策过程称为变量和值排序。现有的研究已经表明,对于许多问题,变量和值排序的选择可以极大地影响CSP实例的求解效率。本文对目前主流的变量和值排序的启发式方法进行了详细的研究。在回溯搜索过程中应用约束传播(constraint propagation)是求解约束满足问题的最重要技术之一。弧相容是约束传播技术的核心,许多的约束传播算法都是围绕弧相容展开的。弧相容是最基本和最著名的约束传播算法,它要求约束网络的每个论域值都可以在约束中找到支持。现在已经提出了许多AC算法。在众多AC算法中,粗粒度的AC-3算法由于其一般性和简便性已经成为当今用途最广泛的弧相容算法。为了建立AC,AC-3算法保留了需要修正的元素列表,并对元素进行连续修正。AC-3算法在AC过程中可以采用不同的传播策略,它有三种经典的变体,分别对应的是面向弧的、面向变量的和面向约束的。对AC-3的三种经典变体,有不同的revision启发式算法,这些revision启发式方法也是基于“失败优先原则(fail-first principle)”。在搜索期间应用AC时对revision表进行排序,可以显著的提高AC-3算法的性能。本文对AC-3的三种经典变体及应用在它们上的revision启发式算法进行了分析和研究,并在此基础上提出了一种新的面向变量的传播策略,新的传播策略也维持了一个变量列表,这个列表需要在建立AC时进行修正。它将传播过程分解为两个独立的阶段。本文将展示它如何减少revision和列表操作的次数。在实验中,将revision启发式应用于这种新的面向变量的传播策略,并将它与现有最有效的传播策略进行比较。来自各种结构性和随机问题的结果表明,新提出的传播策略减少了revision次数并加速了搜索过程。它加快了AC的执行,优于现有的传播策略。
【图文】：

地图,地图着色,澳大利亚,变量

图 2.1 澳大利亚地图着色图着色示例可以由元组(X,D,C)定义，其中：NT, Q, SA, NSW, V, T 表示的是变量，代表地图 green, blue}，表示每个变量的论域；NT, WA≠SA, NT≠SA, NT≠Q, SA≠Q, SA≠NSW 表示的是任意两个相邻地区之间的约束。的赋值为：{WA=red, NT=green, SA=blue, Q仅涉及一个变量（例如 x>5）的约束，二元约个变量。通常，非二元约束包括 n 个变量，，也 + x3 + x4 > 0 称为四元约束）。一元 CSP 仅包含和二元约束。在一般情况下，非二元或者说 n的约束。地图着色问题是二元 CSP。

约束网络,赋值,变量选择,候选解

图 2.2 将地图着色问题转化为约束网络量进行的完整的赋值，要求这些赋值必CSP 是 NP-hard 问题，那么就意味着在可能存在。其最坏情况下的时间复杂度算法算法通过为变量选择值来构建出部分解。所以，当搜索树访问到死节点时，就过程是系统式的，可以保证所有可能的和逐步测试所有候选解的方案上进行的这个选择是否满足所有的约束条件，而
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18

【相似文献】