网树求解有向无环图中具有长度约束的简单路径和最长路径问题.doc

?期 李艳等：网树求解有向无环图中具有长度约束的简单路径和最长路径问题 11
网树求解有向无环图中具有长度约束的简单路径和最长路径问题
李艳1), 孙乐2), 朱怀忠2) , 武优西2)
1)( 河北工业大学 经济管理学院, 天津 中国 300401)
2)(河北工业大学 计算机科学与软件学院, 天津 中国 300401)
摘 要 具有长度约束的简单路径问题(Simple Paths with Length Constraint, SPLC)是指求解图G中任意两点间路径长度为m的简单路径数，是k-path 问题的一种特殊情况。本文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs, NSPLCDAG)。网树是一种多树根多双亲的数据结构。NSPLCDAG算法将该问题转化为一棵网树后，利用树根路径数这一性质对其进行求解。对NSPLCDAG算法进行改造，可以对最长路径问题进行求解，形成了网树在有向无环图中求解最长路径算法(Nettree for the Longest Path in DAGs, NLPDAG)，NLPDAG算法可找到所有的最长路径，在对NLPDAG算法做进一步改进以形成改进的NLPDAG算法，改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径。实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性。
关键词 有向无环网络；简单路径；长度约束；最长路径；网树
中图法分类号 ****　　　DOI号：
A Nettree for Simple Paths with Length Constraint and the Longest Path in Directed Acyclic Graphs
LI Yan1), SUN Le2) , ZHU Huai-Zhong2) , 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 number 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) based 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 DAGs (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.
Key words directed acyclic graphs; simple path; length constraint; the longest path; nettree

1 引言
图是一种比线性表和树更为复杂的数据结构。在线性表中，结点间为单前驱单后继的线性关系；在树结构中，结点间为单前驱多后继的非线性关系；而在图结构中，结点间则为多前驱多后继的非线性关系，图中任意两个结点之间都可能相关。因此，图已经被广泛应用于诸如语言学、逻辑学、物理、化学、电气工程和计算机科学等学科中。
在图论中，最长路径(the longest path)问题[1]是在给定的图中找出一条最长的简单路径。在无向图中求解最长路径是著名的NP难问题，现有的研究主要基于近似算法[2]、参数化算法[3]。另外一类研究是针对特殊图进行求解，并给出多项式时间复杂度的求解算法，例如Mertzios和Corneil注 Mertzios G, Corneil D. A simple polynomial algorithm for the longest path problem on cocomparability graphs. Technical report available at http://arxiv.org/abs/1004.4560
采用一种深度优先搜索策略对伴相似图(cocomparability graphs)中最长路径问题进行了求解；Uehara和Valiente[4]在二部置换图(bipartite permutation graphs)中对最长路径问题建立了线性时间复杂度的求解算法，其求解的二部置换图既是一个置换图也是一个二部图；Ioannidou等人[5]在区间图(interval graphs)中运用动态规划思想，对最长路径问题给出了时间复杂度为O(n4)的求解算法；Edmonds和Chakraborty[6]在有向无环图(Directed Acyclic Graphs，DAGs)所有边长度非负的情况下，对最长路径的方差和期望的边界进行了计算。
而k-path 问题是指在给定的图中找出一条长度为k的简单路径，其是最长路径问题的一种特殊情况。Chen等人[7]基于分治思想对一般图中的k-path问题进行了研究，提高了该问题的计算速度。k-path问题在诸多领域具有非常重要的应用，Scott等人[8]在生物学约束下，采用基于彩色编码技术，在酵母蛋白质相互作用网络中查找蛋白质传导路径，其求解方法是将蛋白质作为结点，蛋白质之间相互作用关系作为边，以此构成生物蛋白质作用网络，权值最大的k-path代表信号传导路径；Desaulniers等人[9]利用推广k-path的不均衡性(generalized k-path inequalities)对k个车辆的路由选择问题进行了研究。与k-path问题相近的问题是求解图中指定两点之间的路径长度为k的最大不相交路径问题，Itai等人[10]给出该问题的判定问题是一个NP-Complete问题的证明。求解两点之间路径长度为k的所有简单路径数是具有长度约束的简单路径(Simple Paths with Length Constraint，SPLC)问题。本文在有向无环图中求解该问题形成了SPLC in DAGs。SPLC in DAGs可在具有周期间隙约束的序列模式挖掘和具有间隙约束的模式匹配等方面得到应用。Zhang等人[11]提出了具有周期间隙约束的序列模式挖掘问题，并将该模式挖掘方法应用在DNA序列挖掘中。Tanbeer等人[12]将具有周期间隙约束的序列模式挖掘方法应用于购买模式的挖掘。尽管Zhang等人采用了空间变换的方法进行序列模式挖掘，但是此方法的基础是具有间隙约束的模式匹配问题[13]。虽然文献[14]是求解具有间隙约束和一次性条件的模式匹配问题，但是该论文给出了将具有间隙约束的模式匹配问题转换为有向无环图的算法，这使得具有间隙约束的模式匹配问题与SPLC in DAGs问题建立了实质性联系。
为了解决SPLC in DAGs问题，本文利用网树数据结构(简称网树，Nettree)[13,15]进行求解。网树是一种新的多前驱多后继的非线性数据结构，是对树结构的拓展。网树不仅具有树结构的所有概念，如根结点，叶子结点，双亲，孩子，路径，层等，而且除根结点外，网树中任何结点可以有多个双亲结点。本文提出了网树求解有向无环图中具有长度约束的简单路径的算法(Nettree for Simple Paths with Length Constraint in DAGs, NSPLCDAG)，NSPLCDAG算法将该问题转化为一棵网树，然后利用网树的树根路径数这一特殊性质对该问题进行求解。NSPLCDAG算法的时间复杂度和空间复杂度分别为O(m×n×t)和O(n+|E|)，这里m, t, n和|E|分别表示两点间的路径长度约束、顶点最大出度以及顶点数和边数。对NSPLCDAG算法做进一步改造，可以形成求解最长路径问题的算法(Nettree for the Longest Path in DAGs, NLPDAG)。对NLPDAG算法做进一步改进形成改进的NLPDAG算法，该算法使得网树退化为一棵树的形式，并使算法的时间复杂度和空间复杂度分别为O(|E|)和O(n+|E|)，这里n和|E|分别表示图的顶点数和边数。
本文结构如下：第2节给出了SPLC in DAGs问题的定义；第3节介绍了网树的概念和性质；第4节提出了NSPLCDAG算法，同时分析了NSPLCDAG算法的时间复杂度和空间复杂度，并通过示例来说明算法的工作原理；第5节提出了最长路径的求解算法并给出了求解示例；第6节给出了实验结果及分析；第7节得出了本文结论。
2 问题的定义
定义1. 图G=(V,E)，其中V称为顶点集，E称为边集。从顶点v到顶点v’的路径是一个有序顶点序列S={v=v0, v1, …, vm= v’}，其中顶点序列应满足<vj-1, vj>E(1jm)。路径长度是路径中有向边的数目。如果序列S中任何两个顶点不重复出现，则称此路径为简单路径。
定义2. 具有长度约束的简单路径SPLC问题是指在图G=(V,E)及图中任意两点u, vV和一个正整数m，求解从u到v路径长度为m的简单路径数问题。SPLC in DAGs是指在给定的有向无环图中求解SPLC问题。
定义3. 邻接矩阵是表示顶点之间相邻关系的矩阵，图G采用邻接矩阵存储。二维数组元素g[i][j] =1(1i, jn, n=|V|)表示顶点i到顶点j之间存在一条有向边，否则表示顶点i到顶点j之间无边。
顶点vi的出度(用OD(vi)表示)是第i行的元素之和，计算公式如下：
(1)
顶点vi的入度(用ID(vi)表示)是第i列的元素之和，计算公式如下：
(2)
例1. 如图1所示的有向无环图其顶点个数n=9，求从顶点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 网树的定义及性质
本节给出了网树的定义和性质。
定义4. 网树数据结构是结点的集合，这个集合可以为空集，否则这个集合由若干不同的根结点r1,…, rm 和0或很多非空子网树T1,T2, …, Tn构成，这些子网树的树根至少存在一条边与网树的根结点ri 相连接，这里1m, 1n 且 1in。
图2给出了一棵一般意义上的网树。

图2 一棵网树

网树具有如下5个性质[13,15]：
(1)网树是树结构的拓展，它具备很多与树相似的概念，如根结点，叶子结点，层，双亲，孩子等；
(2)一棵网树可以有n个根结点，其中n1；
(3)除了根结点之外，网树的其它结点可以有多个双亲结点；
(4)从一个结点到达网树的一个根结点的路径数不唯一；
(5)同一结点可以在网树的不同层上多次出现。
定义5. 由于同一结点可以在网树的不同层上多次出现，为了更好地区分网树结点，这里用nij来表示第j层的结点i。
定义6. 从结点nij到达根结点的路径数称为树根路径数(the number of root paths)，用Nr (nij)来表示。
树根路径数具有如下2个性质：
(1)根结点ni1的树根路径数为1，即Nr ( ni1)=1；
(2)结点nij的树根路径数是其所有双亲结点的树根路径数之和，即
()= (3)
这里是结点nij的第k个双亲，h是结点nij的双亲数。
图3给出了一棵网树。在这棵网树中某些结点出现次数多于一次。例如结点3既在第二层出现又在第三层出现，本文采用n32和n33来分别描述第二层和第三层的结点3。结点n11，n21是网树的两个根结点；n63, n53和n33是网树的三个叶子结点。结点n63有两个双亲结点，分别是n22和n32。结点n32的树根路径数Nr(n32)=2，因为结点n32有两个双亲结点n11和n21且Nr(n11)=Nr(n21)=1；同理可知，Nr(n22)=1；Nr(n63)=Nr(n22)+Nr(n32)=3。网树的另一个特征是从一个结点到达网树的一个根结点的路径可能不唯一。例如叶子结点n63访问根结点n11有两条不同的路径，分别为{n63，n32，n11}和{n63，n22，n11}。

图3 一棵网树
4 NSPLCDAG算法描述及复杂度分析
4.1 算法描述
采用NSPLCDAG算法求解图G中u, v两点间长度为m的简单路径数问题的基本思想为：将有向无环图G转化为一棵m+1层网树，然后利用网树的树根路径数这一性质进行求解。在转化过程中，图G的顶点编号i即为网树结点名称i，网树采用从树根层至m+1层逐层创建的方式。将图G转化为一棵网树及求解的流程如下：
首先，将顶点u作为网树的根结点nu1，该结点为网树的第一层且其树根路径数Nr(nu1)=1；
其次，依据网树第j-1层结点创建网树第j层结点。具体方法是：取网树中第j-1层结点nij-1，如果g[i][l]=1(1ln)且在第j层未创建结点nlj，则在网树的第j层创建结点nlj并在结点nij-1和结点nlj间建立父子关系，并使得nlj的树根路径数与结点nij-1的树根路径数一致；若g[i][l]=1(1ln)且在第j层已创建结点nlj，则在结点nlj和结点nij-1间建立父子关系，并使nlj的树根路径数累加上结点nij-1的树根路径数；
最后，该网树第m层中与顶点v相连接的结点的树根路径数之和即为问题的解。NSPLCDAG算法的描述如下：
算法1. NSPLCDAG算法
输入：有向无环图的顶点数n，有向无环图的邻接矩阵，顶点u，v和两点间的路径长度约束m。
输出：路径数pathnum
1.读取图的邻接矩阵g[i][j] (1i,j n);
2.依据顶点u初始化网树的根结点;
3.FOR(j=2;j<=m;j++)
4. FOR (a=0;a<网树第j-1层结点数; a++)
5. i=网树第j-1层第a+1个结点的名称;
6. FOR (b=0;b<OD(Vi);b++)
7. l=顶点i的第b+1个弧的弧尾顶点;
8. IF (nlj未被创建)
9. 创建nlj结点，Nr (nlj)= Nr ( nij-1)，第j层结点数自增;
10. ELSE
11. Nr (nlj)+= Nr ( nij-1);
12. END IF
13. END FOR
14. END FOR
15. END FOR
16. FOR (d=0;d<网树第m层结点数; d++)
17. IF (g[d][v]==1) pathnum+=Nr(ndm);
18.END FOR
19.RETURN pathnum;

4.2 NSPLCDAG算法复杂度分析
NSPLCDAG算法的空间复杂度是O(m×n×t+n2)且可进一步优化为O(n+|E|)，这里m, t, n和|E|分别表示两点间的路径长度约束、顶点最大出度、顶点数和边数。NSPLCDAG算法占用的空间是由网树和图G的邻接矩阵两部分组成的。第一部分网树的开销为O(m×n×t)，这是因为网树的深度是m，网树中每层最多有n个结点，且每个结点最多有t个孩子。对NSPLCDAG算法可以做进一步改进，使网树的空间开销为O(n)，其改进方法如下：由于NSPLCDAG算法仅依据网树中上一层结点信息来创建下一层结点，因此在存储网树的过程中仅保留一层网树结点即可。此外，在解决SPLC in DAGs问题时，可以不必存储网树的父子关系，而仅计算当前结点的树根路径数，这样网树的开销可以缩减为O(n)。第二部分存储图G邻接矩阵的开销为O(n2)，也可以将图G存储为三元组形式，其开销为O(|E|)，因此NSPLCDAG算法优化后的空间复杂度为O(n+|E|)。
NSPLCDAG算法的时间复杂度为O(m×n×t)。这是因为算法的第3行循环次数为O(m)，第4行的最坏循环次数为O(n)，第6行的最坏循环次数为O(t)，算法的第5，7，9和11行均在O(1)时间内即可完成，算法的16~18行的最坏时间复杂度为O(n)。综上，NSPLCDAG算法的时间复杂度为O(m×n×t)。
4.3 NSPLCDAG算法运行实例
以例1为例来说明NSPLCDAG算法的工作原理。
根据NSPLCDAG算法的思想，将例1中的有向无环图转化为一棵5层网树，所建立网树如图4所示。在图4中箭头方向代表创建网树的方向，图中白色圆圈内数字代表网树结点名称，灰色圆圈内数字代表该结点的树根路径数。网树的创建和计算过程如下：

图4 求解图1中从点1到点7路径长度为4的网树

将顶点1作为网树的根结点n11，树根路径数Nr (n11)=1。将满足g[1][l]=1(1ln)条件的所有顶点创建为网树第二层结点nl2，因此网树的第二层结点分别是n22，n32，n42和n52，且这些结点的树根路径数均为1。之后，对结点n22创建孩子结点，创建依据为g[2][l]=1(1l n)，这样可以创建第三层的结点n33，n43，n53和n63，且这些结点的树根路径数均为1。依据g[3][l]=1(1ln)对结点n32创建孩子结点，易知结点n32有两个孩子结点，分别为n63和n73，此时n63的树根路径数为2。以此类推可以建立网树第三层和第四层全部结点。由于路径长度为4，因此根据第四层结点与顶点7的连接情况，即g[l][7]=1(1ln)的情况建立父子关系。由图4易知，问题的解为1+2+4+3=10。
5 网树求解最长路径问题
求解最长路径问题是图论中经典问题之一，其是指在给定的图G中找到路径长度最长的一条简单路径。将NSPLCDAG算法中根据顶点u创建网树的根结点变为依据图G中所有入度为0的顶点来初始化网树的根结点，同时将创建网树深度为指定的长度约束变为网树不再有新的结点产生，即可对最长路径问题进行求解，形成网树求解最长路径问题的算法(Nettree for the Longest Path in DAGs, NLPDAG)。由于需要产生一条最长路径，因此NLPDAG算法需要从网树最深的一个叶子结点回溯至网树根结点以产生最长路径。故NLPDAG算法需要对NSPLCDAG算法的第2~3行和16~19行进行修改，其余各行均保持不变即可，具体修改如下：
算法2. NLPDAG算法
输入：有向无环图的邻接矩阵
输出：最长路径path
NLPDAG算法的第2~3行：
2.依据图G中所有入度为0的顶点来初始化网树的根结点;
3.FOR(j=2;第j-1层结点个数>0;j++)

NLPDAG算法的第16~19行：
16. K=j-2;
17. path[K]= 第j-1层的第一个结点名;
18.由path[K]回溯至根结点形成最长路径path;
19.RETURN path;

由于NLPDAG算法必须由最深层叶子结点回溯至网树根结点，因此NLPDAG算法不能将之前的各层空间释放，故由NSPLCDAG算法的空间复杂度和时间复杂度分析易知，NLPDAG算法的时间复杂度和空间复杂度分别为O(K×n×t)和O(K×n×t+|E|)，这里K，t，n和|E|分别表示图中最长路径的长度，顶点最大出度，顶点数和边数。由于NLPDAG算法是由NSPLCDAG算法改进而来，因此NLPDAG算法不但可以找到一条最长路径，同时根据所建立的网树可以描述所有最长路径。
以图1为例，说明最长路径是如何获得的。由于图1中入度为0的顶点只有顶点1，因此以顶点1为网树的根结点，并以此创建网树，网树的前四层与图4一致，依据第四层结点创建第五层结点n65，n75，n85和n95，依据第五层结点创建第六层结点n76和n86，依据第六层结点仅能够创建第七层结点n77，由于顶点7的出度为0，因此第八层结点个数为0，循环结束，所创建的网树如图5所示。故图1的最长路径的长度为6，且最长路径的最终顶点为7，而结点n77的第一个双亲结点为n86；以此类推，回溯至第一层，就可以得到一条最长路径：{1, 2, 4, 5, 9, 8, 7}。从图5可以看出，从结点1到结点7最长的路径只有一条，但在实际问题中，通常最长路径并不唯一。

图5 求解图1中最长路径生成的网树

如果仅需在有向无环图中找到一条最长路径，而无需计算最长路径的路径数，则可以对NLPDAG算法进行改进。NLPDAG算法在有向无环图中求解最长路径时，对很多冗余信息进行了计算，这是因为NLPDAG算法将顶点i所指向的所有顶点均作为网树中结点i的孩子结点，而在求解最长路径时，应仅选择满足删除有向边<i,j>后，顶点j的入度为0的点作为网树中顶点i的孩子结点，并形成改进的NLPDAG算法。由于此时不存在一个结点具有多个双亲的情况，因此网树也就退化为一棵树或一个森林（我们可以将树看成是网树的特例）。具体算法如下：
算法3. 改进的NLPDAG算法
输入：有向无环图的邻接矩阵
输出：最长路径path
1.读取图的邻接矩阵g[i][j] (1i,j n);
2.依据图G中入度为0的所有顶点来初始化网树的根结点;
3.依次从已创建的网树中取一个未处理的结点i，图G中所有有向边<i,j>的顶点j的入度自减;
4.IF (id(vj)==0) 为结点i创建孩子结点j;
5.重复步骤3和4直至不再有新的结点产生;
6.最长路径的长度=网树的最大深度-1, 由该叶子结点回溯至根结点以获得最长路径path;
7.RETURN path;

由于改进的NLPDAG算法，对有向无环图中所有有向边仅处理一次，而每次处理的时间复杂度均在O(1)内完成，因此改进的NLPDAG算法时间复杂度为O(|E|)。易知，有向无环图若以三元组形式存储，改进的NLPDAG算法空间复杂度为O(n+|E|)。
按照改进的NLPDAG算法对图1进行求解，易知算法生成的网树如图6所示。

图6 改进NLPDAG算法求解最长路径生成的网树
6 实验结果及分析
6.1 实验结果
文献[16]采用了链式队列数据结构对有向无环图中从u到v两点间全部简单路径问题进行了研究，并以产品族零部件关系网络为例，对实际有向无环网络中的应用加以说明，该算法的空间复杂度和时间复杂度均为O(n3)。由于该算法是用来求解两点间全部简单路径，因此亦可用于求解本文的SPLC in DAGs，该算法的时间复杂度与空间复杂度均保持不变。而本文NSPLCDAG算法亦可用于求解文献[16]的问题，求解的方法是以最长路径K为SPLC in DAGs的长度约束，所创建的网树则可以表示文献[16]问题的解，显然NSPLCDAG算法的时间复杂度和空间复杂度也没有发生任何变化。图5的网树则可描述文献[16]问题在图1上的解。因此本文的NSPLCDAG算法在求解相同问题时，算法的时间复杂度和空间复杂度均优于文献[16]的算法。两种算法的时间复杂度和空间复杂度对比如表1所示。
表1 SPLC in DAGs的算法复杂度对比表
算法
时间复杂度
空间复杂度
文献[16]算法
O(n3)
O(n3)
NSPLCDAG算法
O(m×n×t)
O(n +|E|)

对最长路径问题本文给出了NLPDAG算法和改进的NLPDAG算法，这两种算法的时间复杂度和空间复杂度对比如表2所示。

表2 最长路径问题算法复杂度对比表
算法
时间复杂度
空间复杂度
NLPDAG算法
O(K×n×t)
O(K×n×t+|E|)
改进的NLPDAG算法
O(|E|)
O(n +|E|)

为了获得较大规模的有向无环图，我们采用文献[14]中的算法，将具有间隙约束的模式匹配问题转化为有向无环图。本文采用了文献[15]中使用的前4种模式串P1，P2，P3和P4，并且忽略文献[15]中使用的全局约束。序列串采用美国国家生物计算信息中心公布的猪流感H1N1病毒的一种候选DNA序列(A/Managua/2093.01/2009(H1N1))注：A/Managua/2093.01/2009(H1N1)可在http://www.ncbi.nlm.nih.gov /genomes/FLU/SwineFlu.html 下载
中的第一个片段的前510个字符，在增加源点和汇点后，使得DAG1到DAG4的大小均为512。为了避免序列串对问题求解的影响，DAG5到DAG8则采用文献[15]中的P2模式，而序列串则采用前述DNA序列的第一到第四个序列片段的全部字符，在增加源点和汇点后，使得DAG5，DAG6，DAG7和DAG8的大小分别为2288，2301，2171和1722。表3给出了生成本文八个有向无环图的模式串。

表3 生成有向无环图的模式串
序号
模式串
P1
a[0,3]t[0,3]a[0,3]t[0,3]a[0,3]t[0,3]a[0,3]t[0,3]a[0,3]t[0,3]a
P2
G[1,5]t[0,6]a[2,7]g[3,9]t[2,5]a[4,9]g[1,8]t[2,9]a
P3
g[1,9]t[1,9]a[1,9]g[1,9]t[1,9]a[1,9]g[1,9]t[1,9]a[1,9]g[1,9]t
P4
g[1,5]t[0,6]a[2,7]g[3,9]t[2,5]a[4,9]g[1,8]t[2,9]a[1,9]g[1,9]t

实验运行的软硬件环境为：Intel(R) Core(TM)2 Duo CPU T7100处理器、主频1.80GHz、内存1G、Windows XP操作系统。由于算法的运行速度较快，运行时间较短，为此本文全部实验均采用运行100次获得总的运行时间，然后单次运行时间为总时间除以100的方法以便较为准确地获得算法在各个实例上的运行时间。为了测试有向无环图的大小对于算法运行时间的影响，对DAG1，DAG2，DAG3和DAG4分别在256、320、384和448个结点的子图以及原图中路径长度约束分别为12，10，12和12的条件下进行了测试，并与文献[16]算法的运行时间进行了对比，结果见表4。

表4 不同大小有向无环图的算法运行时间对比表
图名称
路径长度约束m
顶点数
问题解(个)
文献[16]算法
运行时间(ms)
NSPLCDAG
运行时间(ms)
DAG1
12
256
40
4.84
0.94
12
320
40
5.32
1.25
12
384
386
12.5
2.03
12
448
386
17.19
2.5
12
512
386
26.09
2.97
DAG2
10
256
12012
132.5
1.41
10
320
24684
288.75
2.03
10
384
31278
460.15
2.81
10
448
42762
740.78
3.43
10
512
55923
904.53
4.22
DAG3
12
256
31373
355.31
1.56
12
320
61608
901.25
1.56
12
384
89704
1308.28
2.81
12
448
99198
1647.97
4.22
12
512
135193
2526.1
4.69
DAG4
12
256
35539
357.03
0.87
12
320
74458
1080.47
1.44
12
384
109258
1548.12
3.08
12
448
123782
2101.09
2.91
12
512
167794
2901.4
2.83
为了对比算法在不同路径长度约束下解的大小以及运行时间，对DAG1和DAG2两幅图在长度约束分别为16，17，18，19，20和21以及DAG3和DAG4两幅图在长度约束分别为18，24，30，36，42和48的情况下进行了测试，结果见表5。

表5 不同长度约束下算法运行时间
图名称
路径长度约束m
问题解(个)
NSPLCDAG
运行时间(ms)
DAG1
16
884
1.97
17
0
1.96
18
1092
2.58
19
0
2.33
20
360
2.03
21
0
2.08
DAG2
16
3281059
4.47
17
0
4.09
18
0
4.30
19
26537036
4.48
20
0
4.70
21
0
4.97
DAG3
18
9466972
5.63
24
790664231
5.62
30
56485170822
5.94
36
4321739185142
7.35
42
272754257287024
7.81
48
12638966539700128
9.06
DAG4
18
13947750
4.53
24
1340042909
6.41
30
119833139429
7.18
36
10906693648838
8.44
42
756148905584048
8.44
48
51060826962548128
8.60

表6给出了采用NLPDAG算法和改进的NLPDAG算法求得的DAG1到DAG8共八副图的最长路径长度、最长路径及求解时间。
6.2 实验结果分析
(1)本文所提出的NSPLCDAG算法的效率要大大优于文献[16]所提出的算法。
通过表4的全部20个实例可以看出，文献[16]算法的运行时间均显著长于本文算法。如在DAG3中，当路径长度约束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和DAG4中，当解显著增加时，问题的求解时间也显著增大。如在DAG3中，当路径长度约束m为12，顶点数分别为384、448和512时，问题解的大小分别为89704、99198和135193，其运行时间分别为1308.28ms、1647.97ms和2526.1ms，这些实例充分地说明了当解显著增加时，文献[16]算法的求解时间也显著增大。产生上述现象的原因是，文献[16]的算法是从汇点出发，对每条简单路径进行逐一回溯，通过枚举所有可能的解来获得所有的简单路径，因而文献[16]的求解时间与解的大小相关。
(3)NSPLCDAG算法的求解时间与图的大小和长度约束大小相关，更为重要的是当问题的解显著增加时，求解时间并不显著增大。
通过表4可以看出，NSPLCDAG算法的求解时间与图的尺寸未呈现绝对线性变化，但是当图的尺寸增大时，运行时间也相应增长，因此NSPLCDAG算法的求解时间与图的大小呈正相关。表5也呈现出同样的特点，虽然运行时间与路径长度m未呈现绝对线性变化，但是随着路径长度约束m的增大，运行时间也相应增加，因此NSPLCDAG算法的求解时间与长度约束呈正相关。此外，通过表4和5还可以看出，当问题的解快速增加时，问题的求解时间并未显著增大，这一特点在表5中体现尤为明显。如在DAG4中，当路径长度约束由18变为48时，问题的解增加了近5*109倍，然而问题的求解时间增大不到一倍，这充分地说明了当问题的解显著增加时，求解时间并不显著增大。当路径长度约束为18时，DAG3解的大小小于DAG4解的大小，但是在DAG3中的运行时间却略长于DAG4，这说明问题的求解速度与解的大小无关。

表6 最长路径及求解时间
图名称
NLPDAG所求的最长路径的长度及最长路径
改进的NLPDAG所求的最长路径的长度及最长路径
NLPDAG
运行时间(ms)
改进的NLPDAG
运行时间(ms)
DAG1
20 {1, 320, 322, 325, 328, 330, 332, 333,