在很多问题中，问题的解和目标路径并不相关，达到解的路径可能有多条。
局部搜索：每次从当前状态出发，只移动到与之相邻的状态。
- 一般不保留搜索的路径
- 只占有很少内存，可以在很大状态空间内找到合理的解
- 类比：在地形图中行走找到最低谷/最高点
- 常见算法：爬山算法、模拟退火算法、遗传算法
爬山算法
基本思想：局部贪心。每次向函数值增加的方向连续移动，最终找到峰值即可最佳解决方案。
- 只保留当前状态的描述，以及函数值。
- 容易陷入局部最优解、鞍部、平摊区域
爬山算法的变种：
- 随机爬山法：它在上山移动中随机地选择下一步；选择的概率随着上山移动的陡峭程度而变化。
- 首选爬山法：在实现随机爬山法的基础上，采用的方式是随机地生成后继节点直到生成一个优于当前节点的后继。
- 随机重新开始爬山法：随机生成多个初始状态，进行一系列爬山法搜索。这时算法是完备的概率接近1。
模拟退火算法
模拟退火算法：采用类似于物理退火的过程，先以较大步长行走，然后逐渐减少步长，最终达到物理基态。本质是通过温度来控制算法接受劣解的概率，以有效地跳出局部最小。
Metropolis 准则：以概率接受新状态。我们记 $\displaystyle p = \exp \left(-\frac{E_j - E_i}{k_bT}\right)$，并以 $p$ 的概率接受新状态。那么在高温下，
