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

3656 软件学报 2025 年第 36 卷第 8 期

Key words: minimum weakly connected dominating set problem; combinatorial optimization; local search; feedback mechanism; perturbation
strategy; age property

1 引 言

给定一个无向连通图 G(V, E), 其中 V 表示图 G 的顶点集, E 表示图 G 的边集. 若存在一个顶点子集 D ⊆ V, 使
得 V 中的每一个顶点都在 D 中或者至少与 D 中的一个顶点相邻, 那么称集合 D 为支配集 (dominating set, DS). 若
集合 D 是一个支配集, 并且该集合的诱导子图是连通的, 那么称集合 D 为连通支配集 (connected dominating
set, CDS), 其中 D 的诱导子图定义为 IS G (D) = (D, E ∩ (D × D)). 若集合 D 是一个支配集, 且 D 的弱诱导子图是连
通的, 那么称集合 D 为弱连通支配集 (weakly connected dominating set, WCDS), 其中 D 的弱诱导子图定义为
WIS G (D) = (N[D], E ∩ (D × N[D])), 其中 N[D] 包含集合 D 及 D 中顶点的邻居. 最小弱连通支配集问题 (minimum
weakly connected dominating set problem, MWCDSP) 是在图 G 上找到一个具有最小顶点规模的弱连通支配集.
最小弱连通支配集问题是一个经典的 NP 难问题, 最早是由 Dunbar 等人 [1] 提出, 在分布式传感器网络 [2] , 离散
时间线性 2 次调节 [3] , 计算最优网络安全投资问题 [4] , 电力系统安全 [5] 和自然语言处理 [6] 等多个领域得到广泛应
用. 在一个无向网络中, 节点之间可以通过全向天线进行通信. 然而, 由于每个节点的通信半径有限, 因此需要中继
节点来实现信息传播, 从而引入了最小连通支配集问题和最小弱连通支配集问题的研究. 然而, 弱连通支配集在集
群形成 [7] 中具有显著的潜力, 可用于减少网络中的集群头数量, 有效解决了分布式传感器网络 [2] 中关键的安全集
群问题. 同时, 寻找一个最小弱连通支配集意味着确定一组最少数量的节点作为数据转发的中继点, 这样所有节点
都能够通过这些中继节点实现信息的全网覆盖, 即使并非所有节点都直接相连. 这样的解决方案有助于减少所需
的通信资源, 降低能耗, 同时保证网络的整体连通性和稳定性. 此外, 除了一般图的 NP 难度计算挑战之外, 许多研
究还专注于特定类型图 [8−10] 的最小弱连通支配集问题计算复杂性. 这些研究进一步表明了研究最小弱连通支配集
问题的理论意义, 且该问题更为灵活且具有挑战性, 因此本文对该问题进行了深入的研究.
目前, 已有许多学者对最小弱连通支配集问题进行了研究并设计了多种求解算法, 这些算法主要分为两类, 一
类是近似算法, 一类是启发式算法. 对于近似算法, Chen 等人 [11] 提出了一种分布式逼近算法, 用于在无线自组网中
进行聚类. 该算法通过寻找接近最优解的最小弱连通支配集问题的解来实现. Devdatt 等人 [12] 提出了一种在分布式
网络中具有良好的“低拉伸”特性的快速分布式算法. Ding 等人 [13] 提出了一种针对最小弱连通支配集的线性时间
自稳定算法 (MWCDS), 该算法可以快速构造最小弱连通支配集. Torkestani 等人 [14] 首先给出了随机图中弱连通支
配集问题的定义, 接着提出了几种基于自动学习的算法, 用于解决顶点相关权重的概率分布函数未知的随机最小
弱连通支配集问题. 但对于通常包含许多局部最优解的复杂图, 仍难以应用于求解最小弱连通支配集问题. 然而,
近似算法并不能保证解的质量, 而且通常得到的解与最优解有很大的差异. 因此, 一些学者致力于启发式搜索算法
的研究, 该类算法能够在合理的时间内给出更高质量的解.
Niu 等人 [15] 提出了一种针对最小弱连通支配集问题的自稳定模因算法 (MA). 该算法首先构造若干个初始解,
然后随机选择两个解, 将其作为一对染色体序列, 然后对该对染色体序列进行交叉和突变操作, 接着将得到的新的
染色体序列通过简单的局部搜索来对其进一步优化. 随后, 针对该问题, Niu 等人 [16] 提出了一种贪婪的随机自适应
搜索算法 (GRASP). 该算法采用平衡贪婪和随机策略求出初始解, 然后通过简单的局部搜索对该初始解进行优化.
此外, Niu 等人 [16] 对 GRASP 进行了改进, 提出了 GRASP_impLS 算法, 以获得一个更小的弱连通支配集. 在局部搜
索阶段, 引入了一个新的贪婪函数和一个参数. 贪婪函数增强了顶点选择的多样性, 参数控制使用顶点去除方法的
概率. 这些改进显著地提高了 GRASP_impLS 算法解决该问题的效率.
然而, 许多学者更倾向于针对最小支配集问题或其变体设计启发式算法 [17,18] 和精确算法 [19,20] , 而关于最小弱
连通支配集问题的启发式算法研究仍处于起步阶段. 尽管对于小规模实例, 目前求解效果最好的启发式算法
(GRASP_impLS) 可以得到较好的解, 但对于大规模和复杂的实例来说, 仍有很大的改进空间. 其中一个可能的原
因是, 在寻找最优解的过程中, 很难保证不会出现同一顶点被多次选择的情况, 导致当前候选解陷入局部最优. 因