文档分类：
下载前请先预览，预览内容跟原文是一样的，在线预览图片经过高度压缩，下载原文更清晰。
您的浏览器不支持进度条
淘豆网网友近日为您收集整理了关于网树求解有向无环图中具有长度约束的简单路径与最长路径问题的文档，希望对您的工作和学习有所帮助。以下是文档介绍：第卷第期年月计 算 机 学 PUTERSVol.No.Oct. 收稿日期:;最终修改稿收到日期:.本课题得到国家自然科学基金(,)、河北省自然科学基金(G)及河北省高等学校青年基金项目(SQ)资助.李艳,女,年生,博士,副教授,主要研究方向为数据挖掘与智能计算.Email:lywuc@.孙乐,男,年生,硕士研究生,主要研究方向为数据挖掘与智能计算.朱怀忠,男,年生,硕士,讲师,主要研究方向为数据挖掘与智能计算.武优西(通信作者),男,年生,博士,教授,主要研究领域为数据挖掘与智能计算.Email:wuc@.网树求解有向无环图中具有长度约束的简单路径和最长路径问题李艳) 孙乐) 朱怀忠) 武优西))(河北工业大学经济管理学院天津 ))(河北工业大学计算机科学与软件学院天津 )摘要具有长度约束的简单路径(SimplePathswithLengthConstraint,SPLC)问题是指求解图中任意两点间路径长度为犿的简单路径数,是犽path问题的一种特殊情况.treeforSPLCinDirectedAcyclicGraphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,treefortheLongestPathinDAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.关键词有向无环网络;简单路径;长度约束;最长路径;网树中图法分类号TP
犇犗犐号:./SP.J...犃犖犲狋狋狉犲犲犳狅狉犛犻犿狆犾犲犘犪狋犺狊狑犻狋犺犔犲狀犵狋犺犆狅狀狊狋狉犪犻狀狋犪狀犱狋犺犲犔狅狀犵犲狊狋犘犪狋犺犻狀犇犻狉犲犮狋犲犱犃犮狔犮犾犻犮犌狉犪狆犺狊LIYan) SUNLe) ZHUHuaiZhong) WUYouXi))(犛犮犺狅狅犾狅犳犈犮狅狀狅犿犻犮狊犪狀犱犕犪狀犪犵犲犿犲狀狋,犎犲犫犲犻犝狀犻狏犲狉狊犻狋狔狅犳犜犲犮犺狀狅犾狅犵狔,犜犻犪狀犼犻狀 ))(犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犛狅犳狋狑犪狉犲,犎犲犫犲犻犝狀犻狏犲狉狊犻狋狔狅犳犜犲犮犺狀狅犾狅犵狔,犜犻犪狀犼犻狀 )犃犫狊狋狉犪犮狋 TheproblemofSimplePathswithLengthConstraint(SPLC)istocalculatethenumberofsimplepathsbetweentwoverticesunderthelengthconstraint犿inthegraph.Itisaspecialcaseofthe犽pathproblem.InordertosolvetheprobleminDirectedAcyclicGraphs(DAGs),treeforSimplePathswithLengthConstraintinDAGs(NSPLCDAG)treewhichmayhavemorethanonerootandoneparent.tree.treeisusedtosolvetheproblem.BasedonNSPLCDAG,treefortheLongestPathinDAGs(NLPDAG)isconstructedwhichcanfindallthelongestpaths.plexity.TheexperimentalresultsverifythecorrectnessandeffectivenessofthetwoalgorithmsofNSPLCDAGandtheimprovedNLPDAG.犓犲狔狑狅狉犱狊 dtree 引言图是一种比线性表和树更为复杂的数据结构.在线性表中,结点间为单前驱单后继的线性关系;在树结构中,结点间为单前驱多后继的非线性关系;而在图结构中,结点间则为多前驱多后继的非线性关系.图中任意两个结点之间都可能相关,因此图已经被广泛应用于诸如语言学、逻辑学、物理、化学、电气工程和计算机科学等学科中.在图论中,最长路径(thelongestpath)问题[]是指在给定的图中找出一条最长的简单路径.在无向图中求解最长路径问题是著名的NP难问题,现有的研究主要基于近似算法[]、参数化算法[].另外一类研究是针对特殊图进行求解,并给出多项式时间复杂度的求解算法,如Mertzios和Corneil①采用一种深度优先搜索策略对伴相似图(parabilitygraphs)中最长路径问题进行了求解;Uehara和Valiente[]在二部置换图(bipartitepermutationgraphs)中对最长路径问题建立了线性时间复杂度的求解算法,其求解的二部置换图既是一个置换图也是一个二部图;Ioannidou等人[]在区间图(intervalgraphs)中运用动态规划思想,对最长路径问题给出了时间复杂度为犗(狀)的求解算法;Edmonds和Chakraborty[]在有向无环图(DirectedAcyclicGraphs,DAGs)所有边的长度非负的情况下,对最长路径的方差和期望的边界进行了计算.犽path问题是指在给定的图中找出一条长度为犽的简单路径,是最长路径问题的一种特殊情况.Chen等人[]基于分治思想对一般图中的犽path问题进行了研究,提高了该问题的计算速度.犽path问题在诸多领域具有非常重要的应用.Scott等人[]在生物学约束下,采用彩色编码技术,在酵母蛋白质相互作用网络中查找蛋白质传导路径,其求解方法是将蛋白质作为结点,蛋白质之间的相互作用关系作为边,以此构成的生物蛋白质作用网络,权值最大的犽path代表信号传导路径;Desaulniers等人[]利用推广犽path的不均衡性(generalized犽pathinequalities)对犽个车辆的路由选择问题进行了研究.与犽path问题相近的是求解图中指定两点间路径长度为犽的最大不相交路径问题,Itai等人[]plete问题的证明.求解两点间路径长度为犽的所有简单路径数是具有长度约束的简单路径(SimplePathswithLengthConstraint,SPLC)问题.本文在有向无环图中求解该问题形成了SPLCinDAGs.SPLCinDAGs可在具有周期间隙约束的序列模式挖掘和具有间隙约束的模式匹配等方面得到应用.Zhang等人[]提出了具有周期间隙约束的序列模式挖掘问题,并将该模式挖掘方法应用在DNA序列挖掘中;Tanbeer等人[]将具有周期间隙约束的序列模式挖掘方法应用于购买模式的挖掘.尽管Zhang等人采用了空间变换的方法进行序列模式挖掘,但是此方法的基础是具有间隙约束的模式匹配问题[].文献[]研究了具有间隙约束和一次性条件的模式匹配问题的求解方法,给出了将具有间隙约束的模式匹配问题转换为有向无环图的算法,这使得具有间隙约束的模式匹配问题与SPLCinDAGs问题建立了实质性联系.为了解决SPLCinDAGs问题,本文利用网树数据结构(tree)[,]进行求解.网树是一种多前驱多后继的非线性数据结构,是对树结构的拓展.网树不仅具有树结构的所有概念,如根结点、叶子结点、双亲、孩子、路径、层等,而且除根结点外,网树中任意结点可以有多个双亲结点.treeforSimplePathswithLengthConstraintinDAGs,NSPLCDAG),NSPLCDAG算法将该问题转化为一棵网树,然后利用网树的树根路径数这一特殊性质对该问题进行求解.NSPLCDAG算法的时间复杂度和空间复杂度分别为犗(犿×狀×狋)和犗(狀+|犈|),这里犿,狋,狀和|犈|分别表示两点间的路径长度约束、顶点最大出度以及顶点数和边数.对NSPLCDAG算法做进一步改造,treefortheLongestPathinDAGs,NLPDAG).对NLPDAG算法做进一步改进形成改进的NLPDAG算法,该算法使得网树退化为一棵树,并使算法的时间复杂度和空间复杂度分别为犗(|犈|)和犗(狀+|犈|),这里狀和|犈|分别表示图的顶点数和边数.本文第节对SPLCinDAGs问题进行定义;第节介绍网树的概念和性质;第节提出NSPLCDAG算法,同时分析该算法的时间复杂度和空间复杂度,并通过示例来说明算法的工作原理;第节提出NLPDAG算法和改进的NLPDAG算法并给出求解示例;第节给出实验结果及分析;第节得期李艳等:网树求解有向无环图中具有长度约束的简单路径和最长路径问题① MertziosG,CorneilD.parabilitygraphs.Technicalreportavailableat/abs/.出本文结论. 问题的定义定义. 图犌=(犞,犈),其中犞称为顶点集,犈称为边集.从顶点狏到顶点狏′的路径是一个有序顶点序列犛={狏=狏,狏,…,狏犿=狏′},其中顶点序列应满足〈狏犼-,狏犼〉∈犈(犼犿).路径长度是路径中有向边的数目.如果序列犛中任何两个顶点不重复出现,则称此路径为简单路径.定义. 具有长度约束的简单路径SPLC问题是指给定图犌=(犞,犈)中任意两点狌,狏∈犞和正整数犿,求解从狌到狏路径长度为犿的简单路径数.SPLCinDAGs是指在给定的有向无环图中求解SPLC问题.定义. 邻接矩阵是表示顶点之间相邻关系的矩阵,图犌采用邻接矩阵存储.二维数组元素犵[犻][犼]=(犻,犼狀,狀=|犞|)表示顶点犻到顶点犼之间存在一条有向边,否则表示顶点犻到顶点犼之间无边.顶点狏犻的出度(用犗犇(狏犻)表示)是第犻行的元素之和,计算公式如下:犗犇(狏犻)=∑狀-犼=犵[犻][犼] ()
顶点狏犻的入度(用犐犇(狏犻)表示)是第犻列的元素之和,计算公式如下:犐犇(狏犻)=∑狀-犼=犵[犼][犻] ()
例. 如图所示的有向无环图,其顶点个数狀=,求从顶点至顶点路径长度约束犿=的简单路径数.图 一个有向无环图从图可以看出,顶点至顶点路径长度约束为的路径数为,即{,,,,}、{,,,,}、{,,,,}、{,,,,}、{,,,,}、{,,,,}、{,,,,}、{,,,,}、{,,,,}和{,,,,}.SPLCinDAGs问题的求解难度在于,顶点狌和狏之间的路径数呈现指数形式,因此不能采用穷举法列出所有可能的路径并判定路径长度是否满足约束条件来进行求解,本文采用网树这一数据结构进行求解. 网树的定义及性质本节给出了网树的定义和性质.定义. 网树数据结构是结点的集合,这个集合可以为空集,或可由若干不同的根结点狉,狉,…,狉犿和或多个非空子网树犜,犜,…,犜狀构成,这些子网树的树根至少存在一条边与网树的根结点狉犻相连接,这里犿,狀且犻狀.图给出了一棵一般意义的网树.图 一棵一般意义的网树网树具有如下个性质[,]:()网树是树结构的拓展,它具有很多与树相似的概念,如根结点、叶子结点、层、双亲、孩子等;()一棵网树可以有狀个根结点,其中狀;()除了根结点之外,网树的其它结点可以有多个双亲结点;()从一个结点到达网树的一个根结点的路径不唯一;()同一结点可以在网树的不同层上多次出现.定义. 由于同一结点可以在网树的不同层上多次出现,这里用狀犻犼来表示第犼层的结点犻.定义.从结点狀犻犼到达根结点的路径数称为树根路径数(thenumberofrootpaths),用犖狉(狀犻犼)来表示.树根路径数具有如下个性质:()根结点狀犻的树根路径数为,即犖狉(狀犻)=;()结点狀犻犼的树根路径数是其所有双亲结点的树根路径数之和,即犖狉(狀犻犼)=∑犺犽=犖狉(狀犻犽犼-) () 计 算 机 学 报 年这里狀犻犽犼-是结点狀犻犼的第犽个双亲,犺是结点狀犻犼的双亲数.图给出了一棵网树.在这棵网树中一些结点在不同层中多次出现.如结点既出现在第层又出现在第层,本文采用狀和狀来分别描述第层和第层的结点.结点狀和狀是网树的两个根结点;狀,狀和狀是网树的个叶子结点.结点狀有两个双亲结点,分别是狀和狀.结点狀的树根路径数犖狉(狀)=是因为结点狀有两个双亲结点狀和狀且犖狉(狀)=犖狉(狀)=;同理可知,犖狉(狀)=;犖狉(狀)=犖狉(狀)+犖狉(狀)=.网树的另一特征是从一个结点到达网树的一个根结点的路径可能不唯一.如叶子结点狀访问根结点狀有两条不同的路径,分别为{狀,狀,狀}和{狀,狀,狀}.图 一棵网树 犖犛犘犔犆犇犃犌算法描述及复杂度分析 算法描述采用NSPLCDAG算法求解图犌中狌,狏两点间长度为犿的简单路径数问题的基本思想为:将有向无环图犌转化为一棵犿+层网树,然后利用网树的树根路径数这一性质进行求解.在转化过程中,图犌的顶点编号犻即为网树结点名称犻,网树采用从树根层至犿+层逐层创建的方式.将图犌转化为一棵网树及求解的流程如下:首先,将顶点狌作为网树的根结点狀狌,该结点为网树的第层且其树根路径数犖狉(狀狌)=.其次,依据网树第犼-层结点创建网树第犼层结点.具体方法是:取网树的第犼-层结点狀犻犼-,如果犵[犻][犾]=(犾狀)且在第犼层未创建结点狀犾犼,则在网树的第犼层创建结点狀犾犼并在结点狀犻犼-和结点狀犾犼间建立父子关系,并使得狀犾犼的树根路径数与结点狀犻犼-的树根路径数一致;若犵[犻][犾]=(犾狀)且在第犼层已创建结点狀犾犼,则在结点狀犾犼和结点狀犻犼-间建立父子关系,并使狀犾犼的树根路径数累加上结点狀犻犼-的树根路径数.最后,该网树第犿层中与顶点狏相连接的结点的树根路径数之和即为问题的解.NSPLCDAG算法的描述如下:算法. NSPLCDAG算法.输入:有向无环图的顶点数狀,有向无环图的邻接矩阵,顶点狌,狏和两点间的路径长度约束犿输出:路径数狆犪狋犺狀狌犿.读取存储图的二维数组犵[犻][犼](犻,犼狀);.依据顶点狌初始化网树的根结点;.FOR(犼=;犼&=犿;犼++).FOR(犪=;犪&网树第犼-层结点数;犪++).犻=网树第犼-层第犪+个结点的名称;.FOR(犫=;犫&犗犇(犞犻);犫++).犾=顶点犻的第犫+个弧的弧尾顶点;.IF(狀犾犼未被创建). 创建狀犾犼结点,犖狉(狀犾犼)=犖狉(狀犻犼-),第犼层结点数自增;.ELSE. 犖狉(狀犾犼)+=犖狉(狀犻犼-);.ENDIF.ENDFOR.ENDFOR.ENDFOR.FOR(犱=;犱&网树第犿层结点数;犱++).IF(犵[犱][狏]==)狆犪狋犺狀狌犿+=犖狉(狀犱犿);.ENDFOR.RETURN狆犪狋犺狀狌犿; 犖犛犘犔犆犇犃犌算法复杂度分析NSPLCDAG算法的空间复杂度是犗(犿×狀×狋+狀)且可进一步优化为犗(狀+|犈|),这里犿,狋,狀和|犈|分别表示两点间的路径长度约束、顶点最大出度、顶点数和边数.NSPLCDAG算法占用的空间是由网树和图犌的邻接矩阵两部分组成的.第部分网树的开销为犗(犿×狀×狋),这是因为网树的深度是犿,网树中每层最多有狀个结点,且每个结点最多有狋个孩子.对NSPLCDAG算法可以做进一步改进,使网树的空间开销为犗(狀),其改进方法如下:由于NSPLCDAG算法仅依据网树中上一层结点信息来创建下一层结点,因此在存储网树的过程中仅保留一层网树结点即可.此外,在解决SPLCinDAGs问题时,可以不必存储网树的父子关系,而仅计算当前结点的树根路径数,这样网树的开销可以缩减为犗(狀).第部分存储图犌邻接矩阵的开销为犗(狀),也可以将图犌存储为三元组形式,其开销为犗(|犈|),因此NSPLCDAG算法优化后的空间复杂度为犗(狀+|犈|).NSPLCDAG算法的时间复杂度为犗(犿×狀×狋).期李艳等:网树求解有向无环图中具有长度约束的简单路径和最长路径问题这是因为算法的第行循环次数为犗(犿),第行的最坏循环次数为犗(狀),第行的最坏循环次数为犗(狋),算法的第,,和行均在犗()时间内即可完成,算法的第~行的最坏时间复杂度为犗(狀).综上,NSPLCDAG算法的时间复杂度为犗(犿×狀×狋). 犖犛犘犔犆犇犃犌算法运行实例以例为例来说明NSPLCDAG算法的工作原理.根据NSPLCDAG算法的思想,将例中的有向无环图转化为一棵层网树,所建立网树如图所示.在图中箭头方向代表网树的创建方向,白色圆圈内数字代表网树结点名称,灰色圆圈内数字代表该结点的树根路径数.网树的创建和问题的求解过程如下:图 求解图中从顶点至顶点路径长度约束为的网树将顶点作为网树的根结点狀,树根路径数犖狉(狀)=.将满足犵[][犾]=(犾狀)条件的所有顶点创建为网树第层结点狀犾,因此网树的第层结点分别是狀,狀,狀和狀,且这些结点的树根路径数均为.之后,对结点狀创建孩子结点,创建依据为犵[][犾]=(犾狀),这样可以创建第层的结点狀,狀,狀和狀,且这些结点的树根路径数均为.依据犵[][犾]=(犾狀)对结点狀创建孩子结点,易知结点狀有两个孩子结点,分别为狀和狀,此时狀的树根路径数为.以此类推可以建立网树第层和第层全部结点.由于路径长度约束为,因此根据第层结点与顶点的连接情况,即犵[犾][]=(犾狀)来建立父子关系,并求得问题的解为+++=. 网树求解最长路径问题求解最长路径问题是图论中经典问题之一,其是指在给定的图犌中找到路径长度最长的一条简单路径.将NSPLCDAG算法中根据顶点狌创建网树的根结点变为依据图犌中所有入度为的顶点来创建网树的根结点,同时将创建网树深度为指定的长度约束变为网树不再有新的结点产生,即可对最长路径问题进行求解,treefortheLongestPathinDAGs,NLPDAG).NLPDAG算法从网树最深的一个叶子结点回溯至网树根结点以产生一条最长路径,故NLPDAG算法需要对NSPLCDAG算法的第~行和第~行进行修改,其余各行均保持不变,具体修改如下:算法. NLPDAG算法.输入:有向无环图的邻接矩阵输出:最长路径狆犪狋犺NLPDAG算法的第~行:.依据图犌中所有入度为的顶点来创建网树的根结点;.FOR(犼=;第犼-层结点个数&;犼++)NLPDAG算法的第~行:.犓=犼-;.狆犪狋犺[犓]=第犼-层的第个结点名;.由狆犪狋犺[犓]回溯至根结点形成最长路径狆犪狋犺;.RETURN狆犪狋犺;
由于NLPDAG算法必须由最深层叶子结点回溯至网树根结点,因此NLPDAG算法不能在求解过程中删除任何网树结点且必须存储网树结点的父子关系,由NSPLCDAG算法的空间复杂度和时间复杂度分析可知,NLPDAG算法的时间复杂度和空间复杂度分别为犗(犓×狀×狋)和犗(犓×狀×狋+|犈|),这里犓,狋,狀和|犈|分别表示图中最长路径长度、顶点最大出度、顶点数和边数.由于NLPDAG算法是由NSPLCDAG算法改进而来,因此NLPDAG算法不但可以找到一条最长路径,同时根据所建立的网树可以描述所有最长路径.以图为例来说明最长路径是如何获得的.由于图中入度为的顶点只有顶点,因此以顶点为网树的根结点来创建网树,网树的前层与图一致,依据第层结点创建第层结点狀,狀,狀和狀,依据第层结点创建第层结点狀和狀,依据第层结点仅能够创建第层结点狀,由于顶点的出度为,因此第层结点个数为,循环结束,所创建的网树如图所示,故图的最长路径长度为,且最长路径的最终顶点为.结点狀的第个双亲结点为狀;以此类推,回溯至第层,就可以得到 计 算 机 学 报 年一条最长路径:{,,,,,,}.从图可以看出,从顶点至顶点最长的路径只有一条,但在实际问题中,通常最长路径并不唯一.图 求解图中最长路径的网树如果仅需在有向无环图中找到一条最长路径,而无需计算最长路径的路径数,则可以对NLPDAG算法进行改进.NLPDAG算法在有向无环图中求解最长路径时,对很多冗余信息进行了计算,这是因为NLPDAG算法将顶点犻所指向的所有顶点均作为网树中结点犻的孩子结点.在求解最长路径时,应仅选择满足删除有向边〈犻,犼〉后,顶点犼的入度为的点作为网树中顶点犻的孩子结点,从而形成改进的NLPDAG算法.由于此时不存在一个结点具有多个双亲的情况,因此网树也就退化为一棵树或一个森林(我们可以将树看成是网树的特例).具体算法如下:算法. 改进的NLPDAG算法.输入:有向无环图的邻接矩阵输出:最长路径狆犪狋犺.读取存储图的二维数组犵[犻][犼](犻,犼狀);.依据图犌中入度为的所有顶点来创建网树的根结点;.依次从已创建的网树中取一个未处理的结点犻,所有有向边〈犻,犼〉的顶点犼的入度自减;.IF(犻犱(狏犼)==)为结点犻创建孩子结点犼;.重复步和直至不再有新的结点产生;.最长路径长度=网树的最大深度-,由该叶子结点回溯至根结点以获得最长路径狆犪狋犺;.RETURN狆犪狋犺;由于改进的NLPDAG算法对有向无环图中所有有向边仅处理一次,而每次处理均在犗()内完成,因此改进的NLPDAG算法时间复杂度为犗(|犈|).易知,有向无环图若以三元组形式存储,改进的NLPDAG算法空间复杂度为犗(狀+|犈|).按照改进的NLPDAG算法对图进行求解,生成的网树如图所示.图 改进NLPDAG算法求解最长路径的网树 实验结果及分析 实验结果文献[]采用了链式队列数据结构对有向无环图中从狌到狏两点间全部简单路径问题进行了研究,并以产品族零部件关系网络为例,对实际有向无环网络中的应用加以说明,该算法的空间复杂度和时间复杂度均为犗(狀).由于该算法是用来求解两点间全部简单路径,因此亦可用于求解本文的SPLCinDAGs,该算法的时间复杂度与空间复杂度均保持不变.而本文NSPLCDAG算法亦可用于求解文献[]的问题,求解的方法是以最长路径犓为SPLCinDAGs的长度约束,所创建的网树则可以表示文献[]中问题的解,显然NSPLCDAG算法的时间复杂度和空间复杂度也没有发生任何变化.图的网树可描述文献[]中问题在图上的解.因此本文的NSPLCDAG算法在求解相同问题时,算法的时间复杂度和空间复杂度均优于文献[]的算法.两种算法的时间复杂度和空间复杂度对比如表所示.表 犛犘犔犆犻狀犇犃犌狊的算法复杂度对比算法时间复杂度空间复杂度文献[]算法犗(狀) 犗(狀)NSPLCDAG算法犗(犿×狀×狋) 犗(狀+|犈|)期李艳等:网树求解有向无环图中具有长度约束的简单路径和最长路径问题 对最长路径问题本文给出了NLPDAG算法和改进的NLPDAG算法,这两种算法的时间复杂度和空间复杂度对比如表所示.表 最长路径问题算法复杂度对比算法时间复杂度空间复杂度NLPDAG算法犗(犓×狀×狋) 犗(犓×狀×狋+|犈|)改进的NLPDAG算法犗(|犈|) 犗(狀+|犈|)为了获得较大规模的有向无环图,我们采用文献[]中的算法,将具有间隙约束的模式匹配问题转化为有向无环图.本文采用了文献[]中使用的前种模式串犘,犘,犘和犘来分别生成DAG至DAG,并且忽略了文献[]中的全局约束.序列串采用美国国家生物计算信息中心公布的猪流感HN病毒的一种候选DNA序列(A/Managua/./(HN))①中的第一个片段的前个字符.在增加源点和汇点后,使得DAG到DAG的大小均为.为了避免序列串对问题求解的影响,DAG到DAG则采用文献[]中的犘模式,而序列串则采用前述DNA序列的第个~第个序列片段的全部字符,在增加源点和汇点后,使得DAG,DAG,DAG和DAG的大小分别为,,和.表给出了生成本文个有向无环图的模式串.表 生成有向无环图的模式串序号模式串犘犪[,]狋[,]犪[,]狋[,]犪[,]狋[,]犪[,]狋[,]犪[,]狋[,]犪犘犵[,]狋[,]犪[,]犵[,]狋[,]犪[,]犵[,]狋[,]犪犘犵[,]狋[,]犪[,]犵[,]狋[,]犪[,]犵[,]狋[,]犪[,]犵[,]狋犘犵[,]狋[,]犪[,]犵[,]狋[,]犪[,]犵[,]狋[,]犪[,]犵[,]狋实验运行的软硬件环境为:IntelCore DuoCPUT处理器、主频.GHz、内存GB、WindowsXP操作系统.由于算法的运行速度较快,运行时间较短,为此本文全部实验均采用运行次获得总的运行时间,然后单次运行时间为总时间除以的方法以便较为准确地获得算法在各个实例上的运行时间.为了测试有向无环图的大小对于算法运行时间的影响,对DAG,DAG,DAG和DAG分别在、、和个结点的子图以及原图中路径长度约束分别为,,和的条件下进行了测试,并与文献[]算法的运行时间进行了对比,结果见表.表 不同大小有向无环图的算法运行时间对比图名称路径长度约束犿顶点数问题解/个文献[]算法运行时间/msNSPLCDAG算法运行时间/msDAG
. .为了对比算法在不同路径长度约束下解的大小和运行时间的长短,对DAG和DAG在长度约束分别为,,,,和以及DAG和DAG在长度约束分别为,,,,和的情况下进行了测试,结果见表.表 不同长度约束下算法运行时间图名称路径长度约束犿问题解/个 NSPLCDAG算法运行时间/msDAG
表给出了采用NLPDAG算法和改进的NLPDAG算法求得的DAG至DAG的最长路径长度、最长路径及求解时间. 计 算 机 学 报 年①A/Managua/./(HN)可在.gov/genomes/FLU/SwineFlu.html下载表 最长路径及求解时间图名称 NLPDAG算法所求的最长路径长度及最长路径改进的NLPDAG算法所求的最长路径长度及最长路径NLPDAG算法运行时间/ms改进的NLPDAG算法运行时间/msDAG {,,,,,,,,,,,,,,,,,,,,}①{,,,,,,,,,,,,,,,,,,,,} .DAG{,,,,,,,,,,,…,,,,,,,,}②{,,,,,,,,,,,…,,,,,,,,,} .DAG {,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}③{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,} .DAG {,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,} .DAG -④{,,,,,,,,,,,…,,,,,,,}- .DAG -{,,,,,,,,,,,…,,,,,,}- .DAG -{,,,,,,,,,,,…,,,,,,,}- .DAG -{,,,,,,,,,,,,,,,…,,,,,,,}- .①“{}”前面的数字代表最长路径长度;“{}”内的数字串代表求解出的最长路径.②由于DAG以及DAG~DAG的最长路径长度较大,限于篇幅,我们仅给出了最长路径的开始和结束的部分值,中间的绝大部分采用“…”进行了省略.③由于DAG和DAG的最长路径的解仅在附近至附近有所差异,其他部分较为相似,因此本文对这两个实例给出了完整的最长路径.④由于DAG~DAG图相对较大,NLPDAG算法因消耗空间过大,在这些实例上未能给出运行结果. 实验结果分析()本文所提出的NSPLCDAG算法的效率要大大优于文献[]所提出的算法.通过表的全部个实例可以看出,文献[]算法的运行时间均显著长于本文算法.如在DAG中,当路径长度约束犿为,顶点数为时,文献[]算法的运行时间为.ms,而NSPLCDAG算法的运行时间为.ms.这些实验充分地说明了本文所提出的NSPLCDAG算法的效率要大大优于文献[]算法.()文献[]算法的求解时间与顶点数的大小和解的大小相关,特别是与解的大小相关,解越大,求解时间增加越显著.在表的DAG中,当路径长度约束犿为,顶点数分别为、和时,问题解的大小均为,算法运行时间分别为.ms、.ms和.ms,这说明了文献[]算法的运行时间与顶点数的大小相关.而在DAG,DAG和DAG中,当解显著增加时,问题的求解时间也显著增大.如在DAG中,当路径长度约束犿为,顶点数分别为、和时,问题解的大小分别为、和,其运行时间分别为.ms、.ms和.ms,这些实例充分地说明了当解显著增加时,文献[]算法的求解时间也显著增大.产生上述现象的原因是,文献[]的算法是从汇点出发,对每条简单路径进行逐一回溯,通过枚举所有可能的解来获得所有的简单路径,因而文献[]算法的求解时间与解的大小相关.()NSPLCDAG算法的求解时间与图的大小和长度约束大小相关,更为重要的是当问题的解显著增大时,求解时间并不显著增加.通过表可以看出,NSPLCDAG算法的求解时间与图的尺寸未呈现绝对线性变化,但是当图的尺寸增大时,运行时间也相应增加,因此NSPLCDAG期李艳等:网树求解有向无环图中具有长度约束的简单路径和最长路径问题算法的求解时间与图的大小呈正相关.表也呈现出同样的特点,虽然运行时间与路径长度犿未呈现绝对线性变化,但是随着路径长度约束犿的增大,运行时间也相应增加,因此NSPLCDAG算法的求解时间与长度约束呈正相关.此外,通过表和还可以看出,当问题的解快速增大时,问题的求解时间并未显著增加,这一特点在表中体现尤为明显.如在DAG中,当路径长度约束由变为时,问题的解增大了近×倍,然而问题的求解时间增加不到一倍,这充分地说明了当问题的解显著增大时,求解时间并不显著增加.当路径长度约束为时,DAG解的大小小于DAG解的大小,但是在DAG中的运行时间却略长于DAG,这说明问题的求解速度与解的大小无关.NSPLCDAG算法是一个高效求解算法是因为其采用网树结构,该结构将同一层结点名称相同的结点合并为一个网树结点,有效地避免了组合爆炸现象的发生,大大地提高了问题的求解速度.()表中部分实例的解为的分析与说明.在表的DAG中,当长度约束为,和时,问题的解均为,造成这一现象的原因有两种:①通过表可以看出,DAG的最长路径长度为,因此长度约束在大于最大路径长度时,问题的解为,所以DAG中长度约束为时,问题的解为;②本文的全部有向无环图均采用文献[]的算法转化而来,对于DAG来说,指向汇点的所有有向边均由模式串犘的最后一个字符‘a’来生成.模式串犘中‘a’与‘t’交替出现,因此当路径长度约束为偶数时,问题的解均不为;而为奇数时,如为和时,问题的解均为.在DAG,DAG和DAG中存在同样的现象,由于模式串犘,犘和犘中‘a’,‘t’和‘g’三者交替出现,由模式串犘可知,DAG在长度约束为的倍数+时,结果均不为,而在其它情况下均为.由模式串犘和犘可知,DAG和DAG在长度约束为的倍数时,结果均不为,而其他情况均为.表的DAG,DAG和DAG在不同长度约束下的求解结果验证了当路径长度约束小于最长路径长度时,两点间的简单路径数也可能为.()改进的NLPDAG算法适用于求解大规模有向无环图的最长路径问题.通过表可以看出,在求解DAG至DAG的个大小为的有向无环图的最长路径时,最长路径长度达到,由于NLPDAG算法占用空间较大,因此在求解这个实例时,运行时间接近s;而改进的NLPDAG算法运行时间小于ms.而在DAG至DAG的大小达到数量级且最长路径长度达到数量级时,NLPDAG算法因占用空间过大,未能给出运行结果;而改进的NLPDAG算法的求解时间小于ms.这充分地说明了改进的NLPDAG算法具有较快的求解速度,适用于求解大规模有向无环图的最长路径问题.()有向无环图中最长路径不唯一.在表的DAG中路径长度约束为(即为该图最长路径长度)时,SPLCinDAGs问题的解为,这说明在DAG中,从顶点到顶点共有条不同的最长简单路径.此外,表中NLPDAG算法和改进的NLPDAG算法在DAG至DAG中给出相同的最长路径长度,相互验证了算法的正确性,并在DAG,DAG和DAG中给出了不同的最长路径,充分地说明了有向无环图中最长路径不唯一.()对其它现象的分析与说明.对于表的DAG,当其尺寸发生变化时,问题的解可能并不发生变化,即DAG在和个结点的子图以及原图上问题的解均为,这说明在DAG中从顶点至顶点在路径长度约束为的情况下,没有经过顶点~的路径.由于NSPLCDAG算法采用了动态分配内存的方式,因此运行时间会有一定的扰动,故算法在表的DAG中顶点数为和时,取得了相同的运行时间.另外在表的DAG中,长度约束为和时,运行时间都为.在表的DAG中,在长度约束为时,算法运行时间比长度约束为,和的运行时间都长;在表的DAG中,在长度约束为时,算法运行时间比长度约束为和的运行时间都长,这说明算法在某些实例上运行时间会有一定的扰动. 结论本文研究了求解SPLCinDAGs问题的NSPLCDAG算法,该算法将此问题转化为一棵网树,并利用网树的树根路径数性质对该问题进行求解.网树的多前驱多后继性有效地避免了组合爆炸现象的发生,大大地提高了问题的求解速度,使得NSPLCDAG算法的时间复杂度和空间复杂度分别为犗(犿×狀×狋)和犗(狀+|犈|),这里犿,狋,狀和|犈|分别表示两点间的路径长度约束、顶点最大出度以及顶点数和边数.本文通过对NSPLCDAG算法进行适当修改,形成了有向无环图中求解最长路径问题 计 算 机 学 报 年的NLPDAG算法,在对NLPDAG算法进行改进后,形成了改进的NLPDAG算法.改进的NLPDAG算法的时间复杂度和空间复杂度分别为犗(|犈|)和犗(狀+|犈|),这里狀和|犈|分别表示图的顶点数和边数.对比性实验验证了NSPLCDAG算法和改进的NLPDAG算法的正确性和有效性.致谢匿名审稿人对本文提出了宝贵修改意见,在此表示感谢!参考文献[]WangJianXin,YangZhiBiao,ChenJianEr.Algorithmsforlongestpath:puterScience,,():,(inChinese)(王建新,杨志彪,陈建二.最长路径问题研究进展.计算机科学,,():,)[]KimSK.Optimalalgorithmsforfindingthelongestpathwithlengthandsumconstraintsinatree.IEICETransactionsonInformationandSystems,,ED(): []WilliamsR.Findingpathsoflength犽in犗(犽)rmationProcessingLetters,,():[]UeharaR,rmationProcessingLetters,,():[]IoannidouK,MertziosG,NikolopoulosS.Thelongestpathproblemispolynomialonintervalgraphs.puterScience,,():[]EdmondsJ,ChakrabortyS.BoundingvarianceandexpectationoflongestpathlengthsinDAGs//ProceedingsofthestAnnualACMSIAMSymposiumonDiscreteAlgorithms.Philadelphia,USA,:[]ChenJ,LuS,SzeS,ZhangF.Improvedalgorithmsforpath,matching,andpackingproblems//ProceedingsofthethAnnualACMSIAMSymposiumonDiscreteAlgorithms.Philadelphia,USA,:[]ScottJ,IdekerT,KarpRM,SharanR.works.putationalBiology,,():[]DesaulniersG,LessardF,HadjarA.Tabusearch,partialelementarity,andgeneralized犽pathinequalitiesforthevehicleroutingproblemwithtimewindows.TransportationScience,,():[]ItaiA,PerlY,ShiloachY.works,,():[]ZhangM,KaoB,CheungD,YipK.Miningperiodicpatternswithgaprequirementfromsequences.ACMTransactionsonKnowledgeDiscoveryfromData,,():[]TanbeerSK,AhmedCF,JeongB,LeeY.Miningregularpatternsintransactionaldatabases.IEICETransactionsonInformationandSystems,,ED():[]WuY,WuX,MinF,LiY.Anettreeforpatternmatchingwithflexiblewildcardconstraints//ProceedingsoftheIEEEInternationalConferenceonInformationReuseandIntegration(IRI).LasVegas,USA,:[]HeD,ArslanAN,HeY,WuX.Iterativerefinementofrepeatsequencespecificationusingconstrainedpatternmatching//ProceedingsoftheIEEEthInternationalSymposiumonBioinformatics&Bioengineering(BIBE).Cambridge,Massachusetts,USA,:[]WuYouXi,WuXinDong,JiangHe,MinFan.AheuristicalgorithmforMPMGOOC.puters,,():(inChinese)(武优西,吴信东,江贺,闵帆.一种求解MPMGOOC问题的启发式算法.计算机学报,,():)[]LiuFuYun,QiGuoNing,CheHongAn.workanditsapplication.SystemsEngineeringTheory&Practice,,():,(inChinese)(刘夫云,祁国宁,车宏安.复杂网络中简单路径搜索算法及其应用研究.系统工程理论与实践,,():,)犔犐犢犪狀,bornin,Ph.D.,associateprofessor.putation.犛犝犖犔犲,bornin,M.S.candidate.putation.犣犎犝犎狌犪犻犣犺狅狀犵,bornin,M.S.,assistantprofessor.putation.犠犝犢狅狌犡犻,bornin,Ph.D.,professor.putation.犅犪犮犽犵狉狅狌狀犱 Theproblemsofsimplepathswithlengthconstraintandthelongestpathareclassicalproblemsingraphtheory.Theproblemofsimplepathswithlengthconstraintindirectedacyclicgraphshasveryimportantapplicationsincesomepatternmatchingproblemswithgapconstraintscantransformintothisproblem.Inthispaper,treewhichwasputforwardforsolvingpatternmatchingproblemswithgapconstraints.Theexperimentalresultsverifythecorrectnessandeffectivenessofthetwoalgorithms.ThisresearchissupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.,No.,theNaturalScienceFoundationofHebeiProvinceunderGrantNo.G,andtheYoungScholarFoundationofCollegesandUniversitiesofHebeiProvinceundergrantNo.SQ.期李艳等:网树求解有向无环图中具有长度约束的简单路径和最长路径问题播放器加载中，请稍候...
该用户其他文档
下载所得到的文件列表网树求解有向无环图中具有长度约束的简单路径与最长路径问题.pdf
文档介绍：
第卷第期年月计 算 机 学 PUTERSVol.No.Oct. 收稿日期:;最终修改稿收到日期:.本课题得到国家自然科学基金(,)、河北省自然科学基金(G)及河北省高等学校青年基金项目(SQ)资助.李艳,女,年生,博士,副教授,主要研究方向为数据挖掘与智能计算.Email:lywuc@.孙乐,男,年生,硕士研究生,主要研究方向为数据挖掘与智能计算.朱怀忠,男,年...
内容来自淘豆网转载请标明出处.}