计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2012年
5期
48-49,80
,共3页
最大度%度约束%改进算法%最小生成树
最大度%度約束%改進算法%最小生成樹
최대도%도약속%개진산법%최소생성수
度约束最小生成树问题是网络设计和优化中的一个NP-hard问题.提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法.算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析.最后通过与其他算法的仿真比较,表明新算法的有效性和通用性.
度約束最小生成樹問題是網絡設計和優化中的一箇NP-hard問題.提齣一種求解網絡G關于指定節點的最大度約束最小生成樹的改進算法.算法在保證指定節點最大度的前提下,通過選取剩餘邊中權最小的邊加入噹前網絡,得到網絡G關于指定節點的最大度最小生成樹,同時對算法的複雜度進行瞭分析.最後通過與其他算法的倣真比較,錶明新算法的有效性和通用性.
도약속최소생성수문제시망락설계화우화중적일개NP-hard문제.제출일충구해망락G관우지정절점적최대도약속최소생성수적개진산법.산법재보증지정절점최대도적전제하,통과선취잉여변중권최소적변가입당전망락,득도망락G관우지정절점적최대도최소생성수,동시대산법적복잡도진행료분석.최후통과여기타산법적방진비교,표명신산법적유효성화통용성.
