四边形不等式与决策单调性
__ryp__
·
·
个人记录
四边形不等式
a \le b \le c \le d, w(a, c) + w(b, d) \le w(a, d) + w(b, c)
即，交叉小于包含。
如果有方程
f(i) = \min\limits_{1\le j \lt i} w(j, i)
设在 i 点的决策点为 q(i)，要证 j \lt i, q(j) \le q(i)
设有 c \lt d，但 q(c) = b \gt q(d) = a，那么首先有
a \lt b \le c \lt d
于是由最优
w(a, c) \gt w(b, c), w(b, d) \gt w(a, d)
两式相加得
w(a, c) + w(b, d) \gt w(a, d) + w(b, c)
但是这与四边形不等式矛盾。
简单证明 P3195 玩具装箱有决策单调性
w(i, j) = (s_i - s_j - L)^2 = O((s_i - s_j)^2)
其中 s_i 是单调增的，那么对 i \lt j，有
w(i, j - 1) + w(i + 1, j) \lt w(i, j) + w(i + 1, j - 1)
也即
(s_i-s_{j-1})^2 + (s_{i+1}-s_j)^2 \lt (s_i - s_j)^2 + (s_{i+1}-s_{j-1})^2
(s_i-s_{j-1}+s_i - s_j)(s_i-s_{j-1}-s_i+s_j) \lt (s_{i+1}-s_{j-1}+s_{i+1}-s_j)(s_{i+1}-s_{j-1}-s_{i+1}+s_j)
(2s_i - s_j - s_{j-1})(s_j - s_{j-1}) \lt (2s_{i+1}-s_j - s_{j-1})(s_j - s_{j-1})
由于 s_j - s_{j-1} \gt 0，那么
2s_i - s_j - s_{j-1}\lt s_{i+1}-s_j - s_{j-1}
也就是 s_i \lt s_{i+1}，由单调性得证。