这一讲主要讲优化
本地搜索 Local Search
特点
相比于先前学的一些搜索，本地搜索有一些特点：
- 仅维护当前节点（而非更新整个搜索树之类的）
- 基于相邻节点搜索
- 不一定找到全局最优，而是局部最优；可以节省计算资源
- 主要目标并非路径搜索，而是优化目标函数
术语
- 目标函数：把方案的 value 最大化的一个函数
- 成本函数：把方案 cost 最小化的一个函数
- 当前状态
- 相邻节点：当前状态可以一步转换的状态
爬山算法 Hill Climbing
这里的爬山中的“山”，其实和深度学习中 error space 很像
伪代码
爬山算法相对比较短视，因此常常只能找到局部最优
局部和全局的最值
由于局部搜索只能了解当前状态和相邻节点的值，因此算法的停止条件仅能通过比较 current 与 neighbor 的值来实现
这也是为什么被卡在 local minima 的原因
爬山算法的变体 Hill Climbing Variants
- 最陡的爬坡 Steepest-ascent : 选择值最高的邻居
- 随机指标 Stochastic ：从值较高的邻居中随机选择。这样做，我们选择高于我们值的任何方向。
- 选第一个 First-choice ：选择第一个值较高的邻居。
- 随机重启 Random-restart：多次进行爬山。每次，从一个随机状态开始。比较每次试验的最大值，并从中选择最高的。
- 本地集束搜索 Local Beam Search：选择 k 个最高值的邻居。这与大多数本地搜索算法不同，因为它使用多个节点进行搜索，而不仅仅是一个节点。
模拟退火 Simulated Annealing
为了解决爬山算法中，卡在 local minima 的问题，这里允许卡住时可以移动自身，跳出局部最小
“退火”的由来
这里主要指的是加热金属使其缓慢冷却
算法从“高温”开始，在此时允许节点更频繁地自由移动，方便跳出最初的局部最低
随着温度降低，进入“低温”时，此时大概进入了更符合条件的局部最低，此时乱动的频率会降低
伪代码
首先，这里有一个温度 T，接受 t 来返回一个“温度”
这里的 t 是控制降温的，这里使用 for 来进行遍历
其次，这里的 neighbor 是随机选取的
然后判断 neighbor 是否最优，然后有概率地选择如何更新节点
，这里 delta E 如果是负值，则说明 neighbor 的值更差，且如果 Delta E 越小，则概率函数越趋近于 0；T 越高，概率越趋近于 1
旅行商问题 Traveling Salesman Problem
这里的任务是连接所有点同时选择最短的可能距离
线性规划 Linear Programming
内容
- 成本函数：c₁x₁ + c₂x₂ + … + cₙxₙ。在这里，每个 x₋是一个变量，它与某个成本 c₋相关联。
- 加和限制：和小于或等于某个值（a₁x₁ + a₂x₂ + … + aₙxₙ ≤ b）或恰好等于这个值（a₁x₁ + a₂x₂ + … + aₙxₙ = b）。在这种情况下，x 是一个变量，a 是与之相关的某种资源，b 是我们可以为这个问题投入的资源量。
- 变量值域：（例如，一个变量不能为负）的形式为 lᵢ ≤ xᵢ ≤ uᵢ。
约束满足 Constraint Satisfaction
需要变量在满足某些条件的情况下被赋值的一类问题
特性
- 变量集（x₁, x₂, …, xₙ）
- 每个变量的域集合 {D₁, D₂, …, Dₙ}
- 约束集 C
术语
- A Hard Constraint is a constraint that must be satisfied in a correct solution.
- A Soft Constraint is a constraint that expresses which solution is preferred over others.
- A Unary Constraint is a constraint that involves only one variable. In our example, a unary constraint would be saying that course A can’t have an exam on Monday {A ≠ Monday}.
- A Binary Constraint is a constraint that involves two variables. This is the type of constraint that we used in the example above, saying that some two courses can’t have the same value {A ≠ B}.
节点一致性 Node Consistency
节点一致性是指变量域中所有值都满足变量的单一约束
弧一致性 Arc Consistency
弧 在这里指的就是 图中的边
一个变量的域中的所有值都满足该变量的二元约束
换句话说，为了使 X 相对于 Y 弧一致，从 X 的域中移除元素，直到 X 的每个选择都有一个可能的 Y 选择。
伪代码
使得 X Y 弧一致
AC - 3 算法
适用于整个问题弧一致
这里相当于调用 Revise 函数，通过 queue 的数据结构进行遍历实现
此算法将问题中的所有弧添加到队列中。每次考虑一个弧时，它都会将其从队列中移除。然后，它运行 Revise 算法以查看此弧是否一致。如果进行了更改以使其一致，则需要进一步的操作。如果 X 的结果域为空，则意味着此约束满足问题不可解（因为 X 无法取任何值，使得 Y 在给定约束的情况下可以取任何值）。如果在上一步中认为问题不可解，那么由于 X 的域已更改，我们需要查看与 X 关联的所有弧是否仍然一致。也就是说，我们取 X 的所有邻居（除了 Y），并将它们与 X 之间的弧添加到队列中。然而，如果 Revise 算法返回 false，表示域没有更改，我们只需继续考虑其他弧。
搜索问题视角下的限制问题
- Initial state: empty assignment (all variables don’t have any values assigned to them).
- Actions: add a {variable = value} to assignment; that is, give some variable a value.
- Transition model: shows how adding the assignment changes the assignment. There is not much depth to this: the transition model returns the state that includes the assignment following the latest action.
- Goal test: check if all variables are assigned a value and all constraints are satisfied.
- Path cost function: all paths have the same cost. As we mentioned earlier, as opposed to typical search problems, optimization problems care about the solution and not the route to the solution.
但是把限制问题当做搜索问题处理，效率非常低。通过利用限制问题的结构，可以高效解决
回溯搜索 Backtracking Search
一种考虑约束满足搜索问题结构的搜索算法
伪代码
- 检查是否完成
- 选择还没赋值的变量
- 遍历所有值
- 判断值是否符合条件
- 添加到任务中，用回溯再查一下
- 可以，则返回结果
- 不行，则移除刚才的赋值
- 都不行，则返回失败
推理 Inference
维护弧一致性算法：在回溯的每次赋值后强制进行弧一致性
伪代码
其中，
Inference 函数运行 AC-3算法这里的 AC - 3 算法主要是用来砍掉一些不符合限制的节点的，可以节省一些空间，提升计算效率
最小剩余值 Minimum Remaining Values (MRV)
原有的回溯算法仍存在问题：对于限制较多、取值较少的变量，后赋值会导致冲突很多，造成深度回溯，有很大的浪费
因此我们选择优先赋值取值空间较小的变量，以便尽早发现冲突
