噶米网络单纯形算法课件.ppt

上传人(卖家):三亚风情 文档编号:3342186 上传时间:2022-08-22 格式:PPT 页数:45 大小:322KB
下载 相关 举报
噶米网络单纯形算法课件.ppt_第1页
第1页 / 共45页
噶米网络单纯形算法课件.ppt_第2页
第2页 / 共45页
噶米网络单纯形算法课件.ppt_第3页
第3页 / 共45页
噶米网络单纯形算法课件.ppt_第4页
第4页 / 共45页
噶米网络单纯形算法课件.ppt_第5页
第5页 / 共45页
点击查看更多>>
资源描述

1、115.082 和和 6.855J网络单纯形动画网络单纯形动画2计算生成树流计算生成树流136452713-6-4123有供应和需求的树有供应和需求的树.(假设所有的其他弧假设所有的其他弧的流是的流是0)在弧在弧(4,3)中的流是中的流是什么?什么?3计算生成树流计算生成树流136452713-6-4123为了计算流,向上为了计算流,向上迭代树,寻找流能迭代树,寻找流能唯一确定的弧唯一确定的弧.在弧在弧(5,3)中的流是中的流是什么?什么?24计算生成树流计算生成树流136452713-6-4123在弧在弧(3,2)中的流是中的流是什么?什么?235计算生成树流计算生成树流136452713-

2、6-4123在弧在弧(2,6)中的流是中的流是什么什么?2366计算生成树流计算生成树流136452713-6-4123在弧在弧(7,1)中的流是中的流是什么什么?23647计算生成树流计算生成树流136452713-6-4123在弧在弧(1,6)中的流是中的流是什么什么?236438计算生成树流计算生成树流136452713-6-4123注释注释:有两中不同的有两中不同的方法计算在方法计算在(1,2)的流的流,两种方法都给出流,两种方法都给出流为为 4.这是巧合吗?这是巧合吗?2364439计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413这里是有弧代价的生这里是有

3、弧代价的生成树成树.如何选择结点势如何选择结点势以便即约代价是以便即约代价是0呢呢?回忆回忆:(i,j)的即约代的即约代价是价是 cij-i+j1013645275-6-2-413 1 可以被任意设置可以被任意设置.我们令我们令 i=0.结点结点 2 的单纯形乘子的单纯形乘子是什么?是什么?在最小代价流问题中在最小代价流问题中,有一个多余的限制,有一个多余的限制.0计算生成树的单纯形乘子计算生成树的单纯形乘子11计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413结点结点 7 的单纯形乘子的单纯形乘子是什么?是什么?0(1,2)的即约代价是的即约代价是c12-1+2 =

4、0.因此因此5-0+2 =0.-512计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413结点结点 3 的单纯形乘子的单纯形乘子是什么?是什么?0(7,1)的即约代价是的即约代价是c12-1+2 =0.c71-7+1 =0.因此因此-6-7 +0=0.-5-613计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413结点结点 6 的单纯形乘子的单纯形乘子是什么?是什么?0-5-6-214计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413结点结点 4 的单纯形乘子的单纯形乘子是什么?是什么?0-5-6-2-115计算生成树的

5、单纯形乘子计算生成树的单纯形乘子13645275-6-2-413结点结点 5 的单纯形乘子的单纯形乘子是什么?是什么?0-5-6-2-1-416计算生成树的单纯形乘子计算生成树的单纯形乘子13645275-6-2-413有单纯形乘子和这棵有单纯形乘子和这棵树相关树相关.它们不依弧它们不依弧流,也不依赖流,也不依赖非树弧非树弧上上的代价的代价.0-5-6-2-1-4-117网络单纯形算法网络单纯形算法124532-42,$44,$21,$45,$53,$5 4,$14,$23,$45-3最小代价流问题最小代价流问题TLU18生成树流生成树流124532-410032 0135-3初始生成树解初始

6、生成树解TLU19单纯形乘子和即约代价单纯形乘子和即约代价124530-40?400-2023-2初始单纯形乘子和即约代价初始单纯形乘子和即约代价TLUc45=2什么弧是违规的?什么弧是违规的?320添加违规弧到生成树,创建圈添加违规弧到生成树,创建圈124533,2 4,04,13,3弧弧(2,1)添加到了树中添加到了树中TLU圈是什么,能圈是什么,能发送多少流?发送多少流?2,14,01,05,3u14,x1421环绕圈发送流环绕圈发送流124533,0 4,24,33,3沿着圈发送沿着圈发送2 单位的流单位的流TLU下一个生成树下一个生成树是什么?是什么?2,14,01,05,3u14,

