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

武优西 等:无重叠条件严格模式匹配的高效求解算法 3345

运行时间相差较小,但 NETLAP-Nonpruning 算法不能得到问题的完备解.

S1 S2
300 300
250 250
出 200 出 200
现 150 现 150
数 100 数 100
50 50
0 0
P1 P2 P3 P4 P5 P6 P7 P8 P9 P1 P2 P3 P4 P5 P6 P7 P8 P9
INSGrow 15 59 80 43 141 142 81 69 118 INSGrow 10 72 92 52 154 152 89 61 138
NETLAP-Nonpruning 33 113 151 100 252 212 126 88 155 NETLAP-Nonpruning 19 131 171 117 253 212 149 84 180
NETLAP-Best 33 126 203 113 270 228 138 95 163 NETLAP-Best 19 142 228 133 270 233 164 91 188
NETGap 33 126 203 113 270 228 138 95 163 NETGap 19 142 228 133 270 233 164 91 188
NetBack 33 126 203 113 270 228 138 95 163 NetBack 19 142 228 133 270 233 164 91 188

S3 S4
300 250
250 200
出 200 出 150
现 150 现 100
数 100 数
50 50
0 0
P1 P2 P3 P4 P5 P6 P7 P8 P9 P1 P2 P3 P4 P5 P6 P7 P8 P9
INSGrow 9 59 82 47 145 149 91 45 127 INSGrow 13 51 65 43 119 118 83 43 102
NETLAP-Nonpruning 20 111 162 101 250 220 140 68 178 NETLAP-Nonpruning 29 93 136 80 190 171 121 55 135
NETLAP-Best 20 130 221 124 272 235 158 71 181 NETLAP-Best 29 108 178 101 205 184 132 57 139
NETGap 20 130 221 124 272 235 158 71 181 NETGap 29 108 178 101 205 184 132 57 139
NetBack 20 130 221 124 272 235 158 71 181 NetBack 29 108 178 101 205 184 132 57 139

S5 S6

200 200
180 180
160
160
出 140 出 140
120
120
现 100 现 100
80
80
数 60 数 60
40
40
20 20
0 0
P1 P2 P3 P4 P5 P6 P7 P8 P9 P1 P2 P3 P4 P5 P6 P7 P8 P9
INSGrow 6 41 52 29 99 100 59 41 79 INSGrow 5 34 48 28 98 96 62 31 82
NETLAP-Nonpruning 26 74 104 66 163 143 97 55 113 NETLAP-Nonpruning 19 68 105 62 166 136 95 46 113
NETLAP-Best 26 91 138 85 179 155 107 59 120 NETLAP-Best 19 79 135 72 173 146 102 49 121
NETGap 26 91 138 85 179 155 107 59 120 NETGap 19 79 135 72 173 146 102 49 121
NetBack 26 91 138 85 179 155 107 59 120 NetBack 19 79 135 72 173 146 102 49 121

S7 S8
600 1200
500 1000
出 400 出 800
现 300 现 600
数 200 数 400
100 200
0 0
P1 P2 P3 P4 P5 P6 P7 P8 P9 P1 P2 P3 P4 P5 P6 P7 P8 P9
INSGrow 42 112 168 94 269 271 158 70 244 INSGrow 68 186 238 133 559 568 344 205 491
NETLAP-Nonpruning 152 222 343 203 434 372 255 103 344 NETLAP-Nonpruning 194 387 607 343 948 830 551 282 667
NETLAP-Best 152 240 409 217 478 414 279 107 362 NETLAP-Best 194 422 752 382 1008 892 613 307 701
NETGap 152 240 409 217 478 414 279 107 362 NETGap 194 422 752 382 1008 892 613 307 701
NetBack 152 240 409 217 478 414 279 107 362 NetBack 194 422 752 382 1008 892 613 307 701

Fig.9 Comparison of results on sequences S1~S8
图 9 在序列 S1~S8 上结果的比较