Chap10 局部搜索

1、学习目标

局部搜索不从全局一次性构造答案，而是从一个可行解出发，通过局部修改不断改进。它适合解空间巨大、精确算法困难、但局部改进容易定义的问题。

从任意可行解 S 开始
while 存在邻居 S' 比 S 更好:
    S = S'
return S

要定义三件事：

局部搜索的优点是简单、通用；缺点是可能停在局部最优，而不是全局最优。

可以把所有可行解想象成山地地形：

1
2
3

点 = 一个可行解
高度 = 目标函数值
边 = 两个解互为邻居

最大化问题中，局部搜索像爬山：只要附近有更高的点就走过去。最后停在一个周围都不更高的位置。

局部最优不一定全局最优：

1	附近没有更好解，不代表远处没有更好解。

给定无向图，把顶点分成两组，使跨组边数量最大。

局部搜索策略：

1 2	while exists v with gain(v) > 0: move v to the other side

每次翻转至少让割边数增加 1，因此在无权图中一定终止。

当局部搜索停止时，每个顶点跨组边数不少于同组边数。否则翻转它会增加割。

把所有顶点的不等式加起来：

1	跨组贡献 >= 同组贡献

因此当前割边数至少占总边数一半。

最优割最多是所有边，所以局部最优解至少是最优值的 1/2：

1	cut >= OPT / 2

这是一个简单的 2-近似。

局部搜索未必总是快。即使每次都改善，改善次数也可能很多。

常见处理：

在博弈中，Nash 均衡指每个参与者在其他人策略不变时，都没有动力单方面改变策略。

这和局部最优很像：

1 2	局部最优：没有一个局部改动能改善目标函数 Nash 均衡：没有一个玩家单方面改策略能改善自己的收益

很多系统行为可以看成“个体局部优化”产生的稳定状态。

稳定性代价关注：

1	最好的 Nash 均衡 / 全局最优

无政府代价关注：

1	最坏的 Nash 均衡 / 全局最优

它们衡量个体理性和整体效率之间的差距。比如交通路由中，每个人选自己最快路线，整体可能比统一调度更拥堵。