Page 244 - 《软件学报》2025年第8期

李睿智 等: 局部搜索算法求解最小弱连通支配集问题 3667

表 3 在 一般 UDG 实例上的实验结果

CPLEX MWCDS MA GRASP GRASP_impLS FPLS
Nodes R |E|
Solu Stat Best Avg Time Best Avg Best Avg Best Avg Best Avg
60 262 N/A N/A 18 20.1 <0.01 13 13.0 13 13.0 13 13.0 13 13.0
70 329 N/A N/A 16 17.9 <0.01 11 11.0 11 11.0 11 11.0 11 11.0
80 400 N/A N/A 13 15.7 <0.01 8 8.0 8 8.0 8 8.0 8 8.0
80
90 474 N/A N/A 11 12.5 <0.01 8 8.0 8 8.0 8 8.0 8 8.0
(N=400)
100 563 N/A N/A 9 11.1 <0.01 7 7.0 7 7.0 7 7.0 7 7.0
110 647 N/A N/A 8 9.6 <0.01 6 6.0 6 6.0 6 6.0 6 6.0
120 735 N/A N/A 8 9.2 <0.01 5 5.0 5 5.0 5 5.0 5 5.0
80 335 N/A N/A 21 23.5 <0.01 15 15.0 15 15.6 15 15.0 15 15.0
90 368 N/A N/A 21 22.5 <0.01 14 14.0 15 15.0 14 14.0 14 14.0
100
(N=600) 100 435 N/A N/A 18 20.0 <0.01 12 12.0 12 12.0 12 12.0 12 12.0
110 500 N/A N/A 17 18.5 <0.01 11 11.0 11 11.0 11 11.0 11 11.0
120 575 N/A N/A 14 16.3 <0.01 10 10.0 10 10.0 10 10.0 10 10.0
70 756 N/A N/A 43 47.3 <0.01 29 29.0 30 30.6 28 28.4 28 28.0
80 921 N/A N/A 37 39.0 <0.01 24 24.8 26 26.0 24 24.0 24 24.0
200 90 1 113 N/A N/A 29 32.7 <0.01 20 20.0 21 21.0 20 20.0 20 20.0
(N=700) 100 1 305 N/A N/A 27 28.6 <0.01 18 18.0 19 19.0 18 18.0 18 18.0
110 1 501 N/A N/A 23 25.3 <0.01 16 16.0 16 16.3 16 16.0 16 16.0
120 1 730 N/A N/A 20 22.5 <0.01 13 13.8 14 14.0 13 13.3 13 13.0
100 756 N/A N/A 43 47.3 <0.01 29 29.0 30 30.6 28 28.4 28 28.0
110 871 N/A N/A 40 42.5 <0.01 26 26.0 27 27.0 25 25.0 25 25.0
120 997 N/A N/A 32 36.2 <0.01 23 23.0 24 24.0 23 23.0 23 23.0
200
130 1 127 N/A N/A 29 32.9 <0.01 20 20.0 21 21.0 20 20.0 20 20.0
(N=1000)
140 1 269 N/A N/A 28 29.7 <0.01 18 18.0 19 19.0 18 18.0 18 18.0
150 1 400 N/A N/A 26 27.6 <0.01 16 16.2 17 17.5 16 16.0 16 16.0
160 1 541 N/A N/A 23 24.8 <0.01 15 15.0 16 16.0 15 15.0 15 15.0
130 903 N/A N/A 57 60.7 <0.01 37 37.8 39 39.3 37 37.0 36 36.0
250 140 1 011 N/A N/A 52 54.1 <0.01 34 34.8 36 36.7 34 34.0 33 33.0
(N=1500) 150 1 119 N/A N/A 44 49.2 <0.01 31 31.5 33 33.2 31 31.0 30 30.0
160 1 246 N/A N/A 44 45.4 <0.01 29 29.0 30 30.5 28 28.0 28 28.0
200 1 577 N/A N/A 50 53.5 <0.01 32 32.8 34 34.7 32 32.0 31 31.0
300 210 1 710 N/A N/A 48 50.4 <0.01 30 30.8 32 32.3 30 30.0 29 29.0
(N=2000) 220 1 849 N/A N/A 46 47.0 <0.01 28 28.5 29 29.9 27 27.3 27 27.0
230 1 990 N/A N/A 41 43.7 <0.01 26 26.5 28 28.0 26 26.0 25 25.6
200 1 461 N/A N/A 72 76.7 <0.01 49 49.8 51 51.8 46 46.3 45 45.0
350 210 1 555 N/A N/A 69 73.2 <0.01 44 45.5 48 48.3 43 43.7 42 42.0
(N=2500) 220 1 668 N/A N/A 65 69.1 <0.01 42 42.8 46 46.0 40 40.0 39 39.0
230 1 787 N/A N/A 60 64.4 <0.01 40 40.8 43 43.3 39 39.0 38 38.0
210 1 522 N/A N/A 90 94.4 <0.01 61 62.0 62 63.5 57 57.6 55 55.0
400 220 1 621 N/A N/A 84 88.6 <0.01 59 59.2 61 61.2 55 55.1 53 53.0
(N=3000) 230 1 750 N/A N/A 79 85.0 <0.01 54 55.2 56 57.0 51 51.7 50 50.0
240 1 880 N/A N/A 77 80.1 <0.01 51 51.2 53 53.5 47 48.6 46 46.2
最小值 － － 8 9.2 0.00 5 5.0 5 5.0 5 5.0 5 5.0
最大值 － － 90 94.4 0.00 61 62.0 62 63.5 57 57.6 55 55.0
平均值 － － 37.85 40.71 0.00 25.22 25.54 26.39 26.65 24.56 24.69 24.17 24.19
标准差 － － 22.67 23.57 0.00 15.15 15.44 15.94 16.17 14.14 14.32 13.47 13.48
注: 加粗数值是对应算法找到的最优值