Local Search¶
1 Vertex Cover Problem¶
Metropolis 算法：该算法与梯度下降法最大的不同在于，如果新的顶点覆盖集合\(S'\)的成本更大，不会立马被放弃而是以\(e^{\frac{\Delta cost}{kT}}\)
Info
- 匹配问题： 边集E的一个子集，这个子集中的任意两边没有共同的顶点
- 柯尼希定理： 在任意二分图中，最大匹配的边数等于最小覆盖的顶点数
2 Hopfield Neural Networks¶
状态翻转算法(state-flipping)算法：
Text Only
只要这个布局不是稳定的，算法就会找出不满意点并翻转它的状态，这样就能使其变成满意点
ConfigType State_flipping() {
Start from an arbitrary configuration S;
while (!IsStable(S)) {
u = GetUnsatisfied(S);
s_u = -s_u;
}
return S;
}
该算法在之多\(W=\sum|w_e|\)次迭代后终止
3 Maximum Cut Problem¶
给定一张无向图，每条边都有正整数权重，找到一种顶点划分，值得割之间所有边的权重和最大
局部最优的划分至少是全局最优的一半，状态翻转算法在本题是一种2-近似算法
-
能否在多项式时间内得到结果呢？
- 一种策略是：如果算法找不到有“足够大”提升的解，那么算法就会终止迭代，称这种算法为大提升翻转(big-improvement-flip)。具体来说，该算法挑选那些能够提升至少\(\dfrac{2\varepsilon}{|V|}w(A, B)\)割值的顶点来翻转
- 相关结论：
-
算法中止后会返回一个割集\((A, B)\)，满足：\((2 + \varepsilon)w(A, B) \ge w(A^_, B^_)\)
- 因此该算法是一个\((2 + \varepsilon)\)-近似算法 - 该算法能够在至多\(O(\dfrac{n}{\varepsilon} \log W)\)次翻转后终止
-
-
是否存在一种更好的「局部」？
- 一个好的「局部」需要满足：
- 解的邻居需要足够大，使得算法不会陷入局部最优解而“出不来”
- 但解的邻居也不能太大，因为我们希望能够在有限的步数内，在邻居集中高效地寻找最优解
- 改进方法：\(k\)翻转算法（一种启发式算法），时间复杂度为\(\Theta(n^k)\)，下面来看一下执行步骤：
- 第1步：对整个顶点集使用状态翻转算法（单顶点的翻转），此时得到的最优解为\((A_1, B_1)\)，被翻转的那个顶点记为\(v_1\)
- 时间复杂度：\(O(n)\)
- 第k步：对尚未翻转过的顶点集使用状态翻转算法，此时得到的最优解为\((A_k, B_k)\)，被翻转的顶点有\(v_1, \dots, v_k\)
- 时间复杂度：\(O(n - k + 1)\)
- 第n步：\((A_n, b_n) = (B, A)\)
- 因此，划分\((A, B)\)的邻居集为\({(A_1, B_1), \dots, (A_{n - 1}, B_{n - 1})}\)，时间复杂度为\(O(n^2)\)
- 第1步：对整个顶点集使用状态翻转算法（单顶点的翻转），此时得到的最优解为\((A_1, B_1)\)，被翻转的那个顶点记为\(v_1\)
- 一个好的「局部」需要满足：