顶点覆盖问题的求解算法研究

丛 书 名：吉林财经大学资助出版图书

版本说明：1版

作     者：李睿智 

I S B N：(纸本) 9787030724069 

出 版 社：科学出版社 

出 版 年：2022年

页      数：122页页

主 题 词：计算机算法 研究 

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

馆 藏 号：201106029...

摘      要：顶点覆盖问题是经典的组合优化问题，在交通规划、设施选址等多个领域有着重要的应用。其关键性子问题如小加权顶点覆盖问题、泛化顶点覆盖问题和小分区顶点覆盖问题有着广泛的应用领域。在实际应用中，顶点覆盖子问题所需要处理的问题规模往往较大，使用求解方法很难进行有效求解。因此，本书对小加权顶点覆盖问题、泛化顶点覆盖问题和小分区顶点覆盖问题的高效启发式搜索算法进行研究。针对小加权顶点覆盖问题，提出约简规则和自适应顶点删除策略的局部搜索算法；针对泛化顶点覆盖问题，提出基于进化搜索和迭代邻域搜索的模因算法；针对小分区顶点覆盖问题，提出模拟退火算法和随机局部搜索算法。并且，在各自的标准实例上对所提出算法的有效性和高效性进行测试。