15.053
4 月 2 日,周二
最小费用流问题 网络 G=(N,A) —节点集 N,弧集 A; —弧(i,j)容量 uij —弧(i,j)下限 0 —弧(i,j)费用 cij —节点 i 供/需量 (正号表示供应) 带有费用,容量 供需量的网络图
最短路问题 解最短路问题的 Dijkstra's 算法
分发:讲稿
目标:输送流的总费用最小 约束:i 节点流入量-i 节点流出量=bi 弧(i,j)上的流量<=uij. 0<=xij<=uij
建模 给出该问题的一般线性规划模型如下:
最短路问题
从源节点(S)到汇节点(T)的最短路是什 么 从节点 1 到节点 6 的最短路是什么 本节假设: 1.从源点到所有其他节点都存在路 2.所有弧长度都非负
构建线性规划 从源点 s 到汇点 t 的最短路的线性规划问 题一般可表示为:
另一种形式 从源点 s 到汇点 t 的最短路的线性规划问 题可表示为:
其他
有关最短路的一些问题 现实中如何引起的 —直接应用 —间接(通常很微小)应用 如何解最短路问题 —Dijkstra's 算法 如何衡量算法的性能 —CPU 时间 —性能保障 如何确定解是真的最短路 —和对偶线性规划联系
可能的运动得分
Flumbaya 是一项非常规水上运动, 运动过程中可以得 2 类分数.进一 个 gymbol 得 7 分,进一个 quasher 得 5 分.电视播报显示最近的比赛 比分是 19:18,这可能么
Flumbaya 的更多内容 从节点 0 到节点 18 没 有 通路. 因 此 18 分 不可能.
Flumbaya 的更多内容 数据:Gymbol 得 n1 分,Quasher 得 n2 分 确定得分是否可为 q 网络图:G=(N,A),其中 N={0,…q} 对每个节点 j=0 到 q-n1 ,(j,j+n1)∈A, 对每个节点 j=0 到 q-n2 , (j,j+n2)∈A 问题: G 中有从节点 0 到 q 的路径么 图 提示:若 n1 和 n2 除了 1 和-1 之外没有公 共整数约数,则不可能的得分数是 证明需要更多事实.警示: ( (n1-1)(n2-1)/2. 证明是很困难的)
间接应用:寻找最优段落编排 通过最优选择每行间断点, eX 将段落最 T 优分解.它有一个子程序可以计算从第 i 个单词到第 j-1 个单词的引力 F(i,j). 如何 运用 F(i,j),建立一个最短路解决段落分 解问题
间接应用:寻找最优段落设计
通过最优选择每行间断点, TeX 将段落最优分解.它有 一个子程序可以计算从第 i 个单词到第 j-1 个单词的引 力 F(i,j).如何运用 F(i,j),建 立一个最短路解决段落分解 问题 每个单词对 应于一个节 点 , 弧 (i,j) 表 示行从第 i 个单词到第 j-1 个单词. 从 Tex 到 end 对应一段落 分解.
路径的值 叫做路径 的
"ugliness" .
关于段落问题例子 n 个不同的肯定否定决策 决策 j: —肯定: 从第 j 个单词开始形成一行 —否定: 不从第 j 个单词开始形成行 每个肯定决策的费用依靠下面的肯 定决策 —f(i,j)是假定第 j 个单词从下行开始 时,从第 i 个单词开始行的费用. 运用节点 1,2……n+1 建立最短路问 题,其中弧(i,j)的费用是 f(i,j).从节点 1 到节点 n+1 的最短路是什么
数据压缩中的应用:近似分段线性函数 输入:分段线性函数 — n 个 点 ,a1=(x1,y1),a2=(x2,y2),… , an=(xn,yn) —x1<=x2<= … d(i) + cij then d(j) : = d(i) + cij and pred(j) : = i;
至此,从节点 1 到 j 的最短路长 78.
最短路算法的关键步骤 令 d( )代表暂时的标签距离向量 d(j)是从起始节点到节点 j 的路径的 距离. 刷新程序
Procedure Update(i) For each (i,j)∈A(i) do if d(j) > d(i) + cij then d(j) : = d(i) + cij and pred(j) : = i;
Dijkstra 算法 距离初始化 LIST= 暂 时 节点集.
从 LIST 中选 择标签距离最 小的节点 i, 执 行刷新程序

下一页