最小顶点覆盖问题（MVC）是组合优化领域的一类常见问题,在这类问题中,部分顶点覆盖问题（PVC）是其中一个热门研究方向。我们生活中很多问题都可以转化为PVC问题,比如监控设备安装问题、高校教师排课系统、网络优化问题、线路规划问题等。PVC问题属于NP难问题,也就是说随着数据规模的增大,问题的求解时间往往呈指数级增长,这种情况下要求出问题的精确解所需要的时间开销是难以忍受的,因此近似算法成为解决PVC问题最合适的方案。本文提出了两种近似算法来求解PVC问题:一种是贪心随机自适应算法（GRASP-PVC算法）,另一种是模因进化算法（MAPVC算法）。GRASP-PVC算法是一种以局部搜索为核心的启发式算法,它的特征之一是采用贪心与随机相结合的方法构造初始解,这一做法提高了初始种群的优越性,使得算法能够更快地达到收敛状态。此外,我们还引入了最小代价策略,用来提高局部搜索的运行效率。MAPVC算法是一种基于进化思想的启发式算法,与普通进化算法的“选择—交叉—变异”框架相比,它在策略上有三处改进:一是引入了主干交叉操作,二是利用自适应变异代替了固定节点变异,三是在局部搜索阶段提出了基于DNA层的选点机制。为验证算法的有效性,本文将GRASP-PVC算法、MAPVC算法以及其他先进算法置于相同的实验环境下进行了对比测试。实验结果表明,在绝大多数情况下,GRASP-PVC算法、MAPVC算法展现出了优于其他算法的优越性能,表明本文所提出的这两种算法均具有较高的应用价值。此外,关于相关策略的有效性实验也证明了本文提出的若干策略对提高算法的整体性能有着重大意义。