科技信息
科技信息
과기신식
SCIENTIFIC & TECHNICAL INFORMATION
2008年
26期
82-84,44
,共4页
最短路径%最小生树%Steiner Tree%时延%时延拦动%组播路由
最短路徑%最小生樹%Steiner Tree%時延%時延攔動%組播路由
최단로경%최소생수%Steiner Tree%시연%시연란동%조파로유
Dijgtra标号算法是求从一点到网络其它各点之间最短路的重要算法,而最小生成树是求网络各点之间相互连接的整体代价最小的算法.两者之间算法过程以及思路都不同.然而,本文对这两个算法进行研究,发现这两种算法的本质是一致的.接着对算法进行推广,一种综合算法.并应用到组播路径构造上,经对许多事例分析.发现该算法不仅很好地解决了无约束组播和有时延约束组播的近似最优解的问题,同时对部分有时延和时延抖动组合约束问题也能进行快速求解,且复杂度不超过O(kmn2).
Dijgtra標號算法是求從一點到網絡其它各點之間最短路的重要算法,而最小生成樹是求網絡各點之間相互連接的整體代價最小的算法.兩者之間算法過程以及思路都不同.然而,本文對這兩箇算法進行研究,髮現這兩種算法的本質是一緻的.接著對算法進行推廣,一種綜閤算法.併應用到組播路徑構造上,經對許多事例分析.髮現該算法不僅很好地解決瞭無約束組播和有時延約束組播的近似最優解的問題,同時對部分有時延和時延抖動組閤約束問題也能進行快速求解,且複雜度不超過O(kmn2).
Dijgtra표호산법시구종일점도망락기타각점지간최단로적중요산법,이최소생성수시구망락각점지간상호련접적정체대개최소적산법.량자지간산법과정이급사로도불동.연이,본문대저량개산법진행연구,발현저량충산법적본질시일치적.접착대산법진행추엄,일충종합산법.병응용도조파로경구조상,경대허다사례분석.발현해산법불부흔호지해결료무약속조파화유시연약속조파적근사최우해적문제,동시대부분유시연화시연두동조합약속문제야능진행쾌속구해,차복잡도불초과O(kmn2).
