集合覆盖是一个重要的组合优化问题,被广泛应用于人工智能不同的领域。近年来,其关键性子问题研究主要集中在经典最小集合覆盖问题、最小加权集合覆盖问题、极小集合覆盖问题和最大集合K覆盖问题,它们具有非常重要的研究意义和广泛的应用领域。本文将围绕上述四个集合覆盖子问题展开,旨在为不同应用需求子问题设计对应的高效求解方法。针对集合覆盖子问题,求解方法主要分成两大类:精确求解方法和启发式求解方法。使用精确求解方法解决时,可以保证得到的候选解是最优解。但随着求解问题规模不断扩大,精确求解方法的求解时间呈指数上升,此时无法保证在可接受的时间内返回一个候选解。启发式方法在合理的求解时间内能够获得一个尽可能好的候选解,但是不能保证这个候选解是最优解。因此,启发式方法适用于大规模问题以及对解的质量要求不过于苛刻的情况。在实际应用中,经典最小集合覆盖问题,最小加权集合覆盖问题和最大集合K覆盖问题所需要处理的问题规模往往较大,此时使用精确求解方法很难进行有效求解。针对这三个问题,本文针对其分别提出启发式求解方法:针对经典最小集合覆盖问题,本文提出一种迭代局部搜索求解方法,该方法使用三个策略:超图边配置检测策略、权值变化策略和超图边选择策略;针对最小加权集合覆盖问题,本文提出一种新的局部搜索框架并辅以带有问题化简的预处理、低复杂度的初始化策略和多值随机选择策略;针对最大集合K覆盖问题,本文提出一种重启局部搜索方法,该方法使用了随机重启初始化和快速邻居搜索两个策略。由于极小集合覆盖问题对解的质量要求较高,而启发式求解方法得到的候选解精度较低。针对此问题,本文提出一种精确极小集合覆盖求解方法,该方法将极小集合覆盖问题转化为约束可满足问题,然后再进行求解。具体工作如下:1)对于经典最小集合覆盖问题,提出一种基于迭代局部搜索的uSLC方法。该方法使用超图形式表示经典最小集合覆盖问题,辅以三个策略对问题求解效率进行提高:超图边配置检测策略、权值变化策略和超图边选择策略。其中,超图配置检测策略阻止uSLC方法陷入局部最优,且避免局部搜索中循环问题的发生;权值变化策略用于改变被当前候选解覆盖和未覆盖超图顶点的权值,目的是增加uslc方法得到候选解的多样性;超图边选择策略结合上述两个策略,进而更加有效地发现质量更高的候选解。在传统测试用例上的实验结果表明:uslc方法求解性能在大多数情况下明显好于其他方法。当uslc方法和其他方法求得最优解的质量相同时,uslc方法的求解效率相比其他方法快了1到2个数量级。同时,对于其中11个传统测试用例,uslc方法得到了质量更高的最优解。2)针对最小加权集合覆盖问题,提出一种基于新局部搜索框架的wscls求解方法。同时,设计三个策略进一步提高wscls求解方法的效率:带有问题化简的预处理、低复杂度的初始化策略和多值随机选择策略。带有问题化简的预处理可以化简大规模的测试问题,进而缩减搜索空间;使用低复杂度的初始化策略可以在更短的时间内得到一个较好的初始解;在删除子集过程中,使用多值随机选择策略可以更快更好地找到需要删除的子集。实验结果表明wscls求解方法在大规模测试问题上得到解的质量好于其它的求解方法。3)针对极小集合覆盖问题(也可以称作极小碰集问题),给出利用csp求解器求解极小碰集的csp-mhs方法。该方法首先用约束可满足问题的描述形式对极小碰集问题进行表示,然后再调用csp求解器对问题进行求解。csp-mhs方法属于精确求解方法,因此可以保证返回候选解的完备性。同时,本文还提出hard-冲突集和soft-冲突集概念,提高求解方法对于带有特定特征极小碰集问题的求解效率。实验结果表明,对比目前最好的方法,csp-mhs方法的求解时间更短。4)针对最大集合k覆盖问题,提出一种重启局部搜索rnkc方法,该方法同时使用一种改进的随机重启策略和一种改进的邻域搜索策略。在初始化过程中,rnkc方法利用一个随机重启策略处理局部搜索方法中的循环问题同时保证初始候选解的多样性;在构造候选解的过程中,rnkc方法使用一个邻域搜索策略探索所有邻域,目的是尽可能多地发现可行候选解,进一步提高候选解的质量。rnkc方法和目前求解效率较高的cplex求解器(ibm公司)在大量经典测试用例上的实验结果表明,rnkc方法在求解效率和所得最优解质量上均占优势。同时对于部分用例,rnkc方法可以在更短时间内发现更好的最优解。