DPC算法

在《网树求解有向无环图中具有长度约束的最大不相交路径》一文中提出的有向无环图构造生成算法。该论文信息如下:

李艳,武优西,黄春萍,张志颖,曾珍香. 网树求解有向无环图中具有长度约束的最大不相交路径. 通信学报. 2015, 36(8): 38-49

 

该算法可以依据用户输入的n, kd来随机生成从顶点1到顶点n路径长度为k情况下,最大不交路径数为w的有向无环图,这里d表示图中边密度,w为一个大于0.7倍理论最大不相交路径数(该数为(n-2)/(k-1))的随机数(注:因为如果最大不相交路径太少且在边密度较高情况下,任何一种算法都相对较容易获得较好质量的解,因此难于用来评价算法的好坏,这一点在后面的实验中也有所体现). 该算法采用的原理如下:

第一步:随机生成w*(k-1)个不同数字,其范围为2到n-1,每个数字表示一个顶点名;

第二步:建立一条长度为k的路径. 每k-1个数字与顶点1和n一起构成一条长度为k的路径,具体做法是从前一个数字顶点向后一个数字顶点建立一条有向边,然后顶点1向这k-1个数字中第一个数字顶点建立一条有向边,最后一个顶点向顶点n建立一条有向边;

第三步:迭代第二步,直到建立w条长度为k的不相交路径;

第四步:随机加边. 随机生成两个介于1到n-1之间的数字ab,判断从ab的有向边是否存在,如果存在重新生成;如果ab相同,也重新生成;如果会产生回路也重新生成(从顶点b出发,依据当前图G的状态,采用广度优先搜索策略,如果能够回到顶点a,说明存在回路),直到可以生成一组满足要求的数字,然后在顶点ab之间建立一条有向边;

第五步:迭代第四步,直到图中边的密度为用户指定的d值后停止.

由于第二和第三步保证了顶点1到顶点n之间有w条路径长度为k的不相交路径,并且第四步在生成边的过程中b最大为n-1,不能取到n,这样顶点n的入度就仅仅为w,这样就确保随机生成的有向无环图从顶点1到顶点n之间最多仅有w条路径长度为k的不相交路径.

 

算法的源代码:dpc

发表评论