最小顶点覆盖问题是经典的NP难组合优化问题,有着重要的理论恿义和广泛的应用。给定一个无向图,顶点覆盖是指该图的一个顶点子集,使得图中每一条边都至少有一个点属于该集合。而最小顶点覆盖问题就是对一个图找出规模最小的顶点覆盖。最小顶点覆盖问题还有两个等价的问题,即最大团问题和最大独立集问题。这两个问题也是经典的NP难问题,并且也有着广泛应用。这三个问题可以看成是一个问题的不同形式化定义,由于它们的理论意义和应用意义,引起了广泛的兴趣和研究。　　对于这三个问题的现实求解,目前主要有两类算法:精确算法和启发式算法。精确算法可以保证找到最优解,启发式算法不能保证得到最优解,但是能比较快速的给出较好的解。由于组合爆炸的存在,寻找最优解的精确算法所需要的计算时间会随着顶点和边密度的增加呈指数型地增长,无法用于大型问题实例的求解。所以,对于规模较大的问题实例,一般都诉诸于启发式算法,其中最主要是局部搜索算法。本文的工作集中于设计求解最小顶点覆盖问题的高效局部搜索算法。　　本文提出了几个局部搜索策略,并基于这些策略设计了三个高效的局部搜索算法,包括基于部分顶点覆盖和边加权技术的EWLS算法,在EWLS算法基础上利用格局检测策略改进得到的EWCC算法,以及综合了格局检测,两阶段点对交换和带遗忘边加权策略的NuMVC算法。在两个权威的买例组DIMACS和BHOSLIB上的实验说明,这些算法都具有很好的性能。　　本文在MVC局部搜索方面取得了一些不错的成果。目前我们保持着挑战实例frb100-40的最新求解纪录,而我们提出的NuMVC算法在大量权威数据集上比以前的其他最小顶点覆盖算法和最大团算法都有相当大幅度的提高,代表着当前最高效的最小顶点覆盖局部搜索算法,另外,本文提出的格局检测是一个一般化的局部搜索策略,可广泛应用于各种组合问题,已经被成功应用于命题逻辑可满足性(SAT)问题的局部搜索算法。