<li id="smart-nav-recent" class="nav-section"><div class="nav-section-header"><a href="javascript:vold(0)">Article Nav</a></div><ul><li><a href="#article_nav-0" title=" 2D/1D:d[i,j]=opt{d[i,k-1]+d[k,j]}+w[i,j] (1 \(\leq\) i < k \(\leq\) j \(\leq\) n) "> 2D/1D:d[i,j]=opt{d[i,k-1]+d[k,j]}+w[i,j] (1 \(\leq\) i < k \(\leq\) j \(\leq\) n) </a></li> <li><a href="#article_nav-1" title=" 1D/1D:f[i]=opt{f[j]+w[j,i]} (b[i] \(\leq\) j \(\leq\) i-1) "> 1D/1D:f[i]=opt{f[j]+w[j,i]} (b[i] \(\leq\) j \(\leq\) i-1) </a></li> <li><a href="#respond">发表评论</a></li></ul></li>

若w[a,c]+w[b,d] \(\leq\) w[b,c]+w[a,d] (a<b<c<d)

则w满足凸四边形不等式

若w[i,j] \(\leq\) w[i,j] ([i,j]\(\subseteq\) [i',j'])

则w满足区间单调

2D/1D:d[i,j]=opt{d[i,k-1]+d[k,j]}+w[i,j] (1 \(\leq\) i < k \(\leq\) j \(\leq\) n)

d满足凸四边形不等式 k[i,j-1] \(\leq\) k[i,j] \(\leq\) k[i+1,j]

w为凸 \(\Leftrightarrow\) w[i,j]+w[i+1,j+1] \(\leq\) w[i+1,j]+w[i,j+1]

1D/1D:f[i]=opt{f[j]+w[j,i]} (b[i] \(\leq\) j \(\leq\) i-1)

满足决策单调性，可用单调队列优化决策

 

[Dr.Lib]Note:Algorithms – 四边形不等式 by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.