| 基于粗糙集的无向图最小支配集启发式算法 |
| |
| 引用本文： | 王洪,官礼和.基于粗糙集的无向图最小支配集启发式算法[J].计算机应用,2021,41(z2):169-176. |
| |
| 作者姓名： | 王洪 官礼和 |
| |
| 作者单位： | 重庆交通大学数学与统计学院,重庆 400074 |
| |
| 摘 要： | 图的最小支配集在许多领域有广泛应用,但其求解是一个NP问题.针对现有近似求解算法的复杂度和精度有待改进的问题,基于粗糙集理论提出一种低复杂度、高精度的最小支配集启发式求解算法.首先,利用图的邻接矩阵构造诱导决策表,证明了图的最小支配集与其诱导决策表的最小属性约简等价.然后,提出一种启发式的最小支配集近似算法.该方法采用前向和后向搜索机制,有效提高了最小支配集求解的近似精度;采用累积策略计算诱导决策表的正域,有效降低了计算复杂度.最后,在公用数据集上与典型算法进行了实验对比分析,结果表明该算法在运行效率方面具有明显优势,能得到更高精度的近似最小支配集,且输出结果具有较好的稳定性.
|
| 关 键 词： | 最小支配集 粗糙集 属性约简 启发式算法 图论 |
Heuristic algorithm of minimum dominating set for undirected graphs based on rough set |
| |
| WANG Hong,GUAN Lihe.Heuristic algorithm of minimum dominating set for undirected graphs based on rough set[J].journal of Computer Applications,2021,41(z2):169-176. |
| |
| Authors: | WANG Hong GUAN Lihe |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
