局部搜索

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

顶点覆盖问题

给定一个无向图 $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$$

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