基于打分和格局检测的集合K覆盖问题求解算法研究

发布时间：2021-11-16 00:40

　　集合覆盖问题不仅仅是运筹学研究中经典的组合优化问题,也是计算机科学问题中的一个常见问题。作为其扩展问题的集合K覆盖问题,在原问题的基础上,增加了更多的约束,同样也增加了问题的难度。集合K覆盖问题已被证明是一个NP-hard问题且已经很好地应用于日常生活中的工程设计问题,比如网络安全,资源分配,人员调动等。本文在该问题的典型求解算法上提出了一些改进的策略方法。首先是多层打分启发式策略方法（ML）,该策略会对各个子集进行打分。接下来,局部搜索算法会通过子集的分值大小来选择子集加入候选解还是从候选解中移除。另一个改进的策略方法是定量格局检测策略,该策略改进了原有的格局检测策略方法,旨在避免局部搜索算法陷入循环的同时,不仅改善了整个局部搜索路径,跳出局部最优,也提升了解的质量。为了更好的结合多层打分策略和定量格局检测策略,提出了一个有效的子集选择策略方法,并且通过整合上述提出的策略方法形成了一个有效的局部搜索算法,名为MLQCC算法。除此之外,针对集合K覆盖问题的一些特殊情况,提出了一个有效的化简函数来化简集合K覆盖问题的规模,从而在一定程度上降低了算法搜索复杂度。最后一个改进的算法是低复杂度... 

【文章来源】：东北师范大学吉林省 211工程院校 教育部直属院校

【文章页数】：42 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究问题及意义
    1.2 相关工作
    1.3 本文研究内容
    1.4 论文内容安排
第二章 基本局部搜索算法
    2.1 基本概念和定义
    2.2 局部搜索算法求解集合K覆盖问题
        2.2.1 打分策略
        2.2.2 格局检测策略
    2.3 本章小结
第三章 基于多层打分和定量格局检测的局部搜索算法
    3.1 算法框架
    3.2 化简函数
    3.3 生成初始化解函数
    3.4 局部搜索函数
        3.4.1 多层打分启发式
        3.4.2 定量格局检测策略
        3.4.3 子集选择策略
        3.4.4 局部搜索函数
    3.5 大规模例子的初始化函数
    3.6 本章小结
第四章 实验结果与分析
    4.1 实例介绍
    4.2 实验结果
        4.2.1 小规模例子的实验比较
        4.2.2 与LP-MMAS-LS的实验对比
        4.2.3 在大规模例子上的实验结果
        4.2.4 多层打分启发式和定量格局检测策略的有效性
        4.2.5 MLQCC+LI在大规模例子上的实验
第五章 总结与展望
参考文献
致谢



本文编号：3497833