DP归纳（改写自OIBH）最小最大问题(MINMAX)

查看文章

2008年11月12日星期三下午 07:38

与求图的最长路径相同，给出的图需是有向而无环的，才能求它的最小最大问题

定义一条路径的瓶颈为该路径上的边的权值的最大值或最小值，最小最大问题就是求它的瓶颈

它的动规模型：

Ｆ［Ｉ，Ｊ］＝ＭＩＮ　（　ＭＡＸ（Ｆ［Ｉ，Ｋ］，Ｇ［Ｋ，Ｊ］））

求路径最长边的小值，初值Ｇ［Ｉ，Ｊ］＝∞　Ｆ［Ｉ，Ｊ］＝∞　Ｆ［Ｉ，Ｊ］＝Ｇ［Ｉ，Ｊ］（如果Ｉ＼Ｊ有直连）

for k:=1 to 10 do
for i:=1 to 10 do
for j:=1 to 10 do
if (i<>j)and(j<>k)and(i<>k) then
if max(f[i,k],g[k,j]) <f[i,j] then
f[i,j]:=max(f[i,k],g[k,j]);

或是

Ｆ［Ｉ，Ｊ］＝ＭＡＸ　（　ＭＩＮ（Ｆ［Ｉ，Ｋ］，Ｇ［Ｋ，Ｊ］））

求路径最短边的大值，初值Ｇ［Ｉ，Ｊ］＝－∞　Ｆ［Ｉ，Ｊ］＝－∞　Ｆ［Ｉ，Ｊ］＝Ｇ［Ｉ，Ｊ］（如果Ｉ＼Ｊ有直连）

for k:=1 to 10 do
for i:=1 to 10 do
for j:=1 to 10 do
if (i<>j)and(j<>k)and(i<>k) then
if mIN(f[i,k],g[k,j]) >f[i,j] then
f[i,j]:=min(f[i,k],g[k,j]);

类别：dp归纳 | 浏览() | 评论 (0)