西安交通大学学报
西安交通大學學報
서안교통대학학보
JOURNAL OF XI'AN JIAOTONG UNIVERSITY
2003年
10期
1012-1015
,共4页
高磊%张德运%王晓东%安智平
高磊%張德運%王曉東%安智平
고뢰%장덕운%왕효동%안지평
近似算法%拓扑分析%时间复杂度
近似算法%拓撲分析%時間複雜度
근사산법%탁복분석%시간복잡도
针对Berman近似算法k为3情况下的求解思想进行了改进.在使用Fibonacci堆求解出相应点对间最短距离的基础上,通过构建Voronoi域求出元组子树的耗费,并分析了Steiner树的网络拓扑结构以去除无用元组,从而简化拓扑,降低总体时间复杂度.在实验结果中,每个实例的过滤因子均大于0.9,有的甚至高达0.999,这表明大量无用的元组在进入评估阶段和构造阶段之前已被过滤掉,同时运行时间的减少也显示出改进算法在多播应用的路由寻径中更有效.
針對Berman近似算法k為3情況下的求解思想進行瞭改進.在使用Fibonacci堆求解齣相應點對間最短距離的基礎上,通過構建Voronoi域求齣元組子樹的耗費,併分析瞭Steiner樹的網絡拓撲結構以去除無用元組,從而簡化拓撲,降低總體時間複雜度.在實驗結果中,每箇實例的過濾因子均大于0.9,有的甚至高達0.999,這錶明大量無用的元組在進入評估階段和構造階段之前已被過濾掉,同時運行時間的減少也顯示齣改進算法在多播應用的路由尋徑中更有效.
침대Berman근사산법k위3정황하적구해사상진행료개진.재사용Fibonacci퇴구해출상응점대간최단거리적기출상,통과구건Voronoi역구출원조자수적모비,병분석료Steiner수적망락탁복결구이거제무용원조,종이간화탁복,강저총체시간복잡도.재실험결과중,매개실례적과려인자균대우0.9,유적심지고체0.999,저표명대량무용적원조재진입평고계단화구조계단지전이피과려도,동시운행시간적감소야현시출개진산법재다파응용적로유심경중경유효.
