Monge 性

矩阵 w(i,j) 的四边形不等式:w(i1,j1)+w(i2,j2)≤w(i1,j2)+w(i2,j1);行最小值的位置随行单调。

标签 数学 / Monge / 四边形不等式 / 矩阵 / 单调性

定义

设 𝑊=(𝑤(𝑖,𝑗)) 是行、列指标都有全序的矩阵。若对任意 𝑖1≤𝑖2、𝑗1≤𝑗2,

𝑤(𝑖1,𝑗1)+𝑤(𝑖2,𝑗2)≤𝑤(𝑖1,𝑗2)+𝑤(𝑖2,𝑗1),

称 𝑊 满足 Monge 性。这个不等式也叫四边形不等式。

若不等号方向相反,称为反 Monge 性,或称逆四边形不等式。

相邻判定

对离散矩阵,只需验证所有相邻的 2×2 子矩阵。记 𝑤𝑖,𝑗=𝑤(𝑖,𝑗),相邻条件为

𝑤𝑖,𝑗+𝑤𝑖+1,𝑗+1≤𝑤𝑖,𝑗+1+𝑤𝑖+1,𝑗.

沿行、列累加这些相邻不等式,可以得到任意 𝑖1≤𝑖2、𝑗1≤𝑗2 的 Monge 不等式。

行最小值的单调性

先假设每一行都在同一列集合上取最小值。对每一行 𝑖,令

𝐽(𝑖)=argmin𝑗𝑤(𝑖,𝑗),

多个最小值取最小的 𝑗。若 𝑊 满足 Monge 性,则

𝐽(𝑖)≤𝐽(𝑖+1).

证明如下。反设 𝑖1<𝑖2 但 𝐽(𝑖1)>𝐽(𝑖2)。记 𝑗1=𝐽(𝑖1)、𝑗2=𝐽(𝑖2),则 𝑗2<𝑗1。由 Monge 性,

𝑤(𝑖1,𝑗2)+𝑤(𝑖2,𝑗1)≤𝑤(𝑖1,𝑗1)+𝑤(𝑖2,𝑗2).

另一方面,𝑗1 是第 𝑖1 行的最小点,𝑗2 是第 𝑖2 行的最小点,所以

𝑤(𝑖1,𝑗1)≤𝑤(𝑖1,𝑗2),𝑤(𝑖2,𝑗2)≤𝑤(𝑖2,𝑗1).

两式相加得到反向不等式,与 Monge 不等式夹在一起,只能全部取等号。因此 𝑗2 也是第 𝑖1 行的最小点;由 𝑗2<𝑗1 和取最小 𝑗 的约定,𝐽(𝑖1) 应为 𝑗2,矛盾。所以 𝐽(𝑖1)≤𝐽(𝑖2)。

若不等号反向,行最小值的位置随行单调不增。最大化问题可以把 𝑤 换成 −𝑤,或者直接改用相反方向的不等式。

在 1D/1D DP 中,若转移权重与 𝑓(𝑗) 无关且满足 Monge 性,则最优决策点单调;见 决策单调性。

常见误区

  • Monge 性是行最小值单调的充分条件,不是必要条件;不能因为 𝐽 单调就断言 𝑊 满足 Monge 性。
  • 最小化与最大化对应的不等号方向不同;使用前先确认把 𝑤 还是 −𝑤 代入。
  • 相邻判定依赖行、列指标的全序;一般偏序集上没有这种 2×2 判定。
  • 若权重依赖 𝑓(𝑗),它不再是固定矩阵,不能直接检查 Monge 性。
  • 多个最小值时要固定取最小的 𝑗,否则行最小值的位置可能不唯一。
源码位置