%0 Journal Article
%T 网树求解有向无环图中具有长度约束的最大不相交路径
%A 李艳
%A 武优西
%A 黄春萍
%A 张志颖
%A 曾珍香
%J 通信学报
%D 2015
%X ？对有向无环图中具有长度约束的最大不相交路径问题进行研究，该问题是求解图中两点间路径长度为k的最大不相交路径。为了对该问题进行求解，提出了贪婪搜索算法(gp,greedypath)，该算法先将一个有向无环图转化为一棵深度为k+1的网树，然后计算每个网树节点的树根叶子路径数，并以此计算图中每个顶点的总路径数，之后从网树的第k+1层节点出发，在当前节点的双亲节点中选择未被使用且总路径数最小的双亲，以此形成一条优化的不相交路径，最后迭代这一过程，直到不再有新的不相交路径为止。gp算法的时间和空间复杂度分别为o(wkn(p+q))和o(kn(p+q)+n2)。为了测试gp算法的近似性，又建立了一种能够生成人工数据的算法，该算法能够准确地控制有向无环图中最大不相交路径的数量。通过该算法生成了大量测试用数据，实验结果表明gp算法较其他对比性算法具有良好的近似性且实际求解时间较短，验证了该方法的有效性和可行性。
%K 有向无环图
%K 长度约束
%K 不相交路径
%K 网树
%U http://www.joconline.com.cn/CN/10.11959/j.issn.1000-436x.2015145