PLS 问题的定义
一个 PLS 问题通常由以下几部分组成：
- 一个实例集： 定义了问题的不同实例。
- 一个解的集合： 对于每个实例，定义了可能解的集合。
- 一个邻域关系： 对于每个解，定义了其相邻解的集合。
- 一个价值函数 (或成本函数)： 为每个解分配一个值，表示该解的优劣。
- 一个邻居评估算法： 这是一个多项式时间算法，用于评估给定解的邻居，并确定是否存在更好的解。
PLS 问题的目标是找到一个局部最优解，即一个解，其邻居没有比它更好的解。 请注意，局部最优解不一定是全局最优解。
PLS 问题的性质
PLS 类的定义基于多项式时间计算能力。如果一个问题属于 PLS，那么以下操作必须在多项式时间内完成：
- 给定一个实例，产生一个初始解。
- 评估一个给定解的价值。
- 对于一个给定的解，评估其邻居，并找到一个价值更好的邻居（如果存在）。
由于这些操作都可以在多项式时间内完成，因此一个 PLS 问题可以通过局部搜索算法在多项式时间内进行，但无法保证找到全局最优解。 这也意味着局部搜索算法可能陷入局部最优状态。
PLS 问题的例子
PLS 包含了许多重要的优化问题，例如：
- 最大割 (Max-Cut): 给定一个图，找到一个将顶点分割成两部分的划分，使得跨越两部分的边的权重之和最大。
- 最小生成树 (Minimum Spanning Tree): 给定一个加权图，找到一个连接所有顶点的树，使得树的边的权重之和最小。
- 局部搜索版本的问题： 许多组合优化问题，如旅行商问题 (TSP)，都可以通过局部搜索算法来解决，从而构成 PLS 问题。
PLS 与其他复杂性类的关系
PLS 类与其他的复杂性类有密切的关系：
- P: P 代表可以在多项式时间内解决的问题。任何属于 P 的问题也都属于 PLS，因为对于 P 中的问题，可以在多项式时间内找到全局最优解，而局部最优解也满足此条件。
- NP: NP 代表可以在多项式时间内验证解的问题。PLS 属于 NP，因为可以多项式时间内验证一个解是否是局部最优解。然而，PLS 并不等同于 NP，因为找到局部最优解并不等同于验证解。
- PPAD: PLS 是 PPAD（Polynomial Parity Argument, Directed）类的一个子集。 PPAD 类包括一些比 PLS 更难的问题，这些问题也涉及寻找局部最优解，但解决它们的算法更复杂。
结论
PLS 是一种重要的计算复杂性类，它描述了寻找局部最优解的难度。许多实际的优化问题都属于 PLS 类，包括最大割、最小生成树等。 了解 PLS 的性质有助于我们更好地理解这些问题的计算复杂性，并设计有效的算法来解决它们。