知识卡片

普通读书笔记卡 · 3604

蒙日数组满足四点不等式

理解等级:中级

Monge 数组要求任意 i、j 均有 A[i,j]+A[k,l]≤A[i,l]+A[k,j]。它限制跨行列的相对成本。

由此可推得各行最左最小值的列索引单调不减,便于分治缩小搜索区间;这是习题 4-7© 要求证明的推论,不是题干已证结论。

这张卡片看不懂?

已有反馈 · 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 ].