局部搜索

局部搜索会在当前解的邻域内搜索更好的解。局部搜索的目标是找到一个局部最优解，而不是全局最优解。

顶点覆盖问题

给定一个无向图 \(G = (V, E)\)，我们希望找到一个最小的顶点集合 \(S \subseteq V\)，使得对于每一条边 \((u, v) \in E\)，至少有一个顶点 \(u\) 或 \(v\) 属于 \(S\)。

Hopfield 神经网络

给定一个带边权重的图 \(G = (V, E)\)，每个顶点可以有 \(\pm 1\) 两种状态。对于每一条边 \(e = (u, v)\)，若 \(w_e < 0\)，则要求 \(u\) 和 \(v\) 有相同的状态；若 \(w_e > 0\)，则要求 \(u\) 和 \(v\) 有不同的状态。\(|w_e|\) 越大，要求越强烈。

我们说一条边 \(e\) 是好的，如果 \(w_e s_u s_v < 0\)，否则就是坏的；一个顶点 \(u\) 是被满足的，如果考虑所有与它相连的边，好的边的权重和大于等于坏的边的权重和，即

\[ \sum_{e=(u,v)\in E} w_e s_u s_v \le 0 \]

如果所有的点都被满足，则称该配置是稳定的。