跟大家分享最近研究 monotonicity、1D/1D DP、convex hull trick 的心得。 我想很多人高中的时候就搞懂了，这篇文章的主要贡献大概就是文献整理吧。 我每次看这种介绍都会被搞昏，因为有一大堆索引值。 所以我尽量的把索引值的大小关系写清楚， 一般情况下的使用会是 i < j < k < k'。 当要比较两个阵列元素的时候，我会尽量把索引值小的放左侧， 也就是我会尽量写 A[i] ?? A[j] 。 Dominatation 先从一个简单的例子开始介绍 dominate 的概念。 给定一个长度为 n 的整数阵列 A ，对所有 k 计算 A[0] ~ A[k - 1] 中的最小值，亦即计算 B[k] = min_{i < k} A[i] 首先考虑两个元素 A[i], A[j], i < j (A[i] 在 A[j] 之前)， 如果 A[i] > A[j] 的话，那对於所有 j < k, B[k] 不可能会是 A[i] 。 换句话说 A[i] 被 A[j] dominate 了，A[i] 对於 j 之後的元素是没有 影响的，因为选择 A[j] 必定是个更好的选择，所以不需要保留关於 A[i] 的资讯。 反之，如果 A[i] < A[j] ，那 A[i] 就 dominate 了 A[j] 。 因此解法很单纯，只要从 k = 0 ~ n-1 一次扫描，纪录当前的最小值即可。 再考虑一个类似的问题 (all nearest smaller values) https://en.wikipedia.org/wiki/All_nearest_smaller_values 给定一个长度为 n 的整数阵列 A ，对於所有 k 计算出现在 A[k] 之前，最靠近 A[k] 且比 A[k] 小的数字。 亦即计算 B[k] = A[ max_{i < k : A[i] < A[k]} ] 因为必须要找到最靠近的元素，所以问题就变得比较复杂。 考虑两个元素 A[i], A[j], i < j (A[i] 在 A[j] 之前)， A[i] > A[j] 的情况跟之前一样，但是A[i] < A[j] 的情形就不同了， 因为 A[j] 还是有可能会是 B[k], j < k 的解答。 所以可以把所有没被 dominate 的元素储存起来，计算 B[k] 的时候， 只需要从这些没被 dominate 的元素里面找解答就好。 这概念跟 Pareto frontier 的概念一样，只从比较好的候选人中挑解答。 但是 Pareto frontier 可能还是包含了许多元素，所以从 Pareto frontier 里面挑解答还是很花时间，某些时候是可以把 Pareto frontier 里面的元素 放在资料结构内，使得解答可以快速的找出来。 此时就需要引入另外一个概念 -- monotonicity。 Monotonicity 在 all nearest smaller values 问题中，令 i1, ..., it 表示 在 A[k] 前 的 Pareto frontier 中元素的索引值，我们可以把在 Pareto frontier 的元 素按照索引值排列 A[i1], A[i2], ..., A[it], i1 < i2 < ... it < k 那麽 这些元素的值必定是递增的，也就是 A[i1] < A[i2] < .... A[it] 因为如果索引值大的元素有比较低的值，那索引值低的元素就 会被 dominate 了。 而且 all nearest smaller values 问题要求要找到最靠近且小於 A[k] 的元素，所以如果 A[it] < A[k] ，那麽 B[k] 必为 A[it] 。 如果 A[it] > A[k] ，那麽 A[it] 就被 A[k] dominate 了。 所以只要依照 A[it], A[it-1], ... 的顺序去找，找到 A[ih] < A[k] ， 那麽 B[k] 必为 A[ih] 。 然後可以把 A[k] 放到 Pareto frontier 中，然後接着计算 B[k+1]。 因为所有元素的操作都是在 Pareto frontier 的尾端，所以可以使用 一个 stack 来储存 Pareto frontier 。 上面这个例子是使用 stack ，这边我再介绍一个使用 queue 来储存 Pareto frontier 的例子： 给定一个长度为 n 的整数阵列 A 和一正整数 L ，计算所有 长度为 L 的子阵列中的最小值。 亦即计算 B[k] = min_{k - L + 1 <= i <= k} A[i] 简单来说，这问题就是要找出 sliding window 内的最小值。 所以我们想要设计一个 queue ，同时支援最小值查询。 (题外话， deque + 最小值查询也是可以办得到的 可以参考 Gajewska 和 Tarjan 的论文 Deques with heap order http://www.sciencedirect.com/science/article/pii/0020019086900281 ) 考虑两个元素 A[i] 和 A[j], i < j, (A[i] 在 A[j] 之前)， 如果 A[i] > A[j] ，那麽 A[i] 就不可能会是 B[k], j < k 的答案了， 也就是 A[i] 被 A[j] dominate 了 。 如果是 A[i] < A[j] ，那麽 A[i] 还是有可能是 B[k], j < k 的答案。 所以跟 all nearest smaller values 问题类似，把 Pareto frontier 中的元素按照索引值排列，此时 Pareto frontier 中的元素必递增。 所以最小值必定是索引值最小的元素。 跟 all nearest smaller values 类似，也会需要把索引值大的元素从 Pareto frontier 中移除，同时也会新增加索引值大的元素。 不同点在於这问题有长度的限制，计算 B[k] 时的 Pareto frontier 必不 能包含 A[i], i < k - L 。 也就是说在维护 Pareto frontier 时会需要把索引值小的元素从 Pareto frontier 中移除。 所以此时需要用一个 deque 来维护 Pareto frontier ，只是索引值小 的那端只有 deque 不会 enqueue ，而索引值大的那端则是 enqueue 和 deque 都会发生。 所以总归来说，如果要使用 domination 的性质，首先必须要设计一个 domination 的关系，把不可能为答案的 candidate 删除，这步骤虽然 不容易，但是并不是最困难的地方。 而如果要使用 monotonicity 性质，就必须要考虑以下三点： 1. 如何排序 Pareto frontier 2. 如何从有序的 Pareto frontier 中快速找到解答 3. 如何更新 Pareto frontier 且满足有序的性质 有兴趣的人可以研究 maximum density segment 的问题 给定一个长度为 n 的整数阵列 A 和一正整数 L ，找出长度至少 为 L 的子阵列中平均值最大的子阵列。也就是要找出 i, j 满足 i + L - 1 <= j 使得 A[i..j] / (j - i + 1) 的值最大 解法可以参考这个 https://goo.gl/FUmnPt 。 这问题的 domination 是要考虑三个点 A[i], A[j], A[k] 的，只考虑 两个点是找不到 domination 的。而且从 Pareto frontier 找答案的 方式也不太一样。 如果除了有长度的下限 L 之外，又有长度上限 U 的限制的话，deque 的维护就更复杂了，可以参考 D. T. Lee, Tien-Ching Lin 和 Hsueh-I Lu 的论文 Fast Algorithms for the Density Finding Problem http://link.springer.com/article/10.1007%2Fs00453-007-9023-8 1D/1D DP 在使用 DP 解决序列上的问题时，1D/1D 是很常见的形式，我接下来 都会用 line wrap 问题当例子。 https://en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_raggedness 这是 Knuth 在设计 TeX 的时候遇到的问题，这边只是简化的版本。 http://onlinelibrary.wiley.com/doi/10.1002/spe.4380111102/abstract 给定一串 n 个单字和一个正整数 L，把这些单字按照分行， 使得每行的字母数与 L 的差距越小越好 正式的定义如下： 给定一正整数 L 和一个长度为 n 的整数阵列 A ， 找出 p (p 是算法自己决定的) 个索引值 k1, ..., kp = n-1 把 A 分成 p 个子阵列 A[0...k1], A[k1+1...k2], ... 且最小化 penalty 总和。 子阵列 A[i...j] 的 penalty 定义为 (L - sum(A[i...j]))^2 令 w[i][j] 表示 A[i...j] 的 penalty 。 令 B[k] 表示 A[0...k] 的最佳分法的 penalty 。 此问题可以利用下列递回关系式求解： B[k] = min_{i < k} B[i] + w[i + 1][k] 时间复杂度是 O(n^2) 为了解释方便 如果 B[k] = B[i] + w[i + 1][k] ，就称之为 B[k] 选择了 A[i] 。 因为 F 是一个一维函数，而 F[k] 考虑的 candidate 也只有一个维度， 所以这类的 DP 就叫做 1D/1D DP 了。 此外还有 2D/0D DP, 2D/1D DP, 2D/2D DP ，只是不在这篇文章讨论范围了。 首先让我们分析这个问题。 考虑两个元素 A[i] 和 A[j], i < j, (A[i] 在 A[j] 之前)， 不管是 A[i] > A[j] 还是 A[i] < A[j] ，似乎都没有很明显的 domainte 的关系，毕竟问题有本质上的不同。 但是直觉上，因为这问题是在分行，所以尽管在算 B[k] 时，让 A[i...k] 在一行是好选择，但是应该会存有一个 k' > k 时 A[j...k'] 会变成比较 好的选择了。 这性质有人称为决策单调性，只是这性质应该只对 concave 的 w 有用。 (concave 的定义我就省略了)。 Hirschberg 和 Larmore 首先对这类问题展开研究。 The Least Weight Subsequence Problem http://epubs.siam.org/doi/abs/10.1137/0216043 他们发现当 w 是 concave 的时候， 对於任何两个元素 A[i] 和 A[j], i < j, (A[i] 在 A[j] 之前) 如果只考虑选择 A[i] 或是 A[j] 的话， 会存在一个界线 h ，使得 k <= h 时，B[k] 挑选 A[i] 当 k > h 时，B[k] 挑选 A[j]。 而这个界线是可以在 O(lg n) 的时间内用二分法计算出来的。 所以可以维护一个 deque 来放所有的 candidate ，及其是最佳解的区间 也就是在计算 B[k] 时，如果 deque 是 (A[i1], h1) (A[i2], h2) ... 那麽在只考虑从 A[0] ~ A[k-1] 中挑的话 A[i1] 会是 B[k'] 的最佳选择，如果 k <= k' <= h1 A[i2] 会是 B[k'] 的最佳选择，如果 h1+1 <= k' <= h2 等等。 如此一来这问题就可以在 O(n lg n) 的时间内被解决了。 如果想要知道详细内容的，可以看这篇 Galil 和 Park 的论文 Dynamic programming with convexity, concavity and sparsity http://www.sciencedirect.com/science/article/pii/0304397592901353 Convex hull trick 第一次出现这技巧应该是在 Wagelmans, Hoesel 和 Kolen 的论文 Economic lot-sizing- An O(n log n) algorithm that runs in linear time in the Wagner-Whitin case http://pubsonline.informs.org/doi/abs/10.1287/opre.40.1.S145 只是他们只拿来解特定的问题 在 Hoesel, Wagelmans 和 Moerman 的论文提到了比较一般化的方法 Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions http://www.sciencedirect.com/science/article/pii/0377221794900779 使用几何的方法来加速 DP ，专门处理 B[k] = C[k] + min_{i < k} (B[i] + D[i] + E[k]F[i]) 的 DP 问题， 如果 E 和 F 是 monotone 的话，就可以 在线性时间内找到最佳解。 虽然看起来跟 line wrap 不太像，但是实际上是可以转化的。 在 line wrap 问题中，递回关系式是 B[k] = min_{i < k} B[i] + w[i + 1][k] 两边带入 w 的定义 = min_{i < k} B[i] + (L - sum(A[i+1...k]))^2 令 P 为 prefix sum 阵列， P[i] = sum A[0..i], P[-1] = 0 B[k] = min_{i < k} B[i] + (L - (P[k] + P[i]))^2 展开 (L - (P[k] + P[i]))^2 = min_{i < k} B[i] + L^2 - 2L(P[k] + P[i]) + (P[k] + P[i])^2 展开 (P[k] + P[i])^2 = min_{i < k} B[i] + L^2 - 2L(P[k] + P[i]) + P[k]^2 + 2P[k]P[i] + P[i]^2 把跟 i 无关的提到外面来 = P[k]^2 + L^2 - 2LP[k] + min_{i < k} B[i] + P[i]^2 - 2LP[i] + 2P[k]P[i] 所以可以令 C[k] = P[k]^2 + L^2 - 2LP[k] D[i] = P[i]^2 - 2LP[i] E = F = P 就可以使用这个方法了。 这方法的关键就是可以把 1D/1D 的问题转成一个几何的问题，从而找出 一个 dominate 的关系，然後利用 monotonicity 来加速。 而在 Brucker 的论文中，则使用了纯代数的方法。 Efficient algorithms for some path partitioning problems http://www.sciencedirect.com/science/article/pii/0166218X94001465 (这篇论文的的内容後来出现在IOI 2002 的 Batch Scheduling 问题) 其中最关键的一步就是证明了 如果存在有一个 d 函数，和一个递增的 f 函数 使得 对於所有 i < j < k, 计算 B[k] 时，A[i] 被 A[j] dominate 若且唯若 d(i, j) <= f(k) 那 B 就可以在线性时间内算出来。 套在 line wrap 上面， 考虑 A[i] 和 A[j], i < j, (A[i] 在 A[j] 之前) 在计算 B[k] 时, i < j < k, 如果选择 A[i] 比选择 A[j] 差的话代表 B[i] + w[i+1][k] >= B[j] + w[j+1][k] 两边带入 w 的定义 iff B[i] + (L - sum(A[i+1...k]))^2 >= B[j] + (L - sum(A[j+1...k]))^2 利用之前的结论，把两边的 P[k]^2 + L^2 - 2LP[k] 都消掉 iff B[i] + P[i]^2 - 2LP[i] + 2P[k]P[i] <= B[j] + P[j]^2 - 2LP[j] + 2P[k]P[j] 把 所有跟 k 相关的移到右边 跟 k 无关的移到左边 iff (B[i] + P[i]^2) - (B[j] + P[j]^2) <= 2L(P[i] - P[j]) + 2P[k](P[j]-P[i]) 两边同除 P[j] - P[i] iff ((B[j] + P[j]^2) - (B[i] + P[i]^2)) / (P[j] - P[i]) <= 2(P[k] - L) 左边就是 delta 右边是 f 了。 其实也不难看得出来 Hoesel, Wagelmans 和 Moerman 的模型 B[k] = C[k] + min_{i < k} (B[i] + D[i] + E[k]F[i]) 只要 E 和 F 都是 monotone 的，都可以套到 Brucker 的模型里。 （但是有些 case <= 要换成 >=）。 简单来说，看到一个 1D/1D 的问题，可以先试着套用 Brucker 的模型， 也就是在计算 B[k] 的时候，比较 A[i] 和 A[j] 两种选择, i < j < k。 如果可以化成 Brucker 要求的形式，那问题就可以线性时间解出来了。 我也尝试过使用 Brucker 的模型来解释 maximum density segment ， 不过似乎是没办法直接套用的，因为需要两个点 i, k 才能 dominate 另一个 点 j ， Brucker 的模型都是只考虑用一个点就可以 dominate 另一个点的。 结语 其实还有一个 DP 的最佳化技巧叫做 Knuth-Yao quadrangle inequality， 可以拿来加速 optimal binary search tree 的建立。 https://en.wikipedia.org/wiki/Optimal_binary_search_tree 经过专家的研究发现，其实 Knuth-Yao quadrangle inequality 实际上 也可以用 total monotonicity 来解释的。 Bein, Golin, Larmore and Zhang Quadrangle-Inequality Speedup is a Consequence of Total Monotonicity http://dl.acm.org/citation.cfm?id=1644032 至於 total monoonicity, Monge, convex/concave 之间的关系可以参考 http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html#7 参考文献 想要了解各种 DP 的最佳化技巧可以参考 Bein 的论文 Advanced Techniques for Dynamic Programming http://link.springer.com/referenceworkentry/10.1007/978-1-4419-7997-1_28 考古 当 w 是 concave 时 Wilber 设计出了线性演算法，但是是基於 SMAWK 的。 The concave least-weight subsequence problem revisited http://www.sciencedirect.com/science/article/pii/0196677488900326 https://en.wikipedia.org/wiki/SMAWK_algorithm Galil 和 Park 考虑 B[k] = min_{i < k} C[i] + w[i + 1][k] 的情形也 设计出了线性演算法，还是基於 SMAWK 。 A linear-time algorithm for concave one-dimensional dynamic programming http://www.sciencedirect.com/science/article/pii/002001909090215J 然後 Larmore 和 Schieber 设计了不基於 SMAWK 的线性演算法 On-line dynamic programming with applications to the prediction of RNA secondary structure http://www.sciencedirect.com/science/article/pii/019667749190016R Klawe 也设计了线性演算法，但是只有发表在 technical report 上。 可以在这篇论文里面找到 pseudo code Consecutive interval query and dynamic programming on intervals http://www.sciencedirect.com/science/article/pii/S0166218X98000213 当 w 是 convex 的时候（定义我就省略了） Miller and Myers 设计了一个 O(n lg n) 的方法。 Sequence comparison with concave weighting functions http://www.sciencedirect.com/science/article/pii/S0092824088800168 Galil and Giancarlo 也设计了一个 O(n lg n) 的方法， Speeding up dynamic programming with applications to molecular biology http://www.sciencedirect.com/science/article/pii/0304397589901011 而且他的方法可以解决 B[k] = min_{i < k} C[i] + w[i + 1][k] 形式的问题。 Klawe 和 Kleitman 设计了 O(n α(n)) 的方法。 An Almost Linear Time Algorithm for Generalized Matrix Searching http://epubs.siam.org/doi/abs/10.1137/0403009 Eppstein 考虑 convex 和 concave 可以 mix 的情况 Sequence comparison with mixed convex and concave costs http://www.sciencedirect.com/science/article/pii/0196677490900319 Eppstein, Galil, Giancarlo, and Italiano 考虑了 sparse 的情况 Sparse dynamic programming II: convex and concave cost functions http://dl.acm.org/citation.cfm?id=146656 对 FP 有兴趣的人可以看这两篇 Oege de Moor and Jeremy Gibbons Bridging the Algorithm Gap: A Linear-Time Functional Program for Paragraph Formatting http://www.sciencedirect.com/science/article/pii/S0167642399000052 Sharon A. Curtis and Shin-Cheng Mu Calculating a linear-time solution to the densest-segment problem http://dx.doi.org/10.1017/S095679681500026X --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 65.96.6.117 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1458211168.A.907.html