通信学报
通信學報
통신학보
Journal on Communications
2015年
8期
38-49
,共12页
李艳%武优西%黄春萍%张志颖%曾珍香
李豔%武優西%黃春萍%張誌穎%曾珍香
리염%무우서%황춘평%장지영%증진향
有向无环图%长度约束%不相交路径%网树
有嚮無環圖%長度約束%不相交路徑%網樹
유향무배도%장도약속%불상교로경%망수
directed acyclic graph%length constraint%disjoint path%nettree
对有向无环图中具有长度约束的最大不相交路径问题进行研究,该问题是求解图中两点间路径长度为k的最大不相交路径.为了对该问题进行求解,提出了贪婪搜索算法(GP,greedy path),该算法先将一个有向无环图转化为一棵深度为k+1的网树,然后计算每个网树节点的树根叶子路径数,并以此计算图中每个顶点的总路径数,之后从网树的第k+1层节点出发,在当前节点的双亲节点中选择未被使用且总路径数最小的双亲,以此形成一条优化的不相交路径,最后迭代这一过程,直到不再有新的不相交路径为止.GP算法的时间和空间复杂度分别为O(wkn(p+q))和O(kn(p+q)+n2).为了测试GP算法的近似性,又建立了一种能够生成人工数据的算法,该算法能够准确地控制有向无环图中最大不相交路径的数量.通过该算法生成了大量测试用数据,实验结果表明GP算法较其他对比性算法具有良好的近似性且实际求解时间较短,验证了该方法的有效性和可行性.
對有嚮無環圖中具有長度約束的最大不相交路徑問題進行研究,該問題是求解圖中兩點間路徑長度為k的最大不相交路徑.為瞭對該問題進行求解,提齣瞭貪婪搜索算法(GP,greedy path),該算法先將一箇有嚮無環圖轉化為一棵深度為k+1的網樹,然後計算每箇網樹節點的樹根葉子路徑數,併以此計算圖中每箇頂點的總路徑數,之後從網樹的第k+1層節點齣髮,在噹前節點的雙親節點中選擇未被使用且總路徑數最小的雙親,以此形成一條優化的不相交路徑,最後迭代這一過程,直到不再有新的不相交路徑為止.GP算法的時間和空間複雜度分彆為O(wkn(p+q))和O(kn(p+q)+n2).為瞭測試GP算法的近似性,又建立瞭一種能夠生成人工數據的算法,該算法能夠準確地控製有嚮無環圖中最大不相交路徑的數量.通過該算法生成瞭大量測試用數據,實驗結果錶明GP算法較其他對比性算法具有良好的近似性且實際求解時間較短,驗證瞭該方法的有效性和可行性.
대유향무배도중구유장도약속적최대불상교로경문제진행연구,해문제시구해도중량점간로경장도위k적최대불상교로경.위료대해문제진행구해,제출료탐람수색산법(GP,greedy path),해산법선장일개유향무배도전화위일과심도위k+1적망수,연후계산매개망수절점적수근협자로경수,병이차계산도중매개정점적총로경수,지후종망수적제k+1층절점출발,재당전절점적쌍친절점중선택미피사용차총로경수최소적쌍친,이차형성일조우화적불상교로경,최후질대저일과정,직도불재유신적불상교로경위지.GP산법적시간화공간복잡도분별위O(wkn(p+q))화O(kn(p+q)+n2).위료측시GP산법적근사성,우건립료일충능구생성인공수거적산법,해산법능구준학지공제유향무배도중최대불상교로경적수량.통과해산법생성료대량측시용수거,실험결과표명GP산법교기타대비성산법구유량호적근사성차실제구해시간교단,험증료해방법적유효성화가행성.