第6章 不完备算法

简介

不完备算法：不能保证程序会结束或结束时输出正确的结果

结果：可满足的赋值或失败

随机本地搜索(SLS)：调整变量赋值，使得满足的子句最多

贪婪搜索(GSAT)

• 策略：反转使得不满足的子句数最少的变量

随机游走(Walksat)

• 策略：若反转变量不会使得已满足的子句变为不满足，反转；否则：
  • 以概率随机游走：反转随机变量
  • 以概率贪婪：反转使得已满足的子句变为不满足数量最少的变量

基础算法扩展

• 子句权重
• 动态化参数（随机游走、字句权重）
• 基于离散拉格朗日的字句权重

本地搜索算法的评估方法：

• 深度(Depth)：能否快速满足较多的子句
• 机动性(Mobility)：能否快速转移搜索空间
• 覆盖率(Coverage)：对整个搜索空间的探索程度

离散拉格朗日方法

引入拉格朗日乘数：

鞍点：

• 局部最小，局部最大

结论：如果存在鞍点，那么​是局部最小解。

差分梯度：​，且最多一个非零元素

• 对于的所有邻居（包括自身）

迭代算法：其中

后续问题：对于一些问题（奇偶校验、汉诺塔），该方法会掉入陷阱(trap)

解决方法：将最近访问过的点作为惩罚项加入拉格朗日函数

随机k-SAT问题

每个子句：随机从n个变量中选择k个，正负概率0.5

衡量指标：密度（字句数量/变量数量）

问题难度：简单-困难-简单

调查传播(Survey Propagation)

近线性时间内成功求解一百万变量的随机3-SAT问题

• 启发赋值算法，但几乎不出错

可参考第22章详细介绍