Measure and Conquer

普通测度只数还剩多少对象，容易忽略对象因局部状态改变而变得更易处理。Measure and Conquer 给不同类型不同权重，把删除与降度等隐性进展放入同一标尺；权重必须同时满足所有可达规则，最坏分支的指数底才代表整个算法。

图中的 ${\mathrm{\Delta }}_{in}=4$ 只计被删除的四个三次顶点，表示可保证的下降量；未画出的外部降度可使实际下降更大。排除分支则同时计入中心删除与三个邻居从权重 $1$ 变为 $a$。

三次顶点分支的局部账本 ​

考虑最大独立集的回溯分支理路回溯法Backtracking深度优先枚举部分解并在不可能完成时撤销选择的搜索范式。：对三次顶点 $v$，一支排除 $v$，另一支选入 $v$ 并删除闭邻域 $N[v]$。先限于最大度至多三的简单图，三次顶点权重为 $1$、二次顶点权重为 $a\in [0,1]$，度零、一的权重非负且不超过 $a$；降度不增加权重。考察 $v$ 的三个不同邻居也都是三次的局部状态。

排除 $v$ 会删除权重 1，并使三个邻居从三次降为二次，测度下降

选入 $v$ 删除 $v$ 及三个邻居，下降至少 ${\mathrm{\Delta }}_{in}=4$。于是这个局部规则给出

排除分支的这份下降是直接删点后的精确账本；选入分支至少删去权重 $4$，外部降度还可能增加收益。邻居之间相邻或共享外部邻居会影响这部分额外收益，所以没有把它们当作互不重叠的额外删除来收费。完整算法仍须核对度零、一、二的处理和其他可达规则。例子的作用是展示“删除对象”和“对象改类型”都必须进入同一账本，不能只数被删顶点。

权重优化 ​

每条约简给出形如“新测度不大于旧测度”的线性不等式，每条分支给出依赖权重的降幅。固定候选底数 $r$ 后，条件

在 ${\mathrm{\Delta }}_i(w)$ 为仿射函数时是凸约束，因为它是仿射函数的指数之和；配上线性权重条件即可对固定 $r>1$ 检查凸可行性。候选底数增大时条件变弱，可据此二分。线性规划理路线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。能处理部分线性化账本，但指数约束本身不应冒充普通 LP。

数值优化给出的权重只是猜想证书。发布证明时要给足够精度的有理权重或严格区间，并逐规则验证不等式；浮点求解器打印六位小数不构成严格上界。

Reduction rule 的证明责任 ​

若一个约简把三次顶点变为两个二次顶点，测度变化是 $2a-1$；要保证不增加，必须加入 $a\le 1/2$，或把约简产生的其他删除一并计算。权重非负只给测度下界；约简次数、分支的共同下降量以及基例可解性仍须分别证明。

某些局部状态在算法不变量下永远不可达，可以不纳入最大规则；这必须由结构引理证明。反过来，把可达坏状态漏掉会得到虚假的较小指数底。Measure 正确只证明搜索树大小，单节点约简、复制与解恢复的多项式工作仍需相乘。

与其他分析的边界 ​

递归树法理路递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。展开已知递推；Measure and Conquer 先设计递推所用的势尺，再展开。它与摊还势函数都使用权重，但这里衡量尚未解决实例并控制递归叶数，不是在操作序列间搬移成本。

若测度含参数 $k$ 与结构项，例如 $\mu =k+\alpha n_2$（固定 $\alpha \ge 0$），先得到的仍是 ${\rho }^{k+\alpha n_2}\mathrm{poly}(N)$。只有另证 $n_2\le ak+b\ln (N+1)$（固定 $a,b\ge 0$）等条件，才能将它写成 $c^k\mathrm{poly}(N)$，其中 $c={\rho }^{1+\alpha a}$。若 $n_2$ 可独立增长到输入规模，指数并未只依赖 $k$；而 $\mu =O(N)$ 通常只给精确指数算法的界。