顶点覆盖是最经典的组合优化问题之一,在无线网络设计中有广泛应用。所谓连通点覆盖,是在顶点覆盖的基础上增加了生成子图的连通性要求。最小连通点覆盖问题仍然是APX-难的。本文研究正则图上的最小连通点覆盖问题,该问题已被证明即使在4-正则图上也是NP-难的。本文一方面对已有算法的最坏情况界进行了改进分析,另一方面利用局部搜索方法设计了新的近似算法,并通过Python编程实现算法、进行算例比较。全文共分为四章。第一章简要介绍了图论的基本概念、组合优化问题、计算复杂性理论以及近似算法的相关定义并介绍了最小顶点覆盖问题和最小连通点覆盖问题的综述,综述了两个问题在一般图、典型特殊图上的国内外研究情况,包括计算复杂性、精确算法、固定参数算法以及近似算法的结果等。第二章着重考虑了 4-正则和5-正则图上的连通点覆盖问题。对基于贪婪思想设计的一个已有的近似算法进行了最坏情况分析,得到了改进的最坏情况界,它们在4-正则和5-正则图上分别是4/3和10/7,并给出了算法下界的实例。第三章首先在贪婪思想的基础上,增加了局部搜索过程,设计了k-正则图上最小连通点覆盖问题的局部搜索算法。接着通过Python编程实现贪婪算法和局部搜索算法,并通过算例评估了算法的性能。第四章总结全文并给出后续研究方向。