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

摘要：

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

关键词：有向无环图、长度约束、不相交路径、网树

所属期刊栏目：36

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61370144;国家社会科学基金资助项目12CGL112;河北省自然科学基金资助项目F2013202138,G2012202068;河北省教育厅重点基金资助项目ZH2012038;河北省科技支撑计划基金资助项目14210102DThe National Natural Science Foundation of China61370144;The National Social Science Foundation of China12CGL112;The Natural Science Foundation of Hebei ProvinceF2013202138,G2012202068;The Key Project of the Educational Commission of Hebei ProvinceZH2012038;The Science-Technology Support Plan of Hebei Province14210102D

在线出版日期：2015-10-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：38-49