赋权图点覆盖问题的蚁群算法求解

摘要

点覆盖问题为组合优化中一个经典的NP完全问题。目前,该问题在有效的多项式时间内无法找到最优解。文章针对蚁群算法可能出现的早期停滞问题进行改进,通过对信息素浓度进行限定,信息素浓度不会在好的顶点继续加强,也不会忽略掉潜在的一些搜索区域。该算法有效地避免了局部最优,提高了算法的准确度,得到时间复杂性为0[(n-1)2-n]的解决方案。