




已阅读5页,还剩40页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
15.082和6.855J,网络单纯形动画,2,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,有供应和需求的树.(假设所有的其他弧的流是0),在弧(4,3)中的流是什么?,3,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,为了计算流,向上迭代树,寻找流能唯一确定的弧.,在弧(5,3)中的流是什么?,2,4,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,在弧(3,2)中的流是什么?,2,3,5,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,在弧(2,6)中的流是什么?,2,3,6,6,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,在弧(7,1)中的流是什么?,2,3,6,4,7,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,在弧(1,6)中的流是什么?,2,3,6,4,3,8,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,注释:有两中不同的方法计算在(1,2)的流,两种方法都给出流为4.这是巧合吗?,2,3,6,4,4,3,9,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,这里是有弧代价的生成树.如何选择结点势以便即约代价是0呢?,回忆:(i,j)的即约代价是cij-i+j,10,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,1可以被任意设置.我们令i=0.,结点2的单纯形乘子是什么?,在最小代价流问题中,有一个多余的限制.,0,计算生成树的单纯形乘子,11,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点7的单纯形乘子是什么?,0,(1,2)的即约代价是c12-1+2=0.因此5-0+2=0.,-5,12,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点3的单纯形乘子是什么?,0,(7,1)的即约代价是c12-1+2=0.c71-7+1=0.因此-6-7+0=0.,-5,-6,13,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点6的单纯形乘子是什么?,0,-5,-6,-2,14,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点4的单纯形乘子是什么?,0,-5,-6,-2,-1,15,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点5的单纯形乘子是什么?,0,-5,-6,-2,-1,-4,16,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,有单纯形乘子和这棵树相关.它们不依弧流,也不依赖非树弧上的代价.,0,-5,-6,-2,-1,-4,-1,17,网络单纯形算法,1,2,4,5,3,2,-4,2,$4,4,$2,1,$4,5,$5,3,$5,4,$1,4,$2,3,$4,5,-3,最小代价流问题,18,生成树流,1,2,4,5,3,2,-4,1,0,0,3,2,0,1,3,5,-3,初始生成树解,TLU,19,单纯形乘子和即约代价,1,2,4,5,3,0,-4,0,?,4,0,0,-2,0,2,3,-2,初始单纯形乘子和即约代价,TLU,c45=2,什么弧是违规的?,3,20,添加违规弧到生成树,创建圈,1,2,4,5,3,3,2,4,0,4,1,3,3,弧(2,1)添加到了树中,TLU,圈是什么,能发送多少流?,2,1,4,0,1,0,5,3,u14,x14,21,环绕圈发送流,1,2,4,5,3,3,0,4,2,4,3,3,3,沿着圈发送2单位的流,TLU,下一个生成树是什么?,2,1,4,0,1,0,5,3,u14,x14,22,旋转(pivot)之后,1,2,4,5,3,3,0,4,2,4,3,3,3,更新的生成树,TLU,在旋转中,一条弧加入到T,而另一条弧从T删除.,2,1,4,0,1,0,5,3,u14,x14,23,更新乘子,1,2,4,5,3,当前乘子和即约代价,TLU,0,-4,0,4,4,0,0,-2,0,2,3,-2,3,我们如何使cp21=0,且让其他树弧有0即约代价?,24,从T删除(2,1)把T分裂成两部分,1,2,4,5,3,添加到树的一侧不影响任何树弧的即约代价,除了(2,1).为什么?,TLU,0,-4,0,4,4,0,0,-2,0,2,3+,-2+,3,应该选择什么样的值,产生即约代价(2,1)=0?,25,更新的乘子和即约代价,1,2,4,5,3,更新的乘子和即约代价.,TLU,0,-4,0,2,2,0,2,0,0,2,1,-4,3,这棵树的解是最优的吗?,26,添加一条违反弧到生成树,创建圈,1,2,4,5,3,添加弧(3,4)到生成树,TLU,3,0,4,2,4,3,3,3,2,1,4,0,1,0,5,3,圈是什么,能发送多少流?,27,沿圈发送流,1,2,4,5,3,沿圈发送1个单位的流.,TLU,3,0,4,2,4,2,3,2,2,2,4,0,1,0,5,3,下一个生成树解是什么?,28,下一个生成树解,1,2,4,5,3,这是更新的生成树解,TLU,3,0,4,2,4,2,3,2,2,2,4,0,1,0,5,3,29,更新的乘子,1,2,4,5,3,这是当前乘子.,TLU,0,-4,0,2,2,0,2,0,0,2,1,-4,3,我们如何修改乘子?,30,更新的乘子,1,2,4,5,3,这是更新的乘子.,TLU,0,-4+,0,2,2,0,2,0,0,2,1,-4,3,应该是什么值?,31,更新的乘子,1,2,4,5,3,这是更新的乘子.,TLU,0,-6,-2,4,2,0,2,0,0,0,1,-4,3,当前生成树解是最优的吗?,32,最优解,1,2,4,5,3,这是最优解.,TLU,0,-6,-2,4,2,0,2,0,0,0,1,-4,3,没有弧违反最优条件.,33,寻找圈,1,3,6,10,11,8,7,9,12,5,2,34,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,2,4,depth(5)=4;depth(3)=2;用pred(5)替换结点5,35,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,2,3,depth(9)=3;depth(3)=2;用pred(9)替换结点9,36,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,2,2,depth(2)=2;depth(3)=2;用pred(2)替换结点2;用pred(3)替换结点3,37,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,1,1,depth(8)=1;depth(7)=1;用pred(8)替换结点8;用pred(1)替换结点7,38,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,结点3和5的最小共同祖先被找到.,39,更新乘子:使用线和深度,1,3,6,10,11,8,7,9,12,5,2,假设弧(1,8)将从树中删除.以结点8为根的子树是什么?,40,跟随从结点8开始的线,1,3,6,10,11,8,7,9,12,5,2,什么是thread(8)?,41,跟随从结点8开始的线,1,3,6,10,11,8,7,9,12,5,2,什么是thread(3)?,42,跟随从结点8开始的线,1,3,6,10,11,8,7,9,12,5,2,什么是thread(10)?,43,跟随从结点8开始的线,1,3,6
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年咸阳秦都怡心学校招聘考前自测高频考点模拟试题含答案详解
- 浙江国企招聘2025杭州临安文商旅集团有限公司7月公开招聘工作人员3人笔试历年参考题库附带答案详解
- 浙江国企招聘2025台州市商贸核心区开发建设投资集团有限公司公开招聘工作人员3人笔试历年参考题库附带答案详解
- 平武县国有资产监督管理办公室市场化招聘平武县光大国有投资(集团)有限公司高级管理人员笔试历年参考题库附带答案详解
- 2025陕西省西咸新区空港国际文化旅游产业投资有限公司招聘8人笔试历年参考题库附带答案详解
- 2025重庆市綦江区兴农融资担保有限责任公司招聘员工1人笔试历年参考题库附带答案详解
- 2025重庆合川燃气有限责任公司外包岗位招聘1人笔试历年参考题库附带答案详解
- 2025贵州纳雍县志宏就业扶贫劳务有限公司招聘10人笔试历年参考题库附带答案详解
- 2025贵州中建伟业建设(集团)建筑科技有限责任公司招聘笔试历年参考题库附带答案详解
- 2025福建福州市园林建设开发有限公司社会化人员招聘2人笔试历年参考题库附带答案详解
- 2025年未来就业报告
- 邮储银行存款课件
- 2024国家公务员考试地市级申论第2题(带标准答案)
- 工程建设施工项目管理人员职业标准
- GB/T 33285.2-2024皮革和毛皮烷基酚及烷基酚聚氧乙烯醚的测定第2部分:间接法
- 医院护理培训课件:《成人早期预警评分系统介绍》
- 2023保密知识测试题库含答案
- 危险化学品安全作业(氧化工艺)考试题库(含答案)
- 中国农业银行笔试题库(含答案)
- GA 1808-2022军工单位反恐怖防范要求
- 工程建设项目绿色建造施工水平评价申请表
评论
0/150
提交评论