Page 313 - 《软件学报》2025年第7期

3234 软件学报 2025 年第 36 卷第 7 期

16.0 14.0
14.0 12.0
12.0
10.0
DMECV/BWSS 8.0 DMECV/BWSS 8.0
10.0
6.0
6.0
4.0 4.0
2.0 DMECV/BWSS 2.0 DMECV/BWSS
线性 (DMECV/BWSS) 线性 (DMECV/BWSS)
0 0
900 1 100 1 300 1 500 1 700 1 900 2 100 300 500 700 900 1 100 1 300 1 500
n n
(a) m=35, p=0.20 (b) m=30, p=0.25
图 5 BWSS、MHS-DMECV 算法运行时间之比

0.4 0.5 0.25 0.5
Min/Bool
no-MHSs/HSs 0.4 0.20 0.4
Number of no-MHSs/ Number of HSs 0.2 0.3 Minimal time/Bool time Number of no-MHSs/ Number of HSs 0.15 0.3 Minimal time/Bool time
0.3

0.2
0.10
0.2
0.1
0.1
0.05
Min/Bool
no-MHSs/HSs 0.1
0 0 0 0
0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85
p p
(a) m=15, n=200 (b) m=20, n=200
0.35 0.7 0.35 0.8
0.30 0.6 0.30 0.7
Number of no-MHSs/ Number of HSs 0.20 0.4 Minimal time/Bool time Number of no-MHSs/ Number of HSs 0.20 0.5 Minimal time/Bool time
0.6
0.5
0.25
0.25
0.4
0.3
0.15
0.15
0.3
0.10
0.05
0.1
0.05 Min/Bool 0.2 0.10 Min/Bool 0.2
0.1
no-MHSs/HSs no-MHSs/HSs
0 0 0 0
0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85
p p
(c) m=25, n=200 (d) m=30, n=200
0.11 10 0.16 12
0.10 8 0.15 10
Minimal time/Bool time 0.08 6 Number of MHSs and HSs (×10 5 ) Minimal time/Bool time 0.14 8 Number of MHSs and HSs (×10 5 )
0.09
6
0.13
0.07
4
0.12
4
0.06
Min/Bool
MHSs
MHSs
0.05
HSs 2 0.11 Min/Bool 2
HSs
0.04 0 0.10 0
40 50 60 70 80 90 100 40 50 60 70 80 90 100
m m
(e) n=10, p=0.4 (f) n=15, p=0.4
图 6 BWSS 算法解集极小化时间与计算碰集时间之比