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

• 作者: 张志颖 曾珍香 李艳 武优西 黄春萍
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 有向无环图 长度约束 不相交路径 网树
• 年，卷（期）: 2015,（8）
• 所属期刊栏目: 学术论文
• 页码范围: 38-49
• 页数: 12页
• 分类号: TP301
• 字数: 10674字
• 语种: 中文
• DOI: 10.11959/j.issn.1000-436x.2015145

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曾珍香	河北工业大学经济管理学院	72	2328	18.0	48.0
2	武优西	河北工业大学计算机科学与软件学院	28	466	10.0	21.0
3	黄春萍	河北工业大学经济管理学院	25	183	7.0	12.0
4	张志颖	河北工业大学经济管理学院	35	178	8.0	10.0
5	李艳	河北工业大学经济管理学院	19	365	6.0	19.0