7、x1422旋转旋转(pivot)之后之后124533,0 4,24,33,3更新的生成树更新的生成树TLU在旋转中,一条在旋转中,一条弧加入到弧加入到 T,而而另一条弧从另一条弧从 T 删删除除.2,14,01,05,3u14,x1423更新乘子更新乘子12453当前乘子和即约代价当前乘子和即约代价TLU0-404400-2023-23我们如何使我们如何使c 21=0,且让,且让其他树弧有其他树弧有 0 即约代价?即约代价?24从从 T 删除删除(2,1)把把 T 分裂成两部分分裂成两部分12453添加添加 到树的一侧不影响任何树到树的一侧不影响任何树弧的即约代价,除了弧的即约代价,除了(2,

8、1).为为什么什么?TLU0-404400-2023+-2+3应该选择什么应该选择什么样的样的 值,值,产生即约代产生即约代价价(2,1)=0?25更新的乘子和即约代价更新的乘子和即约代价12453更新的乘子和即约代价更新的乘子和即约代价.TLU0-402202 0021-43这棵树的解是这棵树的解是最优的吗?最优的吗?26添加一条违反弧到生成树,创建圈添加一条违反弧到生成树,创建圈12453添加弧添加弧(3,4)到生成树到生成树TLU3,0 4,24,33,32,14,01,05,3圈是什么,能圈是什么,能发送多少流?发送多少流?27沿圈发送流沿圈发送流12453沿圈发送沿圈发送1 个单位的

9、流个单位的流.TLU3,0 4,24,23,22,24,01,05,3下一个生成树下一个生成树解是什么?解是什么?28下一个生成树解下一个生成树解12453这是更新的生成树解这是更新的生成树解TLU3,0 4,24,23,22,24,01,05,329更新的乘子更新的乘子12453这是当前乘子这是当前乘子.TLU0-402202 0021-43我们如何修改我们如何修改乘子?乘子?30更新的乘子更新的乘子12453这是更新的乘子这是更新的乘子.TLU0-4+02202 0021-43 应该是什应该是什么值么值?31更新的乘子更新的乘子12453这是更新的乘子这是更新的乘子.TLU0-6-2420

10、2 0001-43当前生成树解当前生成树解是最优的吗?是最优的吗?32最优解最优解12453这是最优解这是最优解.TLU0-6-24202 0001-43没有弧违反最没有弧违反最优条件优条件.33寻找圈寻找圈1361011879125234使用深度和前驱使用深度和前驱13610118791252024depth(5)=4;depth(3)=2;用用 pred(5)替换结点替换结点535使用深度和前驱使用深度和前驱13610118791252023depth(9)=3;depth(3)=2;用用 pred(9)替换结点替换结点936使用深度和前驱使用深度和前驱13610118791252022d

11、epth(2)=2;depth(3)=2;用用 pred(2)替换结点替换结点2;用用 pred(3)替换结点替换结点337使用深度和前驱使用深度和前驱13610118791252011depth(8)=1;depth(7)=1;用用 pred(8)替换结点替换结点8;用用 pred(1)替换结点替换结点738使用深度和前驱使用深度和前驱136101187912520结点结点3和和5的的最小共同祖最小共同祖先被找到先被找到.39更新乘子:使用线和深度更新乘子:使用线和深度13610118791252假设弧假设弧(1,8)将从树中删将从树中删除除.以结点以结点8为根的子树为根的子树是什么?是什么

12、?40跟随从结点跟随从结点8开始的线开始的线13610118791252什么是什么是thread(8)?41跟随从结点跟随从结点8开始的线开始的线13610118791252什么是什么是thread(3)?42跟随从结点跟随从结点8开始的线开始的线13610118791252什么是什么是thread(10)?43跟随从结点跟随从结点8开始的线开始的线13610118791252什么是什么是thread(11)?44跟随从结点跟随从结点8开始的线开始的线13610118791252什么是什么是thread(6)?45停止规则停止规则13610118791252停止规则停止规则:当当depth(当当前结点前结点)depth(8)的时的时候停止候停止depth=1depth=1

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(噶米网络单纯形算法课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|