图的Steiner最小树问题的降阶回溯算法
도적Steiner최소수문제적강계회소산법
Reduced-order backtracking algorithm for Graphical Steiner Minimum Tree Problem
  • 万方数据
    计算机工程与应用 계산궤공정여응용
    COMPUTER ENGINEERING AND APPLICATIONS
    2014年 7期 67-70,169 ,共5页

    刘艳芳%宁爱兵%王英磊

    류염방%저애병%왕영뢰

    图的Steiner最小树%最小生成树%回溯法%降阶算法 圖的Steiner最小樹%最小生成樹%迴溯法%降階算法
    도적Steiner최소수%최소생성수%회소법%강계산법
    graphical Steiner minimum tree%minimum spanning tree%backtracking algorithm%reduction algorithm
    图的Steiner最小树问题是经典的组合优化问题，是一个NP难题，在不同的领域有着广泛的应用。研究该问题的部分数学性质，在此基础上给出了该问题的初步降阶方法和下界子方法，形成一个新的回溯算法。该算法具有较低的时间复杂度，还给出了应用实例及其分析。
    도적Steiner최소수문제시경전적조합우화문제，시일개NP난제，재불동적영역유착엄범적응용。연구해문제적부분수학성질，재차기출상급출료해문제적초보강계방법화하계자방법，형성일개신적회소산법。해산법구유교저적시간복잡도，환급출료응용실례급기분석。
    Graphical Steiner Minimum Tree Problem(GSMTP)is a well-known optimization problem, which is a NP-hard problem and has many applications in various fields. This paper gives some mathematical properties of GSMTP, then proposes a reduction method and a method to calculate the lower bound of the GSMTP. The paper presents a backtracking algorithm for GSMTP which includes the lower bound method. It is proved to be efficient and can decrease the time complexity. In addition, series of examples and instances are solved and analyzed.
    원문보기 원문다운로드 사이트로이동
저자의 최근 논문