文档介绍：#甪’::.:
——年签字日期:兰皇\矽签字日期:力啦:￡:丝多中国科学技术大学学位论文原创性声明中国科学技术大学学位论文授权使用声明叼公开本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除己特别加以标注和致谢的地方外,论文中不包含任何他人已经发表或撰/作为申请学位的条件之一,学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权,即:学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅,可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索,可以采用影印、缩印或扫写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名:签字日期:描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。导师签名:
目录Ⅲ目录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯第滦髀邸研究背景和意义.⋯⋯.⋯.⋯.⋯.⋯.⋯.⋯⋯⋯⋯.⋯..⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.缌鞲攀觥惴ā惴最短增广路算法第卵谷胫乇昙亲畲罅魉惴ā预流算法简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯...ち魉惴ḿ蚪椤压入重标记算法的实施⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.谷胫乇昙撬惴ǖ氖凳第伦芙嵊胝雇总结......⋯.⋯.⋯.........⋯....⋯⋯.........⋯....展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.巧俎拐殂殂
原书空白页不缺内容
摘要网络流算法问题是图论中经典的算法问题嗍木渌惴ㄓ醚罢以广路方法,其中和乃惴ê虳的算法都是比较经典的。而提出来的预流的概念对于问题的理解更加的简单,产生了一些更高效的算法。我们在本文中在主要的结果和方法上引用,,的证明方法和结论,在一些小的证明上和以上的证明方法稍有不同,并和经典的算法进行对比。我们对于压入重标记最大流算法这一算法进行了较为详细的讨论,在预流这一概念下,我们可以得到结论最大距离压入重标记最大流算法能够在他时间内实施。关键词:算法,最大流问题,预流,
膅’穉甒甒啦甋縨誳:琺—瓵,痑—琾——
第滦髀研究背景和意义研究背景~家生产零件的公司,有很多个大工厂,同时有很多的零售商店来销售零知的星期生产能力啦。零件必须从工厂运送到每个零售商店,对所有可能的数对,,单位运输零件所要的费用为唷N颐敲娑缘奈侍馐侨グ才抛钚》延的运输方式,来解决供需的要求。这样的“运输问题能是组合优化这一学科中最受关注的领域,虽然许多基本的结果在实际年代就已经得到了但是这一学科仍然是一个基础研究课题,应用颇多。最大流问题有一个很著名的结论就是最大流最小割问题,从大流最小割问题可以简单定理等重要定理。另外一方面由于最大流问题源于实际生活,所以也经常被用来解决实际问题,比如说公车系统中的车辆流问题,控制系统的信息流问题,时效性的热缢党盗玖魑侍庵校械穆坊盗瞬荒苡昧司鸵W羁斓恼业揭桓鲂在一个有礼个顶点的流中找到一个尽量少的时间让这个流达到最大,如何在~定的时间来完成这个事情叫一个算法。算法侵附馓夥桨傅淖既范暾拿枋觯且幌盗薪饩鑫侍的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。是这个算法是不是最优的笙嗉坛鱿至瞬簧俚母慕姆绞剑切矶嗟募更易于编程的算法件。所有的零售商店歹都有它已知的星期需求零件数酶,所有的工厂加幸是钚》延昧网络流问题的一个很朴素的例子。网络流畲罅理论可的证明定理,又定理可以简单的可以推导出定理,供水系统的水流问题,金融系统中的现金流问题等等。由于有的最大流是需要的最大流馐焙蛉绾尉】斓恼业秸飧鲎畲罅鳎褪且桓鍪导实奈侍狻R簿褪已知的最原始的最大流的算法是和囊桓龆嘞钍剿惴ǎ算数学编程的时候仍然在用最原始的那个多项式算法,是否会有一个更好的,在这样的背景之下,针对最大流算法的研究仍然是一个基础的研究课题而第绪论.”,
受到重视,其能在一定程度上提升系统对于突发事件的应对能力。:”大约从年起,计际上可能用卧怂憔湍芮蠼猓此菩栌觅次运算的问题实际上可能用卧怂憔湍艽恚襫通常还可以减少到。一些更难的问来,剩下的问题依然