局部搜索

只要给出搜索目标即可，不需要记录搜索过程的每个步骤。

常用的局部搜索方式就是在给定的一系列可能目标候选中进行选择，按照某个标准（称为搜索函数search function）挑选具有最大值/最小值的候选作为目标。

常见局部搜索算法：

1. 爬山法
2. 模拟退火算法
3. 禁忌搜索
4. 反应式搜索

爬山法

当问题规模很大或者很复杂以至于不可能考虑其目标的全部可能性时，以解决寻优问题为目标的优化算法就转变为局部搜索。

优化算法的一些典型例子包括：

1. 图顶点覆盖问题
2. 旅行商问题

局部搜索最终获得的最优目标通常只是局部最优，因此，局部搜索算法的终止条件一般有2种选择：

1. 时间限制
2. 搜索获得的当前目标不能再改善

![[Pasted image 20220313173558.png]]

该算法的思想很简单，是一种典型的贪心算法，即从当前状态触发，向相邻状态试探，只要发现某个相邻状态比当前状态好，就转入那个相邻状态，并放弃当前状态。

过程

局部变量：当前状态节点C，邻居状态节点N

1. 生成问题的初始状态->C;
2. repeat
3. 生成C的所有后续节点
4. 根据某种标准V，具有最高值的后续节点->N
5. if V(C) <= V(N), then 返回C退出；## 此时没有找到更好状态