Lesson12：局部搜索

是一种近似算法。

分为两部分"Local"与"search"。

寻找邻居中比自己更好的点，而不总是全局最优解。类似贪心。

下一个是谁？

困难点在于步长太小会导致计算量太大，步长太大可能错过更优解。

顶点覆盖问题

顶点覆盖问题（Vertex Cover Problem）： 给定一个无向图 \(G=(V,E)\)，要求找出一个最小的顶点子集 \(S⊆V\)，使得对于图中的每条边 \((u,v)∈E\)，至少有一个端点 \(u\) 或 \(v\) 在子集 \(S\) 中。

起始为随机解显然并不好，因为不一定是可行解，我们直接从全集开始，然后将-1点作为邻居。

Case0不作讨论。

Case1：如果-1点减掉的是中心点，那么就将收敛到局部最优，因为全局最优是仅中心点。

Case2：这个样例极值点更多，删掉任意一个红色点都无法达到最优。

思考：上面的算法是不能回溯的，那如果加以回溯呢？

改变在于，从挑选最优邻居的算法变为随机挑选邻居，如果这个邻居没能更好还是有一定概率跳进该情况。

上面的\(-\triangle cost\)表示跳转的点与当前点的差值，差值如果太大，这个值应该小，以实现跳到坏情况的概率更低。下面叫做超参，人为设置。

我们希望超参/概率会变化，肯定希望是开始大一点好，后面小一点好(因为越到后面越可能接近优解？)，也就是开始的超参小一点，后面大一点好。这叫做退火算法(想象巧克力融化，前面快后面慢)。

Hopfield网络

题目描述：就是给定一个无向图，每个边存在一个\(w\)值，可正可负，如果是正的就希望两个点处于不同状态，负的反之(状态可以理解为一个二元值)，权值的绝对值大小表示希望的渴望程度。

我们知道，假设一个全为正值边的三角形，我们必然不可能满足条件输出一个恰当的三点状态。

定义：一个边是好的，如果其\(w*s_u*s_v\)也就是权值乘两边状态小于0，反之则是坏的。

定义：一个点\(u\)是被满足的，如果与其相关的所有边的\(\sum_{incident}w*s_u*s_?\)小于等于0。

定义：一个图是稳定的，如果每个节点都是被满足的。

寻找稳定性图的方法：直观方法：直接全部赋1/-1，然后去随机反转一个点。

然而这样其实不太对，那么我们改为去反转未被满足的节点，会不会更好？

我们使用一个函数来度量是否变好了：

也就是将所有好边的边权和(绝对值)相加。

什么情况下一定是稳定的？那就是所有边的边权值都在该和里。

而且我们发现，反转一个不被满足的点，不管是不是让不被满足的点变多了，好边边权和都是增大的一个趋势。

还有一个之前没有解决的问题：是否会出现不停反转的情况？

显然是不会的，因为是有最大值的(所有边)，又每次都稳定增大，不可能出现无休止增长。

是一个非(伪)多项式时间复杂度的问题。

最大割问题

题目描述：给定无向图，边有边权，然后给所有点染成不同颜色，希望不同颜色的点的边的边权和最大。

把所有边都视为是正的，目的改为求好边的边权和，就转换为了Hopfield网络问题。

实际是一个近似问题，因为不可能出现完美解，近似比不会大于2。

跳转的优化：

对于这个问题的贪心优化：

k-flip其本身意图是解决收敛慢的这个问题，但是我们如果尝试去尝试所有k反转的情况挑最好，那就是一个\(O(n^k)\)的问题，所以需要改变，我们改为一个点一个点的加入，每次选择当前情况能使目标函数最大的点(注意是as good as possible)进行反转，依次进行直到达到k次。