笔记人工智能一种现代方法第6章搜索树

搜索树在问题求解中的应用

6.1定义约束满足问题(CSP)

变量的集合表示为：X={X1, X2,..., Xn}

对应的取值范围定义为：D={D1, D2,..., Dn}

而约束条件则用符号C来表示

6.1.1地图着色问题

为确保相邻区域具有差异化的色彩表现，可将该问题抽象为约束满足问题（CSP）进行处理。

传统搜索方式仅能判断：当前解是否符合目标要求？

在CSP框架下，一旦检测到局部赋值违反约束条件，即可即时进行剪枝操作，从而避免后续不必要的精细化处理。

6.1.2作业调度问题

过程约束：特定任务的执行需在其他相关任务之前予以完成

洗去约束：多个任务在时间安排上不得存在交叉或重叠的情况

6.1.3CSP的形式化

间断型、持续型、有限域型、无限域型

单变量限制、双变量限制、整体限制

任何有限域型的限制条件均可通过引入约束变量的方式转化为双变量限制

6.2约束传播：CSP中的推理

约束传播技术能够有效缩减变量的可行取值区间，该过程既可以与搜索算法交替执行，也可作为搜索操作之前的预处理阶段。其核心理念在于实现局部相容性。

6.2.1结点相容

当某一变量（即图中的一个结点）在自身的值域范围内，所有可能的取值均符合其对应的一元约束条件时，该变量可被称为结点相容。通过执行结点