清华大学出版社 四边形不等式 货物储运问题的动态规划递归式是下面更一般的递归计算式的 特殊情形。 l [, w(i,j)+min(mi,k-1]+m[k,j i<j Y 对于i≤<j≤,当函数w(小满足 n(i,j)+w(i,j)≤w(l,j)+w(2八)了 时称W满足四边形不等式 当函数W(满足 v(i,j)≤w(i,j) 时称W关于区间包含关系单调 对于满足四边形不等式的单调函数W,可推知由递归式定义的 函数m(也满足四边形不等式,即 2 (i,j)+m(i,,)sm(i,j)+m(i, j11 四边形不等式 i j i j w i j m i k m k j m i j i k j  =     + − + =   ( , ) min { [ , 1] [ , ]} 0 [ , ] 货物储运问题的动态规划递归式是下面更一般的递归计算式的 特殊情形。 对于 ,当函数w(i,j)满足 时称w满足四边形不等式。 当函数w(i,j)满足 时称W关于区间包含关系单调 对于满足四边形不等式的单调函数w，可推知由递归式定义的 函数m(i,j)也满足四边形不等式，即 w(i, j) + w(i' , j')  w(i' , j) + w(i, j') i  i' j  j' w(i' , j)  w(i, j') m(i, j) + m(i' , j')  m(i' , j) + m(i, j')