动机
局部搜索算法从一个可行解出发,只要某个小改动能改进目标函数,就进行该改动。最终得到的解未必是全局最优的,但“不存在任何允许的改进”这一事实本身就可以推出有用的近似保证。最大割问题给出了一个特别清晰的例子:当没有任何顶点能通过移到另一侧而获益时,至少有一半的总边权被割开。
解的质量的证明与算法终止性的证明是两件独立的事。对于任意非负实数权重,严格改进规则之所以会终止,是因为割只有有限多个,但这一观察并不能给出关于输入长度的多项式界。对于整数权重,每次改进至少为一,从而得到以总权重的数值大小表示的界。
定义
定义 1.1.1
(割的值)
设 为有限无向无自环图,各边带有非负权重 。允许平行边,且平行边分别计数。割是 的一个划分,分成两侧。其值 是两个端点位于不同侧的边的权重之和。记 ,并令 为最大的割值。由于权重非负,。
定义 1.1.2
(顶点增益与单顶点局部最优)
对割中的顶点 ,记 为与其关联的被割边的总权重, 为与其关联的未被割边的总权重。单独把 移到另一侧,割值的变化量为 。若没有任何单次移动能严格增大割值,即对每个顶点都有 ,则称该割为单顶点局部最优。
定理
定理 1.1.3
(局部最优解的质量)
在有限无自环且权重非负的图中,每个单顶点局部最优割的值至少为 ,因而至少为 。
定理 1.1.4
(严格改进的终止性)
从任意割出发,反复移动满足 的顶点,必在某个单顶点局部最优割处终止。若所有边权均为非负整数,则至多进行 次移动。仅凭这一数值上的界,未必是关于二进制输入长度的多项式界。
证明思路或证明
证明
(双重计数,再由严格改进得到终止)
在局部最优解处,对所有顶点把 求和。每条被割的边在左边于其两个端点处各被计数一次,而每条未被割的边在右边于其两个端点处各被计数一次。于是 ,即 。由于任何割的权重都不超过 ,故 。无自环的假设保证移动一个顶点会改变每条关联边的状态;自环将始终保持未被割,除非另行处理,否则会使所述的移动公式失效。
每次严格改进的移动都会增大目标函数。顶点到两侧的分配只有有限多种,所以同一个割不可能被重复访问,过程必然终止。终止时没有任何顶点具有正的增益,这恰好就是局部最优性条件。对于整数权重,每个正增益都是不小于一的整数。目标函数从非负值开始,且永不超过 ,因此至多有 次移动。以二进制书写的数可以比其表示长度大出指数倍,这就是为什么这只是一个数值意义上的保证,而不是多项式时间保证。
证明透视
双重计数给出保证
局部不等式是针对每个顶点的。把它们相加时,每条边被计数两次,即在每个端点各一次;这就把众多局部命题转化为被割权重与未割权重之间的一个整体比较。
例题详解
例题 1.1.5
(三角形)
给三角形的每条边赋权为一。一侧一个顶点、另一侧两个顶点的割,其值为二。单独的那个顶点的被割权重为二,未割权重为零;另外任一顶点的关联被割权重与未割权重各为一。没有任何单次移动能严格改进该割。最优值为二,因为三角形的三条边不可能全部被割开。
例题 1.1.6
(一次严格改进)
对于单位权重的路径 ,从所有顶点在同一侧开始。割值为零。移动 会使两条边都由未割变为被割,割值增加二。所得割的值为二,等于总权重,因而是最优的。
例题 1.1.7
(局部最优割不必是全局最优)
对于单位边权的四边形(四个顶点的圈),将两个相邻顶点放在一侧,另外两个放在另一侧。两条相对的边界边被割,故 ;每个顶点恰有一条关联边被割、一条未被割,因此每一次单顶点移动的增益都为零。按严格改进的定义,这是一个局部最优解。若让两侧交替分配,则四条边全部被割,值为四。比值 表明,对于任意的单顶点局部最优解,该定理中的因子是紧的。
常见错误
反例模式
不存在改进的单次移动并不意味着全局最优
上面的四边形割无法通过移动一个顶点来改进,但移到交替划分后其值翻倍。局部最优性总是相对于所允许的邻域而言的。
常见错误
(零增益移动可能循环)
若允许零增益移动而没有防循环规则,则可能永远重复访问同一个割。终止性的证明用到的是严格改进。此外,在把 转化为对 的近似时,该结论依赖于权重非负;带负权重的变体需要另行定义和分析。
解读局部不等式
条件 表示,与每个顶点关联的总权重中,至少有一半已经跨越了该割。这并不是说每条单独的关联边都被割开。在四边形的例子中,每个顶点有一条被割边和一条未割边,因此每个顶点处都可能取等号,而整体的割却只有最优值的一半。
双重计数恒等式可以明确写成:
每条无自环的边在其两个端点处各贡献一次权重,并且恰好属于两个类别之一。把局部不等式相加得到 。该论证同样适用于非连通图和孤立顶点。孤立顶点有 ,它位于哪一侧对目标函数没有影响。
例题 1.1.8
(带权局部检验)
取路径 ,边权为 ,。在割 中,割值为 。在 处,;在 处为 ;在 处为 。最后一个顶点具有正增益 ,所以这个割不是局部最优的。移动 得到 ,两条边都被割开,值为 。
严格改进与运行时间
一个实现可以扫描各顶点,找到增益为正的顶点,移动它,然后重复。在每一步,当前的分配都是一个合法的割。移动之后,被移动顶点及其邻点的增益可能发生变化;非邻点的增益不变。维护增益的实现必须一致地更新这些增益,并且在宣告局部最优之前必须检查所有顶点。一次完整的扫描即给出直接的证书:报告每一对 ,并检验 。
有限状态的终止性论证适用于任意实数权重,包括无理数权重,因为严格增大使得不可能回到任何先前的割。把顶点分配到两个有标记的侧,至多有 种分配。这是不同分配个数的指数上界,而不是多项式时间保证。若把两侧视为可互换的,则不同的无标记割的数目可以减少,但这并不改变“需要做复杂度分析”这一结论。
对于整数权重,增益是整数,因此每次严格移动至少使割值增加一。若 ,则每条边的权重为零,每个割已经是局部最优的,不会发生移动。若 ,则无论选择改进顶点的规则如何,移动次数都以 为界。由于 的比特长度是其数值大小的对数,这为朴素算法给出了一个伪多项式界。更强的多项式时间结果需要不同的论证或算法,此处并未建立。
近似与边界情形
对于最大化问题, 近似保证即 。比值 仅在 时才有意义。若所有权重为零,该不等式仍然成立,即 ,而商 则没有定义。直接陈述不等式可以处理这一边界情形,而无需臆造数值比值。
该证明把局部割与 作比较, 是一个容易计算的上界。它可能是一个较弱的界:在单位权重的三角形中,,但最优值为二。三角形的任何割都不可能包含全部三条边,这一更强的观察是该图所特有的。局部搜索的证明不需要这样的结构分析,在所述假设下适用于每一个图。
随机割独立地把每个顶点分配到某一侧,其期望值为 。该平均论证证明了存在一个至少与总权重一半同样好的割,但某次随机实现可能更差。局部搜索定理则是在其单顶点规则下,保证每个终止割的质量。两种论证共享同一个界,而依据的证据不同:一个是期望,另一个是逐顶点不等式。
常见错误
(取到一半界的等号不能证明最优)
四边形还说明,仅凭取到一半界的等号并不能证明最优性。在其相邻两点的割中,双重计数不等式的两边相等,但最优值是局部值的两倍。要改进近似保证,需要额外的算法思想或更大的邻域,并配以新的证明;所展示的定理并未作出这样的断言。
检验一个给定的终止割
读者无需重放移动序列,就可以验证所声称的局部最优解。列出划分的两侧,计算割值,并对每个顶点分别对同侧邻点和异侧邻点求关联权重之和。若每个异侧之和都不小于同侧之和,则该割是局部最优的。随后由双重计数的证明给出近似不等式。若哪怕只有一个顶点违反该不等式,移动它就给出一个显式的严格更优的割,从而否定该局部最优性的声称。
这一检验也清楚地表明该保证依赖于哪些数据。权重必须是所评估实例的权重,并且每条边都必须按其所述的重数计数。平行边对端点和以及对 都是各自独立贡献的。该证明并不要求特定的初始划分或特定的改进顶点序列,因此不同的运行可以终止于不同的局部最优解,而每一个都具有同样的“至少总权重一半”的保证。
局部最优性的证书弱于全局最优性的证书。要证明带权路径例子中的全局最优性,还需给出一个值为 的割,与普适上界相匹配。在四边形的例子中,局部不等式成立,但存在更好的割,从而否定了全局最优性。把这两种断言分开,可以避免把算法的停止条件误当作“没有任何多顶点改动能起作用”的证明。
把半总权重的保证变成确定性构造
前面的局部搜索证明使用终止割处的逐顶点不等式。还有一种构造半权重割的方法:逐个固定顶点,同时保持条件期望。设图有限、无向、无自环,边权非负,总权重为 。先设想每个顶点独立地以各 的概率放到 或 。每条边的端点分处两侧的概率为 ,所以割值期望是 。这里使用的是期望的线性性;各边是否被割开的指示变量不需要相互独立。
固定一部分顶点后,仍把未固定顶点视为将独立地抛公平硬币决定位置。记这种假想补全的割值期望为 :两端已固定且跨割的边贡献全部权重;两端已固定且同侧的边贡献零;至少一端未固定的边贡献其权重的一半。对下一个顶点 ,记固定为 、 后的期望分别为 。由于硬币的两种结果等可能,
因此 至少有一个不小于 。选择其中较大者,平手时任选一侧,再继续处理。空赋值的期望为 ,按此规则所得期望序列不会下降。所有顶点固定后不再有随机性, 就是构造出的实际割值 ,所以 。边权非负保证 ; 时不等式仍成立,但比值 没有定义。这是确定性构造,并不是说每个随机割都达到期望值。
例题 1.1.9
(另一个带权三角形)
这里使用与上面单位权例子不同的三角形:、、,故 。按 的顺序固定顶点,本次在平手时选择 。表中是精确条件期望,并非随机模拟的平均值。
| 下一个顶点 | 选择 | 保留的 | ||
|---|---|---|---|---|
初始 。固定 后, 已跨割,贡献 ;另外两边仍未完全固定,贡献 ,于是 。最后取 ,边 跨割而 不跨割,实际割值为 。一般保证只要求至少 ;这里取得更大值是该实例和这些选择的结果。
从空赋值保持 的证明要求每一步都比较并选择较大的期望。如果手动选了较差的一侧,此后继续选较大者只能保证不低于新前缀的期望,未必能补回此前的损失。例如先取 ,再取 , 降至 ;余下最好的选择是 ,最终割值 。因此从手动前缀继续完成,不能事后补证原来的半权重保证。
实现时,决定 的两侧选择差异的只有它连向已固定邻点的边:通向未固定邻点的边在两种选择下都贡献一半权重。分别求出 连向左右两侧已固定邻点的权重之和,把 放到较大总和的对侧。使用邻接表时,每条边在其两个端点处各检查一次,整次构造需 次算术操作;位复杂度仍取决于输入表示和精确运算。这一构造未必得到单顶点局部最优割;它的证明依据是持续保持条件期望,而非前面的局部不等式。
总结
在单顶点局部最优解处,每个顶点的关联被割权重都不小于未割权重。双重计数给出“至少总权重一半”的保证。严格改进必然终止,但整数权重情形下的数值界不可与多项式比特复杂度界混为一谈。
练习
快速检查
(在单位权重的三角形中,对例中割的两顶点一侧,验证局部不等式。)
把一个顶点上被割与未被割的关联边权重分别加起来。
解答 · 答案
这两个顶点中的每一个,都有一条边连向单独的那个顶点,另有一条边连向其同侧的另一个顶点。因此 。
快速检查
(在三个顶点且未被割的单位权重路径中,移动中间顶点的增益是多少?)
比较移动前后两条关联边的状态。
解答 · 答案
两条关联边都变为被割,所以增益为 。
快速检查
(为什么四边形的例子是局部最优的,却不是全局最优的?)
先算一个顶点的增益,再与交替割比较。
解答 · 答案
每个顶点恰有一条被割的关联边和一条未被割的关联边,因此其增益为零。交替割的值为四,而不是二。
快速检查
(若整数权重之和为 ,该定理对严格改进移动次数给出什么上界?)
每次严格移动使整数的割值至少增加一。
解答 · 答案
至多 次:整数割值每次移动至少增加一,且永不超过总权重。