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