排序与最优化随笔

tylon2006 · 2025-07-03 17:00:59 · 算法·理论

排序的性质

二元关系 R（下为 <，方便书写与理解） 具有以下性质时：

1、非反身性 x \not <x （\not < 表示不可比性，即不满足 <）

2、非对称性 x<y \implies y\not <x

3、传递性 x<y,y<z\implies x<z

4、不可比性的传递性 x\not<y,y\not<z\implies x\not<z

称为其满足严格弱序。满足前三条称为严格偏序。

在确定满足严格弱序的二元关系后，才可以进行排序。

对于任意两个元素均可比时，当二元关系具有确定性（xRy 结果固定）与传递性，n 个元素形成了一个 DAG 竞赛图，那么必然存在一个哈密顿路径，即一个排序。又因为 DAG 的无环性质，这样的哈密顿路径是唯一的。

另一方面，一个排序本身可以生成唯一的 DAG 竞赛图。

综上所述，我们可以得到上述排序与二元关系等价。

但是存在两个元素满足 x\not<y 且 y\not<x 时，上述图无法构造。

我们可以定义二元关系 ==，x==y 表示 x\not<y 且 y\not<x。注意这并不等同于 x=y，而是定义了一个等价类 S，满足 \{x,y\}\subseteq S。

现在你可以对每个等价类进行缩点，缩点后的图就是标准的 DAG 竞赛图。

但是问题仍没有解决。我们注意到等价类 S 中的元素没有一个明确的顺序，而对于一般的排序而言，我们也不关心它们的顺序。而正是不可比性的传递性，保证了这样做的正确性。

显然，根据不可比性的传递性，x==y,y==z\implies x==z。在这个条件下，交换等价类内任意两个元素的次序对排序没有任何影响。

我们可以考虑如果没有这一条性质会发生什么。

即存在 x\not<y,y\not<z，x<z，大部分情况不会太糟糕。

但是存在 {x,y,z}\subseteq S,x==y,y==z,x<z 时，等价类 S 的随意定序此时是可能发生错误的。假设我们定出了 z\rightarrow y\rightarrow x，交换 x 和 y，此时会产生问题：交换 x 与 z 是必须的，这与我们排序完成的假设冲突。

从图论的角度解释，在满足不可比性的传递性的条件下，可以认为等价类内的元素两两存在无向边，构成无向完全图，只需要随意构造一条链，再给边定序，即可构造一个 DAG 竞赛图。

但是对于不满足不可比性的传递性情况下，等价类内某些元素之间的边是有向的，这就导致我们不能任意构造一条偏序链，因为某些边已经是有向的。

于是，我们解释了为什么排序需要二元关系满足严格弱序，这与排序的本质有关而与排序的算法无关。

显然，<（数值小于） 是一个满足严格弱序的二元运算，而 \leq 不满足非反身性、非交换性与不可比性的传递性，因此不满足严格弱序。这也是 std::sort 中要求重载 < 的原因。

排序的探索

非反身性与非交换性一般是显然的。我们需要证明一个二元关系的传递性和不可比性的传递性。

注意到数值大小本身具有优良的传递性，很重要的一个思路就是量化元素的特征，称为特征值。特征值应该是独立且唯一的。

有的时候特征值就是元素的独立贡献，但大多数情况下需要通过代数变形确定特征值（参考示例1）。

这种量化思路十分重要，广泛应用于各个板块。

但是有的时候我们无法做到将贡献规约到独立元素，我们的二元关系常常同时取决于两个元素的性质，还有些情况下贡献不能完全量化，对其他元素的贡献有影响。

这个时候就需要分类讨论证明上述两个性质。如果情况较多，可以用程序模拟枚举 x,y,z 三者的关系进行验证。

找到具有传递性的二元关系后，其不一定具有不可比性的传递性。我们有一个简单的思路解决这个问题（参考示例2）。

问题的根源在于等价类内部的混乱。在原有二元关系的基础上进行进一步比较，增加一个 x==y 时的额外判断的二元关系，使得等价类内的元素有序，从而避免讨论不可比性的传递性；或是根据原有二元关系性质给出额外信息，使得其满足不可比性的传递性。

然而这个额外的二元关系并不是随意的，它必须真的对原问题产生优化，而不是任意的给出顺序（例如给予额外编号并比较），这是治标不治本的行为。

排序与最优化排列

最优化排列，即排列 n 个元素的位置，根据一定的方法计算贡献，使总贡献最小/大的问题。此处的元素可以是一个变量，也可以是一个由许多变量组成的集合。

但是请注意，集合的变量中不应该有位置这个变量，位置应该是独立于元素之外的。

调整法

从调整的角度研究最优化问题，可以从元素角度考虑两个元素交换的影响。

