algorithm - 对于任何局部搜索算法，在邻域中搜索的一步是否总是可以在多项式时间内完成？

Question

既然找到一个局部最优解大概比找到一个最优解更容易，我们是否可以声称对于任何局部搜索算法，在邻域中搜索的一步总是可以在多项式时间内完成？

Answer 1

没有。搜索邻域的难易程度取决于邻域的定义方式。

想象一下 Max-2SAT 问题:令 U 为一组二进制变量 x_1 , ..., x_n 并令 C 为一组子句c 在 U 上。每个子句中的文字数最多为两个，子句c ∈ C 的权重w(c) 为正整数。解决方案是 x_1 , ..., x_n 的分配。如果至少有一个变量为 1，则子句满足。目的是找到一个分配，使满足子句的权重之和最大化。

令FLIP 为邻域结构，其中通过翻转一位x_i< 获得解s 的邻居r/em> 个 。该邻域具有多项式大小，可以在多项式时间内找到下一个最佳邻域。

设ALL 为包含U 所有可能解的邻域结构。该邻域的大小呈指数级增长，找到下一个最佳邻域(在本例中为全局最佳邻域)需要指数时间。局部搜索算法在一步后终止，所以它不是一个真正好的局部搜索算法，而是一个指数邻域函数。

还有更复杂的具有指数邻域函数的算法，例如 I.A.达维多夫，P.A.科诺诺娃，Yu.A.科切托夫，2014 年。他们在所有服务器上的所有可能的磁盘子集集合中搜索下一个具有混合整数程序的邻居，这些磁盘的可能邻居是指数级的。

如果你有一个局部搜索问题，你可以在多项式时间内产生一些解决方案，在多项式时间内计算解决方案的成本，并在多项式时间内找到最佳邻居，你的问题就在复杂性类 PLS 内(见“本地搜索有多简单？”作者:David S Johnson、Christos H Papadimitriou 和 Mihalis Yannakakis，1988 年)。