局部搜索近似 | Codeboy's Blog

形式陈述

三个必须固定的对象

对优化问题，局部搜索先定义有限非空的可行解集合 $\mathcal F$ 、目标函数 $C(S)$ 和邻域 $N(S)$ 。最小化问题中的 improving move 是满足

S'\in N(S),\qquad C(S')<C(S)

的替换。算法从一个可行解出发反复采用改善移动，直到不存在移动；终点只是相对所选邻域的局部最优。

近似算法还必须给出如何搜索邻域与何时停止。有限状态和严格改善保证不会重访同一解，因而最终停止；但可行解可能有指数多个。若邻域检查本身困难，或算法经历指数多个微小改善，终止性仍不足以构成多项式时间保证。

metric k-median 的 p-swap

给定有限候选设施 $F\ne\varnothing$ 、有限客户集 $D$ ，以及 $F\cup D$ 上的度量 $d$ 。取整数 $1\le k\le|F|$ 和 $p\ge1$ ，解 $S\subseteq F$ 满足 $|S|=k$ ，费用为

C(S)=\sum_{j\in D}d(j,S).

客户为空时费用为零，任意 $k$ 个设施都最优。非空情形中，一个 $p$ -swap 从 $S$ 中关闭至多 $p$ 个设施，同时从 $F\setminus S$ 开启同样多个设施，再把每个客户分配给最近的开放设施。

当 $p$ 是常数，可以枚举 $|F|^{O(p)}$ 个交换并计算新费用。邻域越大，单轮越贵，但局部最优条件更强。经典分析表明，metric k-median 的 $p$ -swap 局部最优可达到

3+\frac{2}{p}

的近似比，即下述精确局部最优定理；多项式终止版本会保留额外的阈值损失。

一次交换如何计算

设当前开放设施为 $S=\{x,y\}$ ，考虑关闭 $x$ 、开启 $z$ 。原先由 $x$ 服务的客户要比较到 $z$ 与仍开放的 $y$ 的距离；原先由 $y$ 服务的客户也可能改投更近的 $z$ 。因此交换增量是所有客户新旧最近距离之差，不能只统计 $x$ 的旧客户。

实现可为每个客户保存最近与次近的当前设施。关闭一个设施时，受影响客户先退到次近候选，再与新设施比较；这加速 1-swap，但对一般 $p$ -swap 仍需处理多个同时关闭设施。

从局部不等式到近似比

令 $O$ 为大小 $k$ 的最优设施集。对每个客户 $j$ ，记最近的当前设施为 $s(j)$ 、最近的最优设施为 $o(j)$ ，距离分别为 $a_j,b_j$ 。把每个 $o\in O$ 映到 $S$ 中最近的设施 $\phi(o)$ ；若 $o\in S$ ，则固定 $\phi(o)=o$ 。由最近性和三角不等式，

d(j,\phi(o(j)))\le b_j+d(o(j),s(j))\le a_j+2b_j.

因此关闭 $s(j)$ 后，只要 $\phi(o(j))$ 仍开放，就能以至多 $2b_j$ 的额外成本安置客户。关键是构造每次都满足这一条件的交换族。

把 $S$ 中至少接收一个 $O$ 设施的点称为中心，其余称为零入度点。若中心 $s_i$ 接收 $t_i$ 个最优设施，令 $O_i=\phi^{-1}(s_i)$ ，并给它配上 $t_i-1$ 个尚未分配的零入度点，形成 $S_i$ 。因为 $\sum_i t_i=k$ ，零入度点的总数正好是 $\sum_i(t_i-1)$ ，所以能得到 $|S_i|=|O_i|=t_i$ 的配对分组。各 $S_i$ 中只有 $s_i$ 有正入度。

若 $t_i\le p$ ，取交换 $S_i\mapsto O_i$ ，权重为 $1$ ；两侧的公共设施保留，真正关闭和开启的数量相同且不超过 $p$ 。
若 $t_i>p$ ，对每个 $o\in O_i\setminus S$ 和每个零入度点 $z\in S_i\setminus\{s_i\}$ ，取单交换 $z\mapsto o$ ，权重为 $1/(t_i-1)$ 。若 $o\in O_i\cap S$ ，它只能是 $s_i$ ；为它使用总权重为 $1$ 的“不移动”不等式，设施始终开放。

每个最优设施因此作为客户直接重分配的目的地出现总权重 $1$ ；每个当前设施被关闭的总权重至多 $1+1/p$ 。小组交换中，被关闭中心的全部原像都同时开启；大组交换只关闭零入度点。所以若客户的 $o(j)$ 未在本次直接接收客户， $\phi(o(j))$ 就仍开放。将直接重分配的客户送到 $o(j)$ ，把其余失去设施的客户送到 $\phi(o(j))$ ，其余客户原地保留，即得到每个交换的合法分配。