因为元素的位置不是固定的，能够应用此方法解决的问题的贡献计算函数往往不应该含有位置变量。或者，交换两个元素产生的影响方向（如贡献变化量的正负）应该不因位置变化而改变，只与元素的先后关系相关。

因此，下述的情况都只研究仅元素产生影响的情况。

我们用二元关系 < 衡量交换两个元素的影响，该二元关系需要满足严格偏序。当两个元素（具有先后顺序）不满足该二元关系时，交换这两个元素的位置不会使答案更劣。

显然，当一个排列中的任意两个元素 x,y （x 在 y 前）均满足 x<y 或 x==y 时，此排列是最优排列之一。

但是往往任意两个元素的关系很难衡量，尤其是计算贡献涉及其他元素时。于是一个自然的想法是研究相邻两项的交换情况。

邻项交换排序

二元关系的定义如上，此时二元关系需满足严格弱序。

当一个排列中的任意两个元素 x,y （x 在 y 前）均满足 x<y 或 x==y 时，此排列是最优排列之一。

根据上文对排序性质的探索，我们知道满足严格弱序的二元关系保证了我们可以通过排序得到一个排列 P 满足上述条件。我们可以证明，任意一个不同于 P 的排列 Q，其不优于 P。

从 Q 出发，按照 P 从前往后的顺序，将 Q 的对应元素往前冒泡。显然，每一次冒泡都不会使答案更劣，最终 P 必然不劣于 Q。如此，P 一定是最优排列之一。

注意到上文的任意两个元素调整只需要满足严格偏序，而此处则需要满足严格弱序。我们可以从图论角度直观地理解这个问题。

对于任意调整，我们实际上给出了任意元素到其后方元素的边的情况，x<y 与 x==y 分别表示 x 指向 y 的有向边和两者之间的无向边。经过简单的定序，一定可以生成对应的 DAG 竞赛图。

对于邻项排序，我们仅给出了相邻元素之间边的情况。考虑排序对应的偏序链上的 x,y 两点，二者之间仅存在无向边。此时若没有不可比性的传递性限制，可能出现 y<x 的情况。因此，严格弱序是必要的。

示例

1、P1012 数字排序连接求最大数。

按照固定思维使用前缀排序无法解决问题。

考虑传递性，需要证明 a+b>b+a,b+c>c+b 能够推出 a+c>c+a 。

考虑量化贡献，a+b=a*10^{|b|}+b

特征值为 \dfrac{a}{10^{|a|}-1} 唯一且独立，排序即可。

那么传递性与不可比性的传递性显然成立。

2、 P1248/P2123 \ m=2 的加工调度问题

对于相邻的两项 i,i+1，记 T_i 为处理完第 i 个工件的时间，S_i=\sum_{k=1}^iA_i。

那么 T_i=\max(S_i,T_{i-1})+B_i=\max(S_i+B_i,T_{i-1}+B_i)

对于相邻的 i,i+1，我们注意到其对前面没有影响，而对后面的 T_k(k>i+1) 有影响。我们应该使得 T_{i+1} 尽量小。

交换 i,i+1 的元素后：

注意到第一项是相等的，它不影响 T_{i+1}\geq T_{i+1}' 的判定。

于是我们需要比较 \max(S_{i-1}+A_i+B_i+B_{i+1},S_{i+1}+B_{i+1}) 与 \max(S_{i-1}+A_{i+1}+B_{i+1}+B_i,S_{i+1}+B_i) 。

同时减去 S_{i+1}+B_i+B_{i+1}，

即 \min(A_{i+1},B_i)\leq \min(A_i,B_{i+1})

据此我们得到了一个关于相邻两项的二元关系 R: \min(A_{i+1},B_i)> \min(A_i,B_{i+1})

即 \min(A_i,B_{i+1})< \min(A_{i+1},B_i)

通过简单的分类讨论或是逻辑化表达（详见ouuan的博客），我们可以得到这个式子实际上具有传递性，满足严格偏序。

然而通过简单的举例我们可以发现，其并不满足不可比性的传递性。例如连续的三个元素 \{i,j,k\}:\{(1,2),(1,1),(2,1)\}，我们看到 i==j,j==k,i<k。

这种例子往往藉由 x==y 导出，与上文排序的探索相似。

此时我们需要进一步补充二元条件使得其满足严格弱序。自然地，通过观察 S_i 对答案的影响，我们可以想到通过将 A_i 升序排列以使得 S_i 尽量小。

通过程序模拟验证，无论 A_i,A_j,A_k,B_i,B_j,B_k 的大小关系情况如何，总能满足不可比性的传递性。

按照此时的二元关系排序，即可得到正确答案。

至于其他题解提到的 Johnson 算法，实际上是上述排序方式的特化情况。

从上述的分析我们可以发现，我们关注的是交换使得答案不劣，而不是使答案更优。

因为材料不足，总结与分析可能存在谬误缺漏，还请各位不吝赐教。