Page 20 - 《软件学报》2021年第11期

3346 Journal of Software 软件学报 Vol.32, No.11, November 2021

Table 5 Comparison of running time on sequences S1~S8
表 5 在序列 S1~S8 上运行时间的比较
不同模式下算法的运行时间(ms)
序列 算法
P1 P2 P3 P4 P5 P6 P7 P8 P9
INSGrow 2.8 2.48 3.44 3.12 3.12 3.42 2.5 2.5 1.86
NETLAP-nonpruning 13.11 22.31 41.65 26.67 26.37 17.32 17.79 12.48 12.64
S1 NETLAP-best 14.04 23.87 46.05 29.98 30.26 17.52 19.71 13.64 12.97
NETGap 14.97 24.18 46.65 30.89 30.73 17.47 19.65 13.41 13.89
NetBack 13.58 21.84 43.68 26.52 27.45 15.76 17.54 12.17 11.86
INSGrow 2.8 2.5 2.82 2.8 3.44 2.48 3.12 3.12 2.5
NETLAP-nonpruning 12.16 24.02 42.27 29.8 27.08 16.38 19.04 11.85 14.35
S2 NETLAP-best 14.05 24.88 44.62 31.2 29.84 18.01 20.66 12.16 15.76
NETGap 14.35 25.43 44.78 32.07 31.83 18.09 21.21 13.41 15.29
NetBack 12.78 23.24 43.37 29.64 28.46 16.22 19.34 11.71 13.57
INSGrow 2.8 2.5 3.44 2.82 3.1 3.12 2.82 2.5 2.5
NETLAP-nonpruning 11.39 21.69 39.94 26.68 25.28 16.38 18.74 10.14 13.42
S3 NETLAP-best 13.22 22.77 44.3 29.86 28.64 17.63 20.23 10.61 14.32
NETGap 13.42 24.18 46.49 30.73 29.95 18.41 20.91 11.38 14.66
NetBack 12.01 21.37 41.34 26.83 25.46 15.91 18.61 10.14 12.79
INSGrow 2.8 2.18 2.82 2.8 2.8 1.88 2.5 2.48 1.86
NETLAP-nonpruning 12.5 21.9 43.7 26.5 29.7 14 15.6 9.3 10.9
S4 NETLAP-best 15.6 20.53 45.2 28.1 26.2 15.6 16.84 9.36 11.54
NETGap 14.68 19.66 38.7 25.28 25.28 15.3 16.86 9.68 10.92
NetBack 11.86 17.48 33.08 21.22 22.14 12.8 15.6 8.74 9.98
INSGrow 1.86 2.18 2.5 2.18 3.12 2.5 2.2 2.2 2.18
NETLAP-nonpruning 7.8 14.1 29.6 17.2 17.2 12.5 12.4 7.8 9.4
S5 NETLAP-best 8.74 15.3 32.44 19.34 21.8 13.12 14.04 8.12 9.66
NETGap 9.36 15.6 30.58 19.66 19.34 12.48 13.74 8.1 9.36
NetBack 8.1 14.04 28.4 17.48 18.1 11.26 12.8 7.5 8.74
INSGrow 2.18 2.2 2.5 2.2 2.5 2.5 2.5 2.5 2.18
NETLAP-nonpruning 9.4 14.1 26.5 17.1 17.2 10.9 15 7.8 9.4
S6 NETLAP-best 9.06 14.34 29.34 17.78 17.46 12.16 13.4 7.48 9.98
NETGap 9.66 14.98 29.64 18.1 18.42 11.22 13.1 7.18 9.98
NetBack 8.74 13.4 27.14 16.54 16.86 10.28 12.18 6.88 8.72
INSGrow 6.54 4.68 5.94 4.68 7.18 4.36 5 3.74 3.12
NETLAP-nonpruning 43.83 53.82 97.34 63.98 59.12 38.53 44.93 22.46 32.76
S7 NETLAP-best 46.64 65.5 113.9 74.9 74.9 51.54 57.7 26.5 45.2
NETGap 49.92 68.6 120.1 78 76.5 51.5 59.2 29.7 45.3
NetBack 43.6 53.1 96.7 62.4 62.4 37.4 44.62 22.78 30.88
INSGrow 18.42 11.54 14.66 12.18 23.72 13.1 15.3 9.98 9.06
NETLAP-nonpruning 80.34 97.82 182.2 113.9 121.7 82.68 94.22 57.25 71.76
S8 NETLAP-best 85.33 101.4 192.1 118.4 130.7 86.31 98.43 59.91 72.86
NETGap 89.39 104.9 200 124.8 135.8 89.08 104.7 62.55 75.51
NetBack 80.18 94.36 182.8 111.2 121.3 81.59 94.38 58.18 71.6
本文的 NetBack 算法采用最左孩子路径的方式寻找出现,为了说明其他 3 种寻径方式的可行性与正确性,
将 NetBack 算法与 NetBack-rrtl 算法(最右孩子路径方式)、NetBack-rltr 算法(最右双亲路径方式)、NetBack-lltr
算法(最左双亲路径方式)进行对比.图 10 给出了 4 种算法在 S1~S5 上的匹配结果总和,表 6 给出了 4 种算法在
S1~S5 上的运行时间.分析结果如下.
(1) 4 种不同寻径方式的算法均为完备算法.通过图 10 可以看到,其他 3 种算法的结果与 NetBack 算法一
致,这验证了本文其他 3 种不同遍历方向的算法均为完备算法.例如,模式 P1 在序列 S1~S5 上,4 种算
法匹配到出现总数均为 127 个,其他模式均有相同现象.
(2) NetBack 算法与 NetBack-rrtl 算法、NetBack-rltr 算法、NetBack-lltr 算法运行时间大致相同,差距较小.
说明这 4 种算法在效率上是一致的.这是因为这 4 种算法都使用了回溯策略和网树结构,只是寻径方
式有所不同.