动态环境下最短路径树算法的分析与研究

《动态环境下最短路径树算法的分析与研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ｍＫｐｄＬ＾论文题目：动态环境下最短路径树算法的分析与研究雜＇’工程领域：ｆ．软化释＇＾ｖ：Ｂ５５ｉ＾学习方式：巨全日制攻读□在职攻读＾＾ｉＩ作者姓名：娜靴ｉ＾ｉｉＨ．ＨＺｉｗＨｉ学校导师：武麵教授＾企业导师：武京蠢完成日期－－：二〇？｛针月ＳＢＳＳｔＳ：ＨＢＨＢＳ陰路‘，＾＾■■■１■■曲：ｌｕ＂独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加Ｗ标注和致谢之处外，论文中不包含其他人己经发表

2、或撰写过的研究成果，也不包含为获得天津工业大学或其他教育机构的学位或证书而使用过的材料一。与我同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。学位论文作者签名；同签字曰期年３月曰捉色若３学位论文版权使用授权书本学位论文作者完全了解天津工业大学有关保留、使用学位论文的规定。特授权去達王坐去＾可Ｗ将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编Ｗ供查阅和借阅。同意学校向国家有关部口或机构送交论文的复印件和磁盘。

3、（保密的学位论文在解密后适用本授权说明）口学位论文作者签名：本女妾＾导师签名：＾球巧］签字日期：心ｆｔ年３月３日签字日期：３月３日学位论文的主要创新点一、最短路径树的问题是多领域的研究热点，在动态网络中亦是如此。然而动态网络的状态会随着时间发生变化，有些变化不是很明显，有些却频繁的发生变化甚至会影响到整个网络的维护，１）无论。最典型的动态网络是交通网络交通流量Ｄｉｓｔｒａ如何变化，它的拓扑结构是不变的。两点之间静态的最短路径可Ｗ利用算Ａ法预先计算出来。（２）交通流量发生变化且变化不

4、是均匀分布的，如高峰时期，某些路段的交通流量会成倍的增加。（３）当有路段的交通流量频繁的发生变化时，任意两结点间的最短路径可能会频繁的发生改变。当发生交通事故或上下班等高峰期时，交通网络中某些路段的交通流量不稳定，容易发生拥堵。针对Ｗ上问题，本文提出不稳定边的概念，即频繁发生变化或者是发生频率高的变化，将这些易于发生变化的边称为不稳定边，，。由于存在不稳定边如果追求实时的最短路径那么最短路径将极不稳定，，使得。这样虽每次都找到的是最短路径但是反复的查找和更改计算速度很慢导致最后实时性很难保证

5、。所Ｗ不管是频繁发生变化还是发生频率高的边，我们认为都是影咱最短路径树不稳定的因素。二、找到了影响最短路径树不稳定的因素，就得找到稳定的最短路径树。不稳定边的实时变化使得实时重复计算最短路径，这样不仅对计算机硬件要求较高而且实时性也难保障。况且随着网络规模的增大，频繁的计算最短路径不是很有效一的解决方法レ：Ｊ，。所？本文提出种稳定的最短路径树算法该算法根据静态网络拓扑图中的静态数据计算出初始的最短路径树，利用该初始数据可重新更新新的最短路径树，，在重计算之前需要判断变化的链路对当前的最短路径

6、树是否有影响无影响，则不需要重新计算，。对于不稳定边我们需要统计并做相关处理送样在构建新的最短路径树时，尽量使新旧最短路径树的差异很小，，减少被更新的结点从而维持一个相对稳定的最短路径树。摘要随着传感器技术，通信技术，计算机技术的不断发展，在现实生活和实际应用中，，最短路径问题都起着非常重要的作用。如在交通网络中需要找到最佳的行车路线，使得快速到达目的地。在物流配送中，物流公司不仅要考虑物流的速度还要考虑物流的成本，这些现实问题都可Ｗ通过建模，最终形式化为最短路径的问题，从而利用经典

7、的算法来解决实际的问题。，，近些年对最短路径树的问题被广泛研究，己得到很多成熟稳定的静态算法然而，随着网络规模和网络需求的变化，这些算法已无法满足动态网络的需求。动态网络的状态会随着时间发生变化，如果要得到最短路径，那么实时的变化就要频繁的重新计算最短路径，反复地计算不仅消耗大量时间，也会导致最短路径树的频繁变化，最终使得最短路径树变得极其不稳定。本文通过对＾心往动态算法的分析提出了不稳定边的概念，对不稳定边进行分析和统计，通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中，一从

8、而能够高效地减少边变化带来的操作。为此，我们提出了种稳定的最短路径，树构造算法，该算法与Ｗ往算法相比能使构造的路径树在动态网络上更稳定，即更新最短路径树所需的操作数更少，我们在随机网络。为了测试该算法的性能，环境中进行了科学的实验与传统的动态最短路径树算法相比，。实验结果表明本文的算法可Ｗ得到更稳定的最短路径树，并