一、用计算机生成连通图的最短生成树（论文文献综述）
刘婷婷[1]（2014）在《基于WMN的P2P流媒体组播若干关键技术研究》文中进行了进一步梳理随着互联网的发展,流媒体业务逐渐增多。视频点播、网络电视、远程会议、远程教育已成为互联网的热门应用。P2P （Peer to Peer,对等端到对等端）技术的产生使互联网的工作模式从以客户端/服务器为代表的集中式走向了分布式,为流媒体应用带来了新的发展空间。与此同时,无线Mesh网络（Wireless Mesh Networks, WMN）和移动通信设备的飞速发展使得人们对P2P流媒体业务的需求由有线网络转移到了无线网络。这种用户需求推动了基于WMN的P2P流媒体技术的发展,而WMN的广泛应用前景也吸引了P2P流媒体技术向无线网络的移植。基于WMN的P2P流媒体系统是P2P流媒体在WMN支撑下的应用层实现,由于WMN网络的特殊性,P2P技术在WMN中面临着许多挑战与问题。例如,由于无线网络终端种类繁多造成的网络异构性问题、P2P覆盖层网络与底层网络的拓扑不匹配问题、无线网络链路干扰问题、无线频谱资源有限问题和缺少系统级实验平台的问题。针对上述研究背景和P2P流媒体技术在WMN环境中遇到的问题,本论文在传统的有线网络P2P流媒体组播技术的基础上,从理论和实验两个方面对WMN中的P2P流媒体组播技术进行了研究。论文的主要研究内容和创新点包括：（1）针对覆盖层网络与底层网络的拓扑不匹配问题和无线网络节点异构性问题,提出了一种无线网络通用的应用层组播成员管理协议。该协议通过采用“闲谈”机制、局部概率择优策略和去中心化管理策略,构造了一个稳定的、无标度的覆盖层网络,实现了组播组成员的动态加入与退出管理。基于复杂网络理论对所提协议进行的数学分析证明了其构造的覆盖层网络是稳定的。仿真结果表明,所提出的协议在一定程度上能缓解拓扑不匹配问题,而且比已有的协议模型更能适应异构无线网络环境。（2）针对无线链路干扰问题,提出了一种低代价最少中继树组播路由算法。该算法由组播树构造算法和信道分配算法两部分组成。组播树构造算法在保证中继节点数目最少的同时尽量选择低代价路径进行数据转发,从而充分利用无线链路的一跳广播属性并且降低了端到端时延。信道分配算法通过扩大干扰优化范围、引入更精确的衡量干扰的参数,优化了已有的信道分配算法,从而减少了链路干扰。算法分析和仿真结果表明,所提出的低代价最少中继树组播路由算法降低了已有组播树算法的时间复杂度和组播树代价,减少了用户时延,提高了系统吞吐量。（3）针对无线频谱资源有限和客户端资源受限问题,提出了一种基于SNR（Signal Noise Ratio,信噪比）反馈的多信道组播调度机制。该机制通过SNR反馈判断信道容量的大小,采用将优先级较高的数据块放在信道容量较大的信道上进行传输的策略,减小了流媒体启动时延和下载时间,提高了信道利用率。仿真结果表明,所提出的调度机制与原有调度机制相比,在用户时延、下载时间和带宽利用率方面的性能都有所提高,但其耗费的缓存空间略大于原有调度机制。经分析,在硬件技术日趋发达的今天,存储空间的获取对用户来讲并不困难。而在存储空间充足的条件下,用户对时间的敏感度明显高于对空间的敏感度,因此用少量空间换取时间的做法是可取的。（4）针对缺少系统实验平台的问题,实际搭建了基于WMN的P2P流媒体系统。为了客观和精确地评估WMN中的P2P流媒体性能,启发与流媒体性能相关的下一步研究,在搭建的系统平台上通过现场实验的方式测试了流媒体编解码方式、编码速率、P2P方式的采用与否、跳数和网络拓扑结构五个因素对流媒体性能的影响。实验结果表明,编码方式、编码速率和网络拓扑都是影响视频质量的重要因素;跳数与视频质量没有必然的联系；P2P技术与WMN结合是可行的,但是采用P2P方式对WMN中流媒体质量的影响有利有弊。实验结果对今后的理论创新和实践部署都具有很好的参考意义。
王鑫,沈致和[2]（2010）在《天然气管网定线研究》文中提出在分析和研究最新给水管网计算和物流输配计算的基础上,对天然气管网的设计方案进行了评价,使用图论方法分析了天然气管网的定线问题,并在最短生成树的基础上尝试使用贪心算法定量的讨论天然气调压站选址,以使得天然气初投资最省。
韩帅[3]（2010）在《埕岛油田集输管网调整优化技术研究》文中研究表明胜利埕岛油田为了适应滚动开发的需要,集输管网分期分批建成,没有统一的规划和设计,存在流量分布不均,布局不合理的问题,而且一些边远区块的集输半径较大,集输管网末端干压已经达到2.0MPa,对油井举升工艺和管道运行安全产生较大影响。随着油田勘探开发不断深入,根据油藏调整规划,需新打312口加密调整井,新建产能约247万吨,且规划建设中心三号平台,因此需要对目前的管网布局进行调整,优化管网结构,确定新增油井的连入点位置以及管径大小,实现新增产能顺利进入集输系统,同时解决目前管网存在的问题。本文根据海上油田集输管网的实际情况,将管网的布局优化问题分解为三个子问题:卫星平台分组优化、中心平台选址优化和管网布置优化。基于产量距离的概念,建立了卫星平台分组优化模型,并利用遗传算法求解;结合图论中网络图的加权中心的概念,建立了中心平台选址优化模型,利用Warshall算法求解;对于管网布置优化,文中建立了最小生成树模型和遗传算法模型,分别应用Prim算法和改进的单亲遗传算法进行求解,并利用建立的海底管线费用模型对两种模型的优化结果进行比较分析,最小生成树模型得到的管网总长度最短,但管网投资却不是最省的,而且存在集输半径较大,管网流量分配不均的问题,而遗传算法模型则直接以管网的投资为优化目标,考虑了管网中流量分配对投资的影响,得到的管网不仅投资省,而且流量分布、水力性能都较优。结合埕岛油田的实际平台分布,利用本文的布局优化方法得到了一个优化的管网布局,与现有管网相比可以节省约15%的投资。根据油田后期开发规划,优化了中心三号平台的位置,给出了中心三号平台投产前后的管网布局调整方案,并利用PIPEPHASE软件优化新建管线的管径,模拟了管网的水力状况,模拟结果表明调整优化后的管网流量分布均匀,大多数平台回压都控制在1MPa左右。本文的研究成果可以为埕岛油田的油藏调整及二次开发规划方案提供直接的参考依据,对集输管网的规划设计具有重要指导意义。同时也可以应用于其它海底油气田集输管网的规划设计,对降低地面工程投资和生产运行成本,提高油田的整体效益具有重要意义。
王鑫[4]（2010）在《城镇天然气管网优化设计研究》文中研究指明城镇天然气系统是城市建设和发展的重要基础设施,是保障人民生活和发展的不可缺少的物质基础,而天然气管网是一个较复杂的系统,从调压站的选址,管网的定线到天然气管网的水力计算,需要考虑到各种因素的影响。尤其是调压站的选址和管网的定线,这两项和天然气输配系统的实用性和经济性息息相关,因此对管网进行优化设计具有重要的作用和意义。本文在分析和研究最新给水管网计算和物流输配计算的基础上,对天然气管网的设计方案进行了评价。使用图论方法分析了天然气管网的定线问题,并在最短生成树的基础上尝试使用贪心算法定量讨论天然气调压站选址问题,以使得天然气管网初投资最省。最后将该优化设计方法利用到一工程实例中,分析其原有方案,并将新的计算结果与原有方案进行比较,表明该方法在工程设计中有一定的实用价值。
陈进殿,汪玉春,黄泽俊[5]（2006）在《天然气管网系统最优化研究》文中研究说明在对天然气管网优化问题进行描述和分析的基础上,介绍了自20世纪80年代以来国内外的研究成果。在传统的研究中,基于递阶优化思路建立的天然气管网系统优化模型不能从整体上反映系统的本质,所求得的解往往也不是全局最优解。开拓新的思路,建立能够涵盖管网规划、设计和运行管理等多阶段的优化模型,将是今后天然气管网优化问题的一个研究方向。同时,应将新兴的智能优化算法引入管网的优化问题中,将多种方法有机结合,优势互补,强化管网优化计算方法的通用性。
师涛[6]（2002）在《用计算机生成连通图的最短生成树》文中研究指明手工计算最短生成树是十分困难的 ,必须通过计算机辅助进行 ,利用图的邻接矩阵将图的问题转化为数学计算问题 ,从而借助计算机加以解决。
二、用计算机生成连通图的最短生成树（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、用计算机生成连通图的最短生成树（论文提纲范文）
（1）基于WMN的P2P流媒体组播若干关键技术研究（论文提纲范文）
| 致谢 |
| 中文摘要 |
| ABSTRACT |
| 目录 |
| 1 绪论 |
| 1.1 引言 |
| 1.1.1 P2P流媒体技术简介 |
| 1.1.2 无线Mesh网络技术简介 |
| 1.2 研究背景与意义 |
| 1.2.1 WMN与P2P结合的必然性 |
| 1.2.2 WMN与P2P结合的可行性 |
| 1.2.3 基于WMN的P2P流媒体应用前景与意义 |
| 1.3 相关技术研究现状与问题分析 |
| 1.3.1 基于WMN的P2P流媒体组播相关技术 |
| 1.3.2 基于WMN的P2P流媒体系统面临的问题 |
| 1.4 论文的主要内容和创新点 |
| 1.5 论文结构 |
| 2 通用P2P应用层组播成员管理协议 |
| 2.1 引言 |
| 2.1.1 应用层组播简介 |
| 2.1.2 P2P覆盖层网络结构模型 |
| 2.1.3 基于Gossip的应用层组播成员管理协议 |
| 2.2 BA-Gossip应用层组播成员管理协议设计 |
| 2.2.1 定义 |
| 2.2.2 BA-Gossip应用层组播成员管理协议过程 |
| 2.2.3 局部概率择优策略 |
| 2.2.4 去中心化管理 |
| 2.3 BA-Gossip组播协议建模与分析 |
| 2.3.1 BA-Gossip增长网络模型 |
| 2.3.2 BA-Gossip进化网络模型 |
| 2.4 仿真结果与分析 |
| 2.4.1 瞬时度分布 |
| 2.4.2 稳态度数 |
| 2.4.3 拓扑隔离度 |
| 2.4.4 平均节点度数 |
| 2.4.5 网络直径 |
| 2.5 本章小结 |
| 3 一种面向流媒体的WMN组播路由算法 |
| 3.1 引言 |
| 3.2 问题描述 |
| 3.2.1 定性分析 |
| 3.2.2 定量描述 |
| 3.3 LCMRT构造算法 |
| 3.3.1 算法思想 |
| 3.3.2 算法描述 |
| 3.3.3 算法时间复杂度分析 |
| 3.4 LCMRT信道分配算法 |
| 3.4.1 算法思想 |
| 3.4.2 算法描述 |
| 3.5 仿真结果与分析 |
| 3.6 本章小结 |
| 4 一种面向流媒体的 WMN 组播调度机制 |
| 4.1 引言 |
| 4.2 快速组播调度机制模型 |
| 4.3 基于SNR反馈的组播调度机制设计 |
| 4.3.1 系统模型 |
| 4.3.2 基于SNR反馈的组播调度机制 |
| 4.4 定量分析与仿真结果 |
| 4.4.1 用户启动时延 |
| 4.4.2 下载时间 |
| 4.4.3 带宽利用率 |
| 4.4.4 缓存空间需求 |
| 4.5 本章小结 |
| 5 基于WMN的P2P流媒体质量评估实验 |
| 5.1 引言 |
| 5.1.1 研究背景 |
| 5.1.2 影响流媒体质量的因素 |
| 5.1.3 流媒体性能评估方法 |
| 5.2 基于WMN的P2P流媒体性能评估实验平台设计 |
| 5.2.1 硬件平台 |
| 5.2.2 软件平台 |
| 5.3 实验结果与分析 |
| 5.3.1 编码方式对流媒体质量的影响 |
| 5.3.2 编码速率对流媒体质量的影响 |
| 5.3.3 P2P 方式采用与否对流媒体质量的影响 |
| 5.3.4 跳数对流媒体质量的影响 |
| 5.3.5 网络拓扑对流媒体质量的影响 |
| 5.4 本章小结 |
| 6 总结与展望 |
| 6.1 总结 |
| 6.2 展望 |
| 参考文献 |
| 图索引 |
| 表索引 |
| 作者简历及攻读博士学位期间取得的研究成果 |
| 学位论文数据集 |
（3）埕岛油田集输管网调整优化技术研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第一章 概论 |
| 1.1 课题目的及意义 |
| 1.2 国内外研究现状 |
| 1.2.1 研究现状 |
| 1.2.2 发展趋势 |
| 1.3 本文研究内容 |
| 1.3.1 研究内容 |
| 1.3.2 研究思路 |
| 1.3.3 研究重点与难点 |
| 第二章 集输管网的数学描述 |
| 2.1 图论基础 |
| 2.1.1 图的概念 |
| 2.1.2 图的矩阵表示 |
| 2.2 海底集输管网形式 |
| 2.2.1 海底集输管网构建模式 |
| 2.2.2 管网图的计算机实现 |
| 第三章 集输管网布局优化 |
| 3.1 平台最优分组 |
| 3.1.1 数学模型 |
| 3.1.2 模型求解 |
| 3.1.3 算例分析 |
| 3.2 中心平台选址 |
| 3.2.1 图论中的选址问题 |
| 3.2.2 中心平台的选址 |
| 3.2.3 算例分析 |
| 3.3 集输管网布局优化 |
| 3.3.1 海底管线的投资费用 |
| 3.3.2 集输管网布局优化模型 |
| 3.3.3 算例分析 |
| 3.4 小结 |
| 第四章 埕岛油田集输管网优化 |
| 4.1 工程概况 |
| 4.1.1 平台基础数据 |
| 4.1.2 已建管网资料 |
| 4.2 埕岛油田管网优化计算 |
| 4.2.1 已建管网的优化 |
| 4.2.2 2008-2009 年管网调整优化 |
| 4.2.3 未来管网整体规划 |
| 第五章 结论与建议 |
| 5.1 结论 |
| 5.2 建议 |
| 参考文献 |
| 致谢 |
（4）城镇天然气管网优化设计研究（论文提纲范文）
| 摘要 |
| Abstract |
| 致谢 |
| 第一章 绪论 |
| 1.1 燃气管网理论概述 |
| 1.2 课题研究的背景 |
| 1.3 燃气管网计算发展历程 |
| 1.4 天然气管网优化设计的发展历程 |
| 1.5 本文研究的主要内容 |
| 第二章 城镇天然气管网设计理论 |
| 2.1 天然气管网系统理论 |
| 2.1.1 城镇燃气管网介绍 |
| 2.1.2 燃气管道压力分级 |
| 2.2 天然气调压站设计理论 |
| 2.2.1 用气负荷 |
| 2.2.2 设计压力及运行压力 |
| 2.2.3 管网建设情况 |
| 2.2.4 调压流程的选择 |
| 2.3 天然气管网水力计算概述 |
| 2.3.1 解环方程法 |
| 2.3.2 解节点方程法 |
| 2.3.3 解管段方程法 |
| 第三章 城镇天然气管网定线理论 |
| 3.1 天然气管网定线的作用 |
| 3.2 图论基础与最短生成树概述 |
| 3.2.1 图论基础知识 |
| 3.2.2 最短生成树举例 |
| 3.2.3 使用Prim 算法求最短生成树 |
| 3.2.3.1 算法简介 |
| 3.2.3.2 算法举例 |
| 3.2.4 深度优先遍历 |
| 3.2.4.1 算法举例 |
| 3.2.5 删除不需要的节点算法举例 |
| 第四章 城镇天然气管网设计与水力计算实例 |
| 4.1 工程概况 |
| 4.1.1 工程背景 |
| 4.1.2 用气人口预测 |
| 4.1.3 道路状况及用气人口分布 |
| 4.1.4 初步规划 |
| 4.2 城镇天然气用气量计算 |
| 4.3 管道最优化 |
| 4.3.1 问题描述 |
| 4.3.2 三个假设 |
| 4.3.3 使用Prim 算法求最短生成树 |
| 4.3.3.1 Prim 算法思想 |
| 4.3.3.2 算法编程 |
| 4.3.4 深度优先遍历 |
| 4.3.4.1 算法思想 |
| 4.3.4.2 算法编程 |
| 4.3.5 选取调压站 |
| 4.4 水力计算 |
| 4.5 结果分析 |
| 第五章 结论与展望 |
| 参考文献 |
| 附录：C++程序全文 |
（5）天然气管网系统最优化研究（论文提纲范文）
| 一、问题描述 |
| 1、管网系统规划优化 |
| 2、管网系统设计优化 |
| 3、管网系统运行优化 |
| 二、问题分析 |
| 三、优化方法及其应用 |
| 1、基于图论的管网拓扑优化 |
| 2、基于离散优化策略的管网设计优化 |
| 3、基于混合离散优化策略的管网运行优化 |
| 4、其它优化理论和方法 |
| 四、结论 |
四、用计算机生成连通图的最短生成树（论文参考文献）
- [1]基于WMN的P2P流媒体组播若干关键技术研究[D]. 刘婷婷. 北京交通大学, 2014(12)
- [2]天然气管网定线研究[J]. 王鑫,沈致和. 山西建筑, 2010(19)
- [3]埕岛油田集输管网调整优化技术研究[D]. 韩帅. 中国石油大学, 2010(04)
- [4]城镇天然气管网优化设计研究[D]. 王鑫. 合肥工业大学, 2010(04)
- [5]天然气管网系统最优化研究[J]. 陈进殿,汪玉春,黄泽俊. 油气储运, 2006(02)
- [6]用计算机生成连通图的最短生成树[J]. 师涛. 石家庄师范专科学校学报, 2002(04)