Monge 性
矩阵 w(i,j) 的四边形不等式:w(i1,j1)+w(i2,j2)≤w(i1,j2)+w(i2,j1);行最小值的位置随行单调。标签 数学 / Monge / 四边形不等式 / 矩阵 / 单调性
定义
设 是行、列指标都有全序的矩阵。若对任意 、,
称 满足 Monge 性。这个不等式也叫四边形不等式。
若不等号方向相反,称为反 Monge 性,或称逆四边形不等式。
相邻判定
对离散矩阵,只需验证所有相邻的 子矩阵。记 ,相邻条件为
沿行、列累加这些相邻不等式,可以得到任意 、 的 Monge 不等式。
行最小值的单调性
先假设每一行都在同一列集合上取最小值。对每一行 ,令
多个最小值取最小的 。若 满足 Monge 性,则
证明如下。反设 但 。记 、,则 。由 Monge 性,
另一方面, 是第 行的最小点, 是第 行的最小点,所以
两式相加得到反向不等式,与 Monge 不等式夹在一起,只能全部取等号。因此 也是第 行的最小点;由 和取最小 的约定, 应为 ,矛盾。所以 。
若不等号反向,行最小值的位置随行单调不增。最大化问题可以把 换成 ,或者直接改用相反方向的不等式。
在 1D/1D DP 中,若转移权重与 无关且满足 Monge 性,则最优决策点单调;见 决策单调性。
常见误区
- Monge 性是行最小值单调的充分条件,不是必要条件;不能因为 单调就断言 满足 Monge 性。
- 最小化与最大化对应的不等号方向不同;使用前先确认把 还是 代入。
- 相邻判定依赖行、列指标的全序;一般偏序集上没有这种 判定。
- 若权重依赖 ,它不再是固定矩阵,不能直接检查 Monge 性。
- 多个最小值时要固定取最小的 ,否则行最小值的位置可能不唯一。