局部最优保证真实交换的最优分配费用不下降，因此这个指定分配的费用变化也非负；不移动不等式同样成立，因为已经开放的 $o(j)$ 不可能比当前最近设施更近。把全部不等式按上述权重相加，直接分配项恰为 $\sum_j(b_j-a_j)$ ，绕行项至多 $2(1+1/p)\sum_jb_j$ ，得到

0\le C(O)-C(S)+2(1+1/p)C(O),\qquad C(S)\le(3+2/p)C(O).

这个证明也覆盖 $S\cap O\ne\varnothing$ ；对已经共有的设施使用保留或不移动分支，避免把“开启已有设施、关闭另一设施”误当成维持大小 $k$ 的交换。

直觉

局部最优只排除了邻域中看得见的改善，因此质量完全取决于邻域能否用一组小交换覆盖全局最优与当前解的差异。近似证明把每个禁止的改善写成不等式，再按结构化权重相加；算法停下本身并不会自动产生任何全局比率。

例子与边界

局部最优可以很差

局部最优的质量完全由邻域决定。考虑四个可行状态 $00,10,01,11$ ，邻域只允许翻转一个 bit，费用依次为

C(00)=2,\quad C(10)=3,\quad C(01)=3,\quad C(11)=0.

从 $00$ 出发，两个邻居都更差，因此算法停止在费用 2；全局最优 $11$ 的费用为 0，却需要同时翻转两位才能到达。

这个具体陷阱不是 metric k-median 的近似下界，而是说明“严格改善直到停止”本身不携带任何近似比。k-median 的保证来自度量结构与 p-swap 交换论证，不来自 local optimum 这个名称。

多项式终止

若目标值是非负、范围多项式有界的整数，每次严格改善至少下降 $1$ ，直接累加下降量就能控制迭代数。这里跟踪的是优化目标的下降，与数据结构势能法重分摊每步真实工作量的接口不同。

对上面的 $k$ -median，取有理阈值 $0<\eta<1$ ，只在当前费用为正且某交换满足

C(S')\le(1-\eta/k)C(S)

时移动；费用为零立即停止。上述证明的交换总权重至多 $k$ ，停止时把每个“变化非负”放宽为“变化至少 $-\eta C(S)/k$ ”，累加便得到

(1-\eta)C(S)\le(3+2/p)C(O).

这是明确的 $(3+2/p)/(1-\eta)$ 保证，固定 $p$ 时随 $\eta\downarrow0$ 逼近精确局部最优的比率。

若所有距离都是以二进制给出的非负有理数，令 $B>0$ 为初始费用， $\lambda>0$ 为输入中的最小正距离。每个正费用至少为 $\lambda$ ；因此正费用移动次数至多 $O((k/\eta)\log(B/\lambda))$ ，另加可能到零的一步。若没有正距离或初始费用已经为零，直接处理零费用分支。位长控制 $\log(B/\lambda)$ ，固定 $p$ 时每轮枚举 $|F|^{O(p)}$ 个交换、精确计算客户最近距离，便给出关于输入位长和 $1/\eta$ 的多项式时间。任意实数 oracle 模型若未给正费用下界，就不能据此声称同样的编码时间界。

推论与应用

facility location 与适用边界

非容量 facility location 还要支付设施开启费，邻域可包含 open、close 与 swap。客户重分配节省必须与新增开启费共同比较；把 k-median 的“始终开放恰好 $k$ 个”约束直接搬来会漏掉费用项。

局部搜索适合能快速评价移动、又能由局部交换覆盖全局差异的问题。容量约束、非度量距离或大 $p$ 会让邻域搜索和可行性显著变难。随机选邻居、接受变差移动的模拟退火是另一种启发式，不自动继承这里的近似定理。

参考资料

Vijay Arya、Naveen Garg、Rohit Khandekar、Adam Meyerson、Kamesh Munagala、Vinayaka Pandit，Local Search Heuristics for k-Median and Facility Location Problems，SIAM Journal on Computing 33(3)，2004，§2 的阈值终止与 §§3.3–3.4 的加权多交换分析。本页用最近设施映射写出交换族；一交换的这一写法另见下列教材 §9.2。
David P. Williamson、David B. Shmoys，The Design of Approximation Algorithms，Cambridge University Press，2011，§9.2，Theorems 9.6–9.7：最近设施映射、合法重分配与五近似，以及足够大改善步骤。
Emile Aarts and Jan Karel Lenstra (eds.), Local Search in Combinatorial Optimization, Princeton University Press, 1997.

形式陈述 ​

三个必须固定的对象 ​

metric k-median 的 p-swap ​

一次交换如何计算 ​

从局部不等式到近似比 ​

局部最优可以很差 ​

多项式终止 ​

facility location 与适用边界 ​

反向链接