| 网树求解有向无环图中具有长度约束的最大不相交路径 |
| |
| 引用本文： | 李 艳,武优西,黄春萍,张志颖,曾珍香.网树求解有向无环图中具有长度约束的最大不相交路径[J].通信学报,2015,36(8):38-49. |
| |
| 作者姓名： | 李 艳 武优西 黄春萍 张志颖 曾珍香 |
| |
| 作者单位： | 1. 河北工业大学 经济管理学院，天津 300401：2. 河北工业大学 计算机科学与软件学院，天津 300401 |
| |
| 基金项目： | 国家自然科学基金资助项目(61370144); 国家社会科学基金资助项目(12CGL112); 河北省自然科学基金资助项目(F2013202138, G2012202068); 河北省教育厅重点基金资助项目(ZH2012038); 河北省科技支撑计划基金资助项目(14210102D) |
| |
| 摘 要： | 对有向无环图中具有长度约束的最大不相交路径问题进行研究，该问题是求解图中两点间路径长度为k的最大不相交路径。为了对该问题进行求解，提出了贪婪搜索算法(GP, greedy path)，该算法先将一个有向无环图转化为一棵深度为k+1的网树，然后计算每个网树节点的树根叶子路径数，并以此计算图中每个顶点的总路径数，之后从网树的第k+1层节点出发，在当前节点的双亲节点中选择未被使用且总路径数最小的双亲，以此形成一条优化的不相交路径，最后迭代这一过程，直到不再有新的不相交路径为止。GP算法的时间和空间复杂度分别为O(wkn(p+q))和O(kn(p+q)+n2)。为了测试GP算法的近似性，又建立了一种能够生成人工数据的算法，该算法能够准确地控制有向无环图中最大不相交路径的数量。通过该算法生成了大量测试用数据，实验结果表明GP算法较其他对比性算法具有良好的近似性且实际求解时间较短，验证了该方法的有效性和可行性。
|
| 关 键 词： | 有向无环图 长度约束 不相交路径 网树 |
| 收稿时间： | 7/7/2014 12:00:00 AM |
Nettree for maximum disjoint paths with length constraint in DAG |
| |
| Yan LI,You-xi WU,Chun-ping HUANG,Zhi-ying ZHANG,Zhen-xiang ZENG.Nettree for maximum disjoint paths with length constraint in DAG[J].Journal on Communications,2015,36(8):38-49. |
| |
| Authors: | Yan LI You-xi WU Chun-ping HUANG Zhi-ying ZHANG Zhen-xiang ZENG |
| |
| Affiliation: | 1. School of Economics and Management,Hebei University of Technology,Tianjin 300401,China;2. School of Computer Science and Software,Hebei University of Technology,Tianjin 300401,China |
| |
| Abstract: | The problem of the maximum disjoint paths in directed acyclic graphs (DAG) was researched which is to find the maximum disjoint paths with length k between two given vertices. A greedy algorithm named greedy path (GP) was proposed to solve the problem. GP transformed a DAG into a nettree with depth k+1 at first. Then the number of root-leaf paths for each node of the nettree was calculated to achieve the number of total paths for each vertex of the DAG. In order to obtain an optimized disjoint path, GP selected the node in the (k+1)th level of the nettree as the current node, and searched for the optimized parent in the usable parents whose number of total paths was minimal. This process was iterated, until there was no disjoint path. The space and time complexities of GP are O(wkn(p+q)) and O(kn(p+q)+n2). To evaluate the performance of GP, an algorithm which can create artificial DAG with known maximum disjoint paths was also proposed. Experimental results show that GP can get better performance than other competitive algorithms. |
| |
| Keywords: | directed acyclic graph length constraint disjoint path nettree |
|
| 点击此处可从《通信学报》浏览原始摘要信息 |
|
点击此处可从《通信学报》下载全文 |
