计算机基础理论的研究，特别是对计算复杂性和基本算法的研究，是发展应用理论和高性能软件系统的基础。找到NP完全问题的快速算法是计算复杂性研究的主要研究方向，顶点覆盖问题(Vertex Cover Problem)是NP完全问题中应用较广的一个典型问题。它在超大规模集成电路(VLSI)的生产、设计；网络流量监测点的选择；生物化学中基因对的配对；交通信息管理系统等领域中都有广泛的应用。顶点覆盖问题是一个组合优化问题，传统算法并不能满足求解问题的需要。元启发式算法的引入使得求解有了新的发展，本文我们利用遗传算法和蚁群优化算法对问题进行研究和试验。 在使用基本遗传算法进行搜索时，存在着局部搜索能力较弱的不足，本文提出了一种新的求解最小顶点覆盖问题的混合遗传算法，将基本遗传算法与局部优化策略相结合，改善遗传算法的局部搜索能力，加快求解该问题的速度，同时采用了双重惩罚的方法，设计两种不同的惩罚项，一个惩罚力度较小，另一个较大，以实现惩罚力度的稳健性。对几种典型无向图的实验证实了新方法的有效性，其整体性能优于现有的一些顶点覆盖问题遗传算法。蚁群优化算法是一种适宜于解决离散组合优化问题的算法。为更好的求解顶点覆盖问题，我们利用4个筛选规则，将部分顶点标识为不可访问，以加速算法的搜索；在全局信息素更新时，为减缓蚁群的收敛速度，对满足限定条件的顶点减少其信息素的增长量。为进一步提高解的质量，我们针对图的顶点覆盖问题的一些特性，提出了局部搜索算法，把局部搜索算法和生成初始解的机制相结合，进一步优化了蚂蚁构建的路径。通过几个典型的实例图和基准测试，验证了算法的有效性。对比ACS，在相同的运算时间内，改进之后的算法在解的质量上有较明显的改进。与遗传算法相比，蚁群算法求解顶点覆盖问题具有更好的性能。 为了进一步证明改进算法的实用性和有效性，将改进的蚁群优化算法应用于网络流量有效监测点选择。本文研究了有效监测点选择的弱顶点覆盖模型，并将其推广到求解顶点加权情况下的弱顶点覆盖问题，通过仿真实验将改进算法与已有算法进行了性能比较。实验结果表明，改进算法的求解质量较高。