李艳,武优西,黄春萍,张志颖,曾珍香. 网树求解有向无环图中具有长度约束的最大不相交路径. 通信学报. 2015, 36(8): 38-49

 

A Nettree for Maximum Disjoint Paths with Length Constraint in DAGs

ABSTRACT  In this paper, we focus on the problem of the maximum disjoint paths in directed acyclic graphs (DAGs) which is to find the maximum disjoint paths with length k between two given vertices. We propose a greedy algorithm named Greedy Path (GP) to solve the problem. GP transforms a DAG into a Nettree with depth k+1 at first. Then we calculate the number of root-leaf paths for each node of the Nettree to achieve the number of total paths for each vertex of the DAG. In order to obtain an optimized disjoint path, GP selects the node in the k+1th level of the Nettree as the current node, and searches for the optimized parent in the usable parents whose number of total paths is minimal. We iterate this process, until there is no disjoint path. The space and time complexities of GP are O(wkn(p+q)) and O(kn(p+q)+n2), respectively, where k, n, p, q, and w are length constraint, number of vertices, maximum indegree, maximum outdegree, and the solution, respectively. To evaluate the performance of GP we also propose an algorithm which can create artificial DAGs with known maximum disjoint paths. Experimental results show that GP can get better performance than other competitive algorithms.

 

网树求解有向无环图中具有长度约束的最大不相交路径

摘要  本文对有向无环图中具有长度约束的最大不相交路径问题进行研究,该问题是求解图中两点间路径长度为k的最大不相交路径. 为了对该问题进行求解,本文提出了贪婪搜索算法(Greedy Path,GP),该算法先将一个有向无环图转化为一棵深度为k+1的网树,然后计算每个网树结点的树根叶子路径数,并以此计算图中每个顶点的总路径数,之后从网树的第k+1层结点出发,在当前结点的双亲结点中选择未被使用且总路径数最小的双亲,以此形成一条优化的不相交路径,最后迭代这一过程,直到不再有新的不相交路径为止. GP算法的时间和空间复杂度分别为O(wkn(p+q))和O(kn(p+q)+n2),这里k, n, p, qw为分别为长度约束、顶点数、最大顶点入度、最大顶点出度以及问题的解. 为了测试GP算法的近似性,本文又建立了一种能够生成人工数据的算法,该算法能够准确地控制有向无环图中最大不相交路径的数量. 通过该算法生成了大量测试用数据,实验结果表明GP算法较其他对比性算法具有良好的近似性且其实际求解时间较短,验证了该方法的有效性和可行性.

 

求解算法

 

 

求解算法1:LP

 

求解算法2:RP

 

求解算法3:SP

 

求解算法4:GP

 

 

 

测试数据:测试用48组数据