约束传播

• 前向检验将信息从已分配的变量传播到未分配的变量，但不能为所有失败情景提供早期检测：NT和SA不能都是蓝色的！
• 约束传播在局部重复强制执行约束

弧约束

• 能使每个弧相容的最简单形式：

  • X→Y是可相容的，当：

    • 对于X的每个值x，Y都存在不与之冲突的取值y

  • 如果X丢失了一个值，则需要重新检查X的邻居

  • 弧相容比前向检验更早检测到可能失败的情景

  • 弧相容可以作为预处理运行，也可以在每次分配后运行

弧相容算法AC-3

• 时间复杂度：$O(n^2{d}^3)$

问题结构

• T和其它地区是独立的子问题，独立性可以简单地通过在约束图中寻找连通子图来确定。每个连通子图对应于一个子问题CSP
  

• 假设每个子问题有n个变量中的c个。最坏情况下的解决方案成本是$n/c\cdot d^c$，对n是线性的

• 例如，$n=80，d=2,c=20$

  • $2^{80}=40$亿年，1000万个节点/秒
  • $4\cdot 2^{20}=0.4$秒，1000万个节点/秒

• 任何一个树状结构的CSP问题可以在变量个数的线性时间内求解；

  如果约束图没有循环，CSP可以在$O(n\cdot d^2)$时间内解决。
  与一般CSP相比，最坏情况下的时间是$O(d^n)$
  

化简约束图-树结构

CSP问题的局部搜索

CSP的迭代算法

• 爬坡法、模拟退火法通常对 "完整 "状态进行工作，即所有变量均被分配
• 为了适用于CSP：
  • 允许有未满足的约束条件的状态
  • 操作者重新分配变量值
• 变量选择：随机选择任何有冲突的变量
• 通过最小冲突进行价值选择 启发式：
  • 选择会造成与其它变量的冲突最小的值
  • 在爬山法中，h(n)=被违反的约束总数

举例：4-Queens

• 状态： 4个皇后在4列（4⁴=256个状态）
• 行动：在列中移动皇后
• 目标测试：没有冲突
• 评价：h（n）=冲突次数
  
• 最小冲突启发式的性能
  • 给定随机初始状态，可以在几乎恒定的时间内解决任意n的高概率问题（如n=10,000,000）的n-queens。
  • 对于任何随机生成的CSP来说，除了在一个狭窄的比率范围内，似乎也是如此。
• 在3-SAT问题中也能取得很好的性能：

加速：模拟退火法

• 思路：通过允许一些 "坏 "的动作来逃避局部最大值，但要逐渐减少其频率

加速：最小最大优化(约束加权法)

• 

小结