1、第?卷 第? 期 计 算 机 学 报 Vol. ? No. ?20?年？月 CHINESE JOURNAL OF COMPUTERS ?. 20?收稿日期：年-月- 日*投稿时不填写此项*；最终修改稿收到日期：年-月-日 *投稿时不填写此项*.本课题得到国家自然科学基金(61072100)；国家自然科学基金(51107029) ；河北省自然科学基金(G2010000165) 资助. 李艳，女，1975年生，博士，E-mail: ，副教授，主要研究领域为数据挖掘与智能计算. 孙乐，男，1986年生，研究生，E-mail: ，主要研究领域为数据挖掘与智能计算. 朱怀忠，男，1978年生，硕士，E-
2、mail:，讲师，主要研究领域为数据挖掘与智能计算. 武优西（通信作者），男，1974年生，博士，E-mail: ，教授，主要研究领域为数据挖掘与智能计算. 通讯作者：武优西 电话：13116179687网树求解有向无环图中具有长度约束的简单路径和最长路径问题李 艳 1), 孙乐 2), 朱 怀 忠 2) , 武 优 西 2) 1)( 河北工业大学 经济管理学院, 天津 中国 300401)2)(河北工业大学 计算机科学与软件学院, 天津 中国 300401)摘 要 具有长度约束的简单路径问题(Simple Paths with Length Constraint, SPLC)是指求解图 G
3、中任意两点间路径长度为m 的简单路径数，是 k-path 问题的一种特殊情况。 本文基于网树数据结构提出了在有向无环图中求解 SPLC 问题的算法(Nettree for SPLC in Directed Acyclic Graphs, NSPLCDAG)。网树是一种多树根多双亲的数据结构。 NSPLCDAG 算法将该问题转化为一棵网树后，利用树根路径数这一性质对其进行求解。对 NSPLCDAG 算法进行改造，可以对最长路径问题进行求解，形成了网树在有向无环图中求解最长路径算法(Nettree for the Longest Path in DAGs, NLPDAG)，NLPDAG 算法可找到
4、所有的最长路径，在对 NLPDAG 算法做进一步改进以形成改进的 NLPDAG 算法，改进的 NLPDAG 算法可在线性时间复杂度内给出有向无环图中的一条最长路径。实验结果验证了 NSPLCDAG 和改进的 NLPDAG 算法的正确性与有效性。关键词 有向无环网络；简单路径；长度约束；最长路径；网树中图法分类号 * DOI 号： A Nettree for Simple Paths with Length Constraint and the Longest Path in Directed Acyclic GraphsLI Yan1), SUN Le2) , ZHU Huai-Zhong2)
5、 , WU You-Xi2)1)(School of Economics and Management, Hebei University of Technology, Tianjin 300401, China) 2)(School of Computer Science and Engineering, Hebei University of Technology, Tianjin 300401, China)Abstract The problem of Simple Paths with Length Constraint (SPLC) is to calculate the numb
6、er of simple paths between two vertices under the length constraint m in the graph. It is a special case of the k-path problem. In order to solve the problem in Directed Acyclic Graphs (DAGs), this paper proposes an algorithm named Nettree for Simple Paths with Length Constraint in DAGs (NSPLCDAG) b
7、ased on a data structure of Nettree which may have more than one root and one parent. First NSPLCDAG transforms the graph into a Nettree. Then the concept of the number of root paths of Nettree is used to solve the problem. Based on NSPLCDAG, a new algorithm named Nettree for the Longest Path in DAG
8、s (NLPDAG) is constructed which can find all the longest paths. Then NLPDAG is improved and the improved NLPDAG can find one of the longest paths with linear time complexity. The experimental results verify the correctness and effectiveness of the two algorithms of NSPLCDAG and the improved NLPDAG.K
9、ey words directed acyclic graphs; simple path; length constraint; the longest path; nettree2 计 算 机 学 报 20?年1 引言图是一种比线性表和树更为复杂的数据结构。在线性表中，结点间为单前驱单后继的线性关系；在树结构中，结点间为单前驱多后继的非线性关系；而在图结构中，结点间则为多前驱多后继的非线性关系，图中任意两个结点之间都可能相关。因此，图已经被广泛应用于诸如语言学、逻辑学、物理、化学、电气工程和计算机科学等学科中。在图论中，最长路径(the longest path)问题 1是在给定的图中找出
10、一条最长的简单路径。在无向图中求解最长路径是著名的NP难问题，现有的研究主要基于近似算法 2、参数化算法 3。另外一类研究是针对特殊图进行求解，并给出多项式时间复杂度的求解算法，例如Mertzios和Corneil 注采用一种深度优先搜索策略对伴相似图(cocomparability graphs)中 最长路径问题 进行了求解 ；Uehara 和Valiente4在二部置换图(bipartite permutation graphs)中对最长路径问题建立了线性时间复杂度的求解算法，其求解的二部置换图既是一个置换图也是一个二部图；Ioannidou等人 5在区间图(interval graphs
11、)中运用动态规划思想，对最长路径问题给出了时间复杂度为O(n 4)的求解算法；Edmonds和Chakraborty 6在有向无环图(Directed Acyclic Graphs，DAGs)所有边长度非负的情况下，对最长路径的方差和期望的边界进行了计算。而k-path 问题是指在给定的图中找出一条长度为k的简单路径，其是最长路径问题的一种特殊情况。Chen等人 7基于分治思想对一般图中的 k-path问题进行了研究，提高了该问题的计算速度。k-path问题在诸多领域具有非常重要的应用，Scott等人 8在生物学约束下，采用基于彩色编码技术，在酵母蛋白质相互作用网络中查找蛋白质传导路径，其求解
12、方法是将蛋白质作为结点，蛋白质之间相互作用关系作为边，以此构成生物蛋白质作用网络，权值最大的k-path 代表信号传导路径；Desaulniers等人 9利用推广k-path 的不均衡性(generalized k-path inequalities)对k个车辆的路由选择问题进行了研究。与k-path 问题相近的问题是注 Mertzios G, Corneil D. A simple polynomial algorithm for the longest path problem on cocomparability graphs. Technical report available at
13、 http:/arxiv.org/abs/1004.4560求解图中指定两点之间的路径长度为k的最大不相交路径问题，Itai等人 10给出该问题的判定问题是一个NP-Complete 问题的证明。求解两点之间路径长度为k的所有简单路径数是具有长度约束的简单路径(Simple Paths with Length Constraint，SPLC)问题。本文在有向无环图中求解该问题形成了SPLC in DAGs。SPLC in DAGs可在具有周期间隙约束的序列模式挖掘和具有间隙约束的模式匹配等方面得到应用。Zhang等人 11提出了具有周期间隙约束的序列模式挖掘问题，并将该模式挖掘方法应用在DNA
14、序列挖掘中。Tanbeer等人 12将具有周期间隙约束的序列模式挖掘方法应用于购买模式的挖掘。尽管Zhang等人采用了空间变换的方法进行序列模式挖掘，但是此方法的基础是具有间隙约束的模式匹配问题 13。虽然文献14是求解具有间隙约束和一次性条件的模式匹配问题，但是该论文给出了将具有间隙约束的模式匹配问题转换为有向无环图的算法，这使得具有间隙约束的模式匹配问题与SPLC in DAGs问题建立了实质性联系。为了解决SPLC in DAGs问题，本文利用网树数据结构(简称网树，Nettree) 13,15进行求解。网树是一种新的多前驱多后继的非线性数据结构，是对树结构的拓展。网树不仅具有树结构的所
15、有概念，如根结点，叶子结点，双亲，孩子，路径，层等，而且除根结点外，网树中任何结点可以有多个双亲结点。本文提出了网树求解有向无环图中具有长度约束的简单路径的算法(Nettree for Simple Paths with Length Constraint in DAGs, NSPLCDAG)， NSPLCDAG算法将该问题转化为一棵网树，然后利用网树的树根路径数这一特殊性质对该问题进行求解。NSPLCDAG算法的时间复杂度和空间复杂度分别为O(mnt)和O(n+|E|)，这里m, t, n和|E| 分别表示两点间的路径长度约束、顶点最大出度以及顶点数和边数。对NSPLCDAG算法做进一步改造
16、，可以形成求解最长路径问题的算法(Nettree for the Longest Path in DAGs, NLPDAG)。对NLPDAG算法做进一步改进形成改进的NLPDAG算法，该算法使得网树退化为一棵树的形式，并使算法的时间复杂度和空间复杂度分别为O(|E|)和O(n+|E |)，这里n和|E| 分别表示图的顶点数和边数。本文结构如下：第 2 节给出了 SPLC in DAGs问题的定义；第 3 节介绍了网树的概念和性质；第 4 节提出了 NSPLCDAG 算法，同时分析了?期 李艳等：网树求解有向无环图中具有长度约束的简单路径和最长路径问题 3NSPLCDAG 算法的时间复杂度和空间
17、复杂度，并通过示例来说明算法的工作原理；第 5 节提出了最长路径的求解算法并给出了求解示例；第 6 节给出了实验结果及分析；第 7 节得出了本文结论。2 问题的定义定义 1. 图 G=(V,E)，其中 V 称为顶点集，E称为边集。从顶点 v 到顶点 v的路径是一个有序顶点序列 S=v=v0, v1, , vm= v，其中顶点序列应满足 E(1 j m)。路径长度是路径中有向边的数目。如果序列 S 中任何两个顶点不重复出现，则称此路径为简单路径。定义 2. 具有长度约束的简单路径 SPLC 问题是指在图 G=(V,E)及图中任意两点 u, v V 和一个正整数 m，求解从 u 到 v 路径长度为
18、 m 的简单路径数问题。SPLC in DAGs 是指在给定的有向无环图中求解 SPLC 问题。定义 3. 邻接矩阵是表示顶点之间相邻关系的矩阵，图 G 采用邻接矩阵存储。二维数组元素 gij =1(1 i, j n, n=|V|)表示顶点 i 到顶点 j 之间存在一条有向边，否则表示顶点 i 到顶点 j 之间无边。顶点 vi 的出度 (用 OD(vi)表示)是第 i 行的元素之和，计算公式如下：(1)10)(njijigOD顶点 vi 的入度 (用 ID(vi)表示)是第 i 列的元素之和，计算公式如下：(2)10)(nji igI例 1. 如图 1 所示的有向无环图其顶点个数n=9，求从顶
19、点 1 到顶点 7 路径长度约束为 m=4 的简单路径数。图 1 一个有向无环图从图 1 可以看出，顶点 1 到 7 路径长度约束为 4 的路径数为 10，即1,2,4,3,7、1,2,3,6,7、1,4,3,6,7、1,2,5,8,7、1,4,5,8,7、1,4,9,8,7、1,5,9,8,7、1,2,4,9,7、1,2,5,9,7和1,4,5,9,7。SPLC in DAGs 问题的求解难度在于，顶点 u和 v 之间的路径数呈现指数形式，因此不能采用穷举法列出所有可能的路径并判定路径长度是否满足约束条件来进行求解，本文采用网树这一数据结构进行求解。3 网树的定义及性质本节给出了网树的定义和
20、性质。定义 4. 网树数据结构是结点的集合，这个集合可以为空集，否则这个集合由若干不同的根结点 r1, rm 和 0 或很多非空子网树 T1,T2, , Tn 构成，这些子网树的树根至少存在一条边与网树的根结点 ri 相连接，这里 1 m, 1 n 且 1 i n。图 2 给出了一棵一般意义上的网树。 r 1 r mT 1 T 2 T n图 2 一棵网树网树具有如下 5 个性质 13,15：(1)网树是树结构的拓展，它具备很多与树相似的概念，如根结点，叶子结点，层，双亲，孩子等；(2)一棵网树可以有 n 个根结点，其中 n 1；(3)除了根结点之外，网树的其它结点可以有多个双亲结点；(4)从一
21、个结点到达网树的一个根结点的路径数不唯一；(5)同一结点可以在网树的不同层上多次出现。定义 5. 由于同一结点可以在网树的不同层上多次出现，为了更好地区分网树结点，这里用 nij来表示第 j 层的结点 i。定义 6. 从结点 nij 到达根结点的路径数称为树根路径数(the number of root paths)，用 Nr (nij)来表示。树根路径数具有如下 2 个性质：4 计 算 机 学 报 20?年(1)根结点 ni1 的树根路径数为 1，即 Nr ( ni1)=1；(2)结点 nij 的树根路径数是其所有双亲结点的树根路径数之和，即( )= (3)rNij )(11kijrhkn这
22、里 是结点 nij 的第 k 个双亲，h 是结点 nij 的双kij1亲数。图 3 给出了一棵网树。在这棵网树中某些结点出现次数多于一次。例如结点 3 既在第二层出现又在第三层出现，本文采用 n32 和 n33 来分别描述第二层和第三层的结点 3。结点 n11，n 21 是网树的两个根结点；n 63, n53 和 n33 是网树的三个叶子结点。结点 n63 有两个双亲结点，分别是 n22 和 n32。结点 n32 的树根路径数 Nr(n32)=2，因为结点 n32 有两个双亲结点 n11 和 n21 且 Nr(n11)=Nr(n21)=1；同理可知，N r(n22)=1；N r(n63)=Nr
23、(n22)+Nr(n32)=3。网树的另一个特征是从一个结点到达网树的一个根结点的路径可能不唯一。例如叶子结点 n63 访问根结点 n11 有两条不同的路径，分别为n 63，n 32，n 11和n 63，n 22，n 11。图 3 一棵网树4 NSPLCDAG 算 法 描 述 及 复 杂 度 分 析4.1 算法描述采用 NSPLCDAG 算法求解图 G 中 u, v 两点间长度为 m 的简单路径数问题 的基本思想为：将有向无环图 G 转化为一棵 m+1 层网树，然后利用网树的树根路径数这一性质进行求解。在转化过程中，图 G 的顶点编号 i 即为网树结点名称 i，网树采用从树根层至 m+1 层逐
24、层创建的方式。将图G 转化为一棵网树及求解的流程如下：首先，将顶点 u 作为网树的根结点 nu1，该结点为网树的第一层且其树根路径数 Nr(nu1)=1；其次，依据网树第 j-1 层结点创建网树第 j 层结点。具体方法是：取网树中第 j-1 层结点 nij-1，如果 gil=1(1 l n)且在第 j 层未创建结点 nlj，则在网树的第 j 层创建结点 nlj 并在结点 nij-1 和结点nlj 间建立父子关系，并使得 nlj 的树根路径数与结点 nij-1 的树根路径数一致；若 gil=1(1 l n)且在第 j 层已创建结点 nlj，则在结点 nlj 和结点 nij-1间建立父子关系，并使
25、 nlj 的树根路径数累加上结点 nij-1 的树根路径数；最后，该网树第 m 层中与顶点 v 相连接的结点的树根路径数之和即为问题的解。NSPLCDAG算法的描述如下：算法 1. NSPLCDAG 算法输入：有向无环图的顶点数 n，有向无环图的邻接矩阵，顶点 u，v 和两点间的路径长度约束 m。输出：路径数 pathnum1.读取图的邻接矩阵 gij (1 i,j n);2.依据顶点 u 初始化网树的根结点;3.FOR(j=2;j0; j+)NLPDAG 算法的第 1619 行：16. K=j-2;17. pathK= 第 j-1 层的第一个结点名;18.由 pathK回溯至根结点形成最长路
26、径 path;19.RETURN path;由于 NLPDAG 算法必须由最深层叶子结点回溯至网树根结点，因此 NLPDAG 算法不能将之前的各层空间释放，故由 NSPLCDAG 算法的空间复杂度和时间复杂度分析易知，NLPDAG 算法的时6 计 算 机 学 报 20?年间复杂度和空间复杂度分别为 O(Knt)和O(Knt+|E|)，这里 K，t，n 和|E| 分别表示图中最长路径的长度，顶点最大出度，顶点数和边数。由于 NLPDAG 算法是由 NSPLCDAG 算法改进而来，因此 NLPDAG 算法不但可以找到一条最长路径，同时根据所建立的网树可以描述所有最长路径。以图 1 为例，说明最长路
27、径是如何获得的。由于图 1 中入度为 0 的顶点只有顶点 1，因此以顶点 1 为网树的根结点，并以此创建网树，网树的前四层与图 4 一致，依据第四层结点创建第五层结点 n65，n 75，n 85 和 n95，依据第五层结点创建第六层结点 n76 和 n86，依据第六层结点仅能够创建第七层结点 n77，由于顶点 7 的出度为 0，因此第八层结点个数为 0，循环结束，所创建的网树如图5 所示。故图 1 的最长路径的长度为 6，且最长路径的最终顶点为 7，而结点 n77 的第一个双亲结点为 n86；以此类推，回溯至第一层，就可以得到一条最长路径：1, 2, 4, 5, 9, 8, 7。从图 5 可以
28、看出，从结点 1 到结点 7 最长的路径只有一条，但在实际问题中，通常最长路径并不唯一。1 1 13 111 03482112122212111111798765398765435342第一层第四层第三层第二层6 8 97 87第五层第七层第六层图 5 求解图 1 中最长路径生成的网树如果仅需在有向无环图中找到一条最长路径，而无需计算最长路径的路径数，则可以对NLPDAG 算法进行改进。NLPDAG 算法在有向无环图中求解最长路径时，对很多冗余信息进行了计算，这是因为 NLPDAG 算法将顶点 i 所指向的所有顶点均作为网树中结点 i 的孩子结点，而在求解最长路径时，应仅选择满足删除有向边后，
29、顶点 j 的入度为 0 的点作为网树中顶点 i 的孩子结点，并形成改进的 NLPDAG 算法。由于此时不存在一个结点具有多个双亲的情况，因此网树也就退化为一棵树或一个森林（我们可以将树看成是网树的特例） 。具体算法如下：算法 3. 改进的 NLPDAG 算法输入：有向无环图的邻接矩阵输出：最长路径 path1.读取图的邻接矩阵 gij (1 i,j n);2.依据图 G 中入度为 0 的所有顶点来初始化网树的根结点;3.依次从已创建的网树中取一个未处理的结点 i，图 G 中所有有向边的顶点 j 的入度自减 ;4.IF (id(vj)=0) 为结点 i 创建孩子结点 j;5.重复步骤 3 和 4
30、 直至不再有新的结点产生;6.最长路径的长度= 网树的最大深度 -1, 由该叶子结点回溯至根结点以获得最长路径 path;7.RETURN path;由于改进的 NLPDAG 算法，对有向无环图中所有有向边仅处理一次，而每次处理的时间复杂度均在 O(1)内完成，因此改进的 NLPDAG 算法时间复杂度为 O(|E|)。易知，有向无环图若以三元组形式存储，改进的 NLPDAG 算法空间复杂度为O(n+|E|)。按照改进的 NLPDAG 算法对图 1 进行求解，易知算法生成的网树如图 6 所示。15342第一层第四层第三层第二层6 987第五层第七层第六层图 6 改进 NLPDAG 算法求解最长路
31、径生成的网树6 实验结果及分析6.1 实验结果文献16采用了链式队列数据结构对有向无环图中从 u 到 v 两点间全部简单路径问题进行了研?期 李艳等：网树求解有向无环图中具有长度约束的简单路径和最长路径问题 7究，并以产品族零部件关系网络为例，对实际有向无环网络中的应用加以说明，该算法的空间复杂度和时间复杂度均为 O(n3)。由于该算法是用来求解两点间全部简单路径，因此亦可用于求解本文的 SPLC in DAGs，该算法的时间复杂度与空间复杂度均保持不变。而本文 NSPLCDAG 算法亦可用于求解文献16的问题，求解的方法是以最长路径 K 为 SPLC in DAGs 的长度约束，所创建的网树
32、则可以表示文献16问题的解，显然 NSPLCDAG算法的时间复杂度和空间复杂度也没有发生任何变化。图 5 的网树则可描述文献16问题在图 1 上的解。因此本文的 NSPLCDAG 算法在求解相同问题时，算法的时间复杂度和空间复杂度均优于文献16的算法。两种算法的时间复杂度和空间复杂度对比如表 1 所示。表 1 SPLC in DAGs 的算法复杂度对比表算法 时间复杂度 空间复杂度文献 16算法 O(n3) O(n3)NSPLCDAG 算法 O(mnt) O(n +|E|)对最长路径问题本文给出了 NLPDAG 算法和改进的 NLPDAG 算法，这两种算法的时间复杂度和空间复杂度对比如表 2
33、所示。表 2 最长路径问题算法复杂度对比表算法 时间复杂度 空间复杂度NLPDAG 算法 O(Knt) O(Knt+|E|)改进的 NLPDAG 算法 O(|E|) O(n +|E|)为了获得较大规模的有向无环图，我们采用文献14中的算法，将具有间隙约束的模式匹配问题转化为有向无环图。本文采用了文献15中使用的前 4 种模式串 P1，P2，P 3 和 P4，并且忽略文献15中使用的全局约束。序列串采用美国国家生物计算信息中心公布的猪流感 H1N1 病毒的一种候选 DNA 序列(A/Managua /2093.01/2009(H1N1)A中的第一个片段的前 510 个字符，在增加源点和汇点后，使
34、得 DAG1 到 DAG4 的大小均为 512。为了避免序列串对问题求解的影响，DAG5 到 DAG8则采用文献15中的 P2 模式，而序列串则采用前述 DNA 序列的第一到第四个序列片段的全部字符，注：A/Managua/2093.01/2009(H1N1)可在 http:/www.ncbi.nlm.nih.gov /genomes/FLU/SwineFlu.html 下载在增加源点和汇点后，使得DAG5，DAG6，DAG7 和 DAG8 的大小分别为2288，2301，2171 和 1722。表 3 给出了生成本文八个有向无环图的模式串。表 3 生成有向无环图的模式串序号 模式串P1 a0
35、,3t0,3a0,3t0,3a0,3t0,3a0,3t0,3a0,3t0,3aP2 G1,5t0,6a2,7g3,9t2,5a4,9g1,8t2,9aP3 g1,9t1,9a1,9g1,9t1,9a1,9g1,9t1,9a1,9g1,9tP4 g1,5t0,6a2,7g3,9t2,5a4,9g1,8t2,9a1,9g1,9t实验运行的软硬件环境为：Intel(R) Core(TM)2 Duo CPU T7100 处理器、主频 1.80GHz、内存1G、Windows XP 操作系统。由于算法的运行速度较快，运行时间较短，为此本文全部实验均采用运行 100 次获得总的运行时间，然后单次运行时间为
36、总时间除以 100 的方法以便较为准确地获得算法在各个实例上的运行时间。为了测试有向无环图的大小对于算法运行时间的影响，对DAG1，DAG2，DAG3 和 DAG4 分别在256、320、384 和 448 个结点的子图以及原图中路径长度约束分别为 12，10，12 和 12 的条件下进行了测试，并与文献16算法的运行时间进行了对比，结果见表 4。表 4 不同大小有向无环图的算法运行时间对比表图名称 路径长度约束 m 顶点数 问题解(个)文献16 算法运行时间(ms)NSPLCDAG运行时间(ms)12 256 40 4.84 0.9412 320 40 5.32 1.2512 384 386
37、 12.5 2.0312 448 386 17.19 2.5DAG112 512 386 26.09 2.9710 256 12012 132.5 1.4110 320 24684 288.75 2.0310 384 31278 460.15 2.8110 448 42762 740.78 3.43DAG210 512 55923 904.53 4.2212 256 31373 355.31 1.5612 320 61608 901.25 1.5612 384 89704 1308.28 2.8112 448 99198 1647.97 4.22DAG312 512 135193 2526.1
38、 4.69DAG4 12 256 35539 357.03 0.878 计 算 机 学 报 20?年12 320 74458 1080.47 1.4412 384 109258 1548.12 3.0812 448 123782 2101.09 2.9112 512 167794 2901.4 2.83为了对比算法在不同路径长度约束下解的大小以及运行时间，对 DAG1 和 DAG2 两幅图在长度约束分别为 16，17，18，19，20 和 21 以及DAG3 和 DAG4 两幅图在长度约束分别为18，24，30，36，42 和 48 的情况下进行了测试，结果见表 5。表 5 不同长度约束下算法
39、运行时间图名称 路径长度约束 m 问题解(个)NSPLCDAG运行时间(ms)16 884 1.9717 0 1.9618 1092 2.5819 0 2.3320 360 2.03DAG121 0 2.0816 3281059 4.4717 0 4.0918 0 4.3019 26537036 4.4820 0 4.70DAG221 0 4.9718 9466972 5.6324 790664231 5.6230 56485170822 5.9436 4321739185142 7.3542 272754257287024 7.81DAG348 12638966539700128 9.061
40、8 13947750 4.5324 1340042909 6.4130 119833139429 7.1836 10906693648838 8.4442 756148905584048 8.44DAG448 51060826962548128 8.60表 6 给出了采用 NLPDAG 算法和改进的NLPDAG 算法求得的 DAG1 到 DAG8 共八副图的最长路径长度、最长路径及求解时间。6.2 实验结果分析(1)本文所提出的 NSPLCDAG 算法的效率要大大优于文献16所提出的算法。通过表 4 的全部 20 个实例可以看出，文献16算法的运行时间均显著长于本文算法。如在 DAG3中，当路
41、径长度约束 m 为 12 顶点数为 512 时，文献16算法的运行时间为 2526.1ms，而NSPLCDAG 算法的运行时间为 4.69ms。这些实验充分地说明了本文所提出的 NSPLCDAG 算法的效率要大大优于文献16算法。(2)文献16算法的求解时间与顶点数的大小相关，特别是与解的大小相关，解越大，求解时间显著增加。在表 4 的 DAG1 中，当路径长度约束 m 为12，顶点数分别为 384、448 和 512 时，问题解的大小均为 386，算法运行时间分别为12.50ms、17.19ms 和 26.09ms，这说明了文献16算法的运行时间与顶点数的大小相关。而在DAG2，DAG3 和
42、 DAG4 中，当解显著增加时，问题的求解时间也显著增大。如在 DAG3 中，当路径长度约束 m 为 12，顶点数分别为 384、448 和512 时，问题解的大小分别为 89704、99198 和135193，其运行时间分别为1308.28ms、1647.97ms 和 2526.1ms，这些实例充分地说明了当解显著增加时，文献16算法的求解时间也显著增大。产生上述现象的原因是，文献16的算法是从汇点出发，对每条简单路径进行逐一回溯，通过枚举所有可能的解来获得所有的简单路径，因而文献16的求解时间与解的大小相关。(3)NSPLCDAG 算法的求解时间与图的大小和长度约束大小相关，更为重要的是当
43、问题的解显著增加时，求解时间并不显著增大。通过表 4 可以看出，NSPLCDAG 算法的求解时间与图的尺寸未呈现绝对线性变化，但是当图的尺寸增大时，运行时间也相应增长，因此NSPLCDAG 算法的求解时间与图的大小呈正相关。表 5 也呈现出同样的特点，虽然运行时间与路径长度 m 未呈现绝对线性变化，但是随着路径长度约束 m 的增大，运行时间也相应增加，因此NSPLCDAG 算法的求解时间与长度约束呈正相关。此外，通过表 4 和 5 还可以看出，当问题的解快速增加时，问题的求解时间并未显著增大，这一特点在表 5 中体现尤为明显。如在 DAG4 中，当?期 李艳等：网树求解有向无环图中具有长度约束
44、的简单路径和最长路径问题 9路径长度约束由 18 变为 48 时，问题的解增加了近 5*109 倍，然而问题的求解时间增大不到一倍，这充分地说明了当问题的解显著增加时，求解时间并不显著增大。当路径长度约束为 18 时，DAG3 解的大小小于 DAG4 解的大小，但是在DAG3 中的运行时间却略长于 DAG4，这说明问题的求解速度与解的大小无关。表 6 最长路径及求解时间图名称NLPDAG 所求的最长路径的长度及最长路径 改进的 NLPDAG 所求的最长路径的长度及最长路径NLPDAG运行时间(ms)改进的 NLPDAG运行时间(ms)DAG120 1, 320, 322, 325, 328,
45、330, 332, 333, 337, 339, 342, 343, 344, 345, 346, 350, 353, 354, 357, 361, 51220 1, 320, 322, 325, 328, 330, 332, 333, 337, 339, 342, 343, 344, 345, 346, 350, 353, 354, 357, 361, 5121953 5.47DAG273 1, 131, 135, 137, 142, 146, 149, 154, 159, 169, 179, 470, 475, 484, 488, 493, 498, 508, 51273 133, 138
46、, 141, 144, 151, 153, 158, 162, 172, 182, 186, 460, 470, 476, 486, 496, 500, 504, 510, 5121515 4.38DAG375 1, 131, 135, 137, 142, 146, 149, 151, 153, 157, 160, 164, 169, 179, 189, 191, 193, 198, 200, 206, 214, 216, 221, 231, 239, 248, 250, 256, 260, 267, 269, 271, 273, 277, 283, 288, 290, 294, 296, 2
47、99, 303, 307, 313, 321, 327, 330, 340, 342, 349, 359, 366, 369, 372, 382, 386, 392, 397, 402, 408, 412, 414, 416, 418, 420, 426, 435, 440, 450, 460, 470, 475, 484, 488, 493, 498, 51275 126, 131, 135, 140, 142, 146, 149, 151, 153, 158, 162, 172, 182, 186, 192, 197, 199, 202, 209, 211, 214, 220, 222,
48、231, 241, 251, 257, 261, 264, 267, 269, 272, 275, 277, 284, 288, 292, 294, 296, 302, 304, 307, 317, 326, 332, 339, 341, 346, 354, 364, 366, 371, 376, 382, 386, 393, 399, 402, 408, 412, 414, 416, 423, 433, 437, 439, 444, 450, 460, 470, 476, 486, 496, 500, 504, 5121891 5.16DAG478 1, 131, 135, 137, 142, 146, 149, 151, 153, 157, 160, 164, 169, 179, 189, 190, 193, 198, 200, 206, 214, 216, 221, 231, 239, 248, 250, 256, 260, 267, 269, 271, 273, 274, 283, 288, 289, 294, 296, 299, 303, 307, 3
