计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2010年
36期
40-42,47
,共4页
度%度约束%最小生成树%第k最小生成树%最小k度生成树
度%度約束%最小生成樹%第k最小生成樹%最小k度生成樹
도%도약속%최소생성수%제k최소생성수%최소k도생성수
针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小七度生成树的新算法.该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树.给出了算法实施的具体步骤,并证明了算法的正确性.最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性.
針對網絡設計和組閤優化中的度約束最小生成樹問題,基于第k最小生成樹的求解算法,提齣瞭一種求解網絡G關于指定節點的最小七度生成樹的新算法.該算法通過對網絡G的最小生成樹作最優可行變換,逐步構造齣指定節點的度數越來越接近度約束k的最小i度生成樹,最終得到瞭網絡G關于指定節點的最小k度生成樹.給齣瞭算法實施的具體步驟,併證明瞭算法的正確性.最後通過倣真結果和一箇運輸實例,錶明瞭該算法在解決度約束最小生成樹問題中的有效性.
침대망락설계화조합우화중적도약속최소생성수문제,기우제k최소생성수적구해산법,제출료일충구해망락G관우지정절점적최소칠도생성수적신산법.해산법통과대망락G적최소생성수작최우가행변환,축보구조출지정절점적도수월래월접근도약속k적최소i도생성수,최종득도료망락G관우지정절점적최소k도생성수.급출료산법실시적구체보취,병증명료산법적정학성.최후통과방진결과화일개운수실례,표명료해산법재해결도약속최소생성수문제중적유효성.
