知识卡片
蒙日数组满足四点不等式
Monge 数组要求任意 i、j 均有 A[i,j]+A[k,l]≤A[i,l]+A[k,j]。它限制跨行列的相对成本。
由此可推得各行最左最小值的列索引单调不减,便于分治缩小搜索区间;这是习题 4-7© 要求证明的推论,不是题干已证结论。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
An m × n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 ≤ i < k ≤ m and 1 ≤ j < l ≤ n, we have A[i, j] + A[k, l] ≤ A[i, l] + A[k, j].
参考来源
- 位置:《算法导论(第4版)》第 4 章 Problems 与 Chapter notes(`OEBPS/chapter004.xhtml`,文本字符 [90000, 95000);相关公式图 Art_P231–P244)。
- 结论依据:习题 4-7 定义四点不等式;对相邻两行若下行最左极小列 l 小于上行的 j,则上行 A[i,j]<A[i,l]、下行 A[k,l]≤A[k,j],与四点不等式矛盾,故 4-7(c) 的列索引单调性成立。
- 原始内容:An m × n array A of real numbers is a Monge array if for all i , j , k , and l such that 1 ≤ i < k ≤ m and 1 ≤ j < l ≤ n , we have A [ i , j ] + A [ k, l ] ≤ A [ i, l ] + A [ k , j ].