基于粗糙集的无向图最小支配集启发式算法

• 作者: 王洪 官礼和
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 最小支配集 粗糙集 属性约简 启发式算法 图论
• 年，卷（期）: 2021,（z2）
• 所属期刊栏目: 先进计算|Advanced computing
• 页码范围: 169-176
• 页数: 8页
• 分类号: TP18
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2021020341

摘要

图的最小支配集在许多领域有广泛应用,但其求解是一个NP问题.针对现有近似求解算法的复杂度和精度有待改进的问题,基于粗糙集理论提出一种低复杂度、高精度的最小支配集启发式求解算法.首先,利用图的邻接矩阵构造诱导决策表,证明了图的最小支配集与其诱导决策表的最小属性约简等价.然后,提出一种启发式的最小支配集近似算法.该方法采用前向和后向搜索机制,有效提高了最小支配集求解的近似精度;采用累积策略计算诱导决策表的正域,有效降低了计算复杂度.最后,在公用数据集上与典型算法进行了实验对比分析,结果表明该算法在运行效率方面具有明显优势,能得到更高精度的近似最小支配集,且输出结果具有较好的稳定性.