计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2014年
12期
3414-3416,3457
,共4页
MPH算法%加权节点%Steiner树%启发式算法%最短路径
MPH算法%加權節點%Steiner樹%啟髮式算法%最短路徑
MPH산법%가권절점%Steiner수%계발식산법%최단로경
Minimum cost Path Heuristic (MPH) algorithm%weighted node%Steiner tree%heuristic algorithm%shortest path
Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择.为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法.该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树.对STEINLIB标准数据集中的部分数据进行计算,结果表明:NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法;NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法.
Steiner最小樹問題是一箇NP完全問題,被廣汎應用在通信網絡中點到多點的路由選擇.為瞭實現更多鏈路的共享,減少所求Steiner樹的費用,提齣瞭一種基于加權節點求解Steiner樹的啟髮式(NWMPH)算法.該算法構造瞭非正則點的權值公式,給每一箇非正則點賦權值,根據權值對鏈路的費用進行脩正,通過脩正費用最短路徑依次把所有的正則點連接起來,得到包含所有正則點的最小樹.對STEINLIB標準數據集中的部分數據進行計算,結果錶明:NWMPH算法與MPH算法所用時間基本相同,得到的Steiner樹費用優于MPH算法;NWMPH算法比KBMPH算法所用時間少,得到的Steiner樹費用絕大多數優于KBMPH算法.
Steiner최소수문제시일개NP완전문제,피엄범응용재통신망락중점도다점적로유선택.위료실현경다련로적공향,감소소구Steiner수적비용,제출료일충기우가권절점구해Steiner수적계발식(NWMPH)산법.해산법구조료비정칙점적권치공식,급매일개비정칙점부권치,근거권치대련로적비용진행수정,통과수정비용최단로경의차파소유적정칙점련접기래,득도포함소유정칙점적최소수.대STEINLIB표준수거집중적부분수거진행계산,결과표명:NWMPH산법여MPH산법소용시간기본상동,득도적Steiner수비용우우MPH산법;NWMPH산법비KBMPH산법소용시간소,득도적Steiner수비용절대다수우우KBMPH산법.
