最小碰集问题的精确快速算法  

Exact fast algorithm for minimum hitting set

作　　者：石磊[1] 蔡烜[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200240

出　　处：《计算机工程与设计》2010年第19期4225-4227,4264,共4页Computer Engineering and Design

基　　金：国家973重点基础研究发展计划基金项目(2003CB317005);国家自然科学基金项目(60703033)

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

关 键 词：精确算法 最小碰集 度量与分治 拟凸规划 算法分析 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]