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