中文摘要：

为了有效解决最小碰集问题，基于分支约减技术提出了一个相对简单的递归算法。同时使用新近提出的一种称为度量与分治的方法，通过对问题实例规模进行加权，建立非标准的度量，对算法进行了分析，并与标准的分析方法做了比较。在分析过程中，为了优化权值以获得更好的算法时间复杂度，使用了一种成功应用于回溯算法分析的数学规划方法——拟凸规划，对建立的问题实例规模新度量中的权值进行了优化，最终证明了该算法可以在使用多项式空间情况下，在O（1．23801^n）时间内解决最小碰集问题。

英文摘要：

To solve the minimum hitting set problem, a relatively simple recursive algorithm based on the branch and reduce technology is proposed. A recently developed method called measure and conquer is used in the algorithm analysis. By weighting the different aspects of the problem instance, a non-standard measure is built to do the analysis comparing with the standard analysis of such algorithms. At the end of this process, another new technology named quasiconvex programming, a mathematical programming approach which is successfully used for the analysis of backtracking algorithm, is applied to improve the weights in the newly built measure of the problem instance, finally the algorithm proved to solve the minimum hitting set problem in O （1.23801^n） and polynomial space.