中文摘要：

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

英文摘要：

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 net-tree with depth k＋l 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＋l）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 iter- ated, until there was no disjoint path. The space and time complexities of GP are O（wkn（p＋q）） and O（kn（p＋q）＋n^2）. 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.