图的Steiner最小树问题的算法与应用研究.pdf

《图的Steiner最小树问题的算法与应用研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、*11ft~:10293¥f;w.:---;:.;J.,=10120817147-?~1~£;J'ftB...-;--UrtJ~tLrn~~8Zffl~3=7-~31-~~~Jf~1Jjc]~1H1I~g~ffl$i~~ill:~~IJw"¥"'1500±~"-€!?-rt.::c-1=11:~Jt1£~a~Ji-....:=_.-~---__l_L-'-r---IJAlgorithmandApplicationResearchofSteinerTreeProbleminGraphsThesisSubmittedtoNanjingUniversity

2、ofPostsandTelecommunicationsfortheDegreeofMasterofScienceByWangXiaolongSupervisor:Prof.ZhaoLifengMarch2015::$:A'FaA?JT~~~~1ftii::X£ft1-AtE~·~f!lm.@rjjj:ir8JliJfJl.IffJl.Jt£1~8iUJf1LJ£5f!o,eft?JT~Q,~1Xt:p*fJ1U:IJo~t~ff:;foJ&t~jEntil!.:iJY'Li!~Xt:p:f~-g-;tt11EActl:1X:~~~~:i1~~~~*

3、·ili~~~~~~m~~~*$~X~ft·m~~~~~~~~~fflM~MM.~~-~I~~~~~*~nMmEn~W~~~B~~~tf~1~~~&~#~~7~··*A*&~x&w&m~~fl~~~~.~•*m-mffi~~$-fiff.*A15Hx~~mE~7:~OJij,{~m#rPJ00*~=*~flMffltt.Ji!X:H::X!¥1][~p14,fo~.:PX~;ft~~x~~oo~m~;m~~~m~x~~s~•*~W~A~~~m~~fi-~;PJij,*ffla;~p~ffilfW~x:f3:tia~1l11iiJ-¥f9:1~1¥,¥C

4、~::$:$fil:i!t::Z:.::$::;Z:Et!-=f:Z:t~IN~W~t~&l~~~~~ffi-ft.~x~0~c§gft~>~~m*~~*~*~~~~~.摘要图的Steiner最小树问题是经典的组合优化问题，在通信网络和电路设计等领域有广泛应用。该问题是一个NP难题，虽然有一些精确算法，但是随着网络规模的增大，这些算法的运行时间呈指数增长。为了能够在多项式时间内得到最优解或者近似最优解，寻找有效的启发式算法就显得尤为重要。本文对遗传算法和传统的启发式算法进行了改进，主要工作如下：1.针对基本遗传算法采用自适应规则，引入模拟退火思想，提出

5、了一种解决Steiner最小树问题的混合遗传算法并进行仿真实验。实验结果表明：与基本遗传算法相比，改进的混合遗传算法能够加快收敛速度，减少迭代次数，使得到的解更稳定。2.分析已有典型启发式算法，提出了一种基于加权节点的Steiner树启发式算法。该算法根据正则点对间的最短路径、节点的度数、与正则点连接的次数等计算出节点的权值，然后根据权值对最短路径的费用进行修正，通过修正费用最短路径将正则点添加到多播树中，从而实现更多链路的共享，降低整棵树的费用。3.为了模拟真实的通信网络来测试算法的性能，本文对Waxman算法进行改进，设计了一种逼近现实网络特性的随

6、机网络生成算法。用该算法生成不同规模的仿真网络，然后用启发式算法对仿真网络进行求解，结果表明基于加权节点的启发式算法是一个性能较好的算法。关键词：Steiner树，遗传算法，启发式算法，随机网络，组播IAbstractTheGraphicalSteinerTreeProblem(GSTP)isaclassicalcombinatorialoptimizationproblemthatappearsinmanypracticallyimportantapplications.TheproblemisaNPhard.Therearesomeaccurate

7、algorithm,butwiththeincreaseofnetworkscale,thealgorithmisexponentiallyrunningtime.Inordertogettheoptimalsolutionorapproximateoptimalsolutioninpolynomialtime,itisparticularlyimportanttosearchforeffectiveheuristicalgorithm.Inthispaper,thegeneticalgorithmandthetraditionalheuristica

8、lgorithmisimproved,themainworkisasfollows:1.Inv