论文部分内容阅读
FPT-算法(Fixed-Parameter-Tractable Algorithms)被认为是当前比较流行的运用于解决许多NP完全问题的较为有效的算法,许多FPT-算法是通过两个步骤来对问题进行求解:首先,把实例转化为一个较小的等价体,具体来说,其大小由只依赖于参数的一个函数所限制。这一步称为化简问题核心。其次,通过用一些更小的参数解决一些导出子例,把简化了的问题用递归的方式来解决。因为在递归调用中的那些参数更小,所以递归最终能完成(要么找到一个解,要么了解到由于k≤0而没有解存在)。这一步称为限定搜索树。 顶点覆盖问题是一个公认的NP完全问题,对它的解决将具有十分广阔的应用前景,特别是对于受二分图约束的顶点覆盖(CBVC)问题在超大规模集成电路芯片的修复上的运用已相当成熟。但随着芯片集成度的提高,对顶点覆盖的算法无论在精确度上还是运行时间上都提出更高的要求。而把固定参数算法与受约束的二分图顶点覆盖问题相结合起来的算法能适应这种要求。 本文通过用把匹配理论的经典理论运用到参数理论与二分图顶点覆盖问题的结合中,得到时间复杂度只需要O(1.26~k+nk)[8]的优良结果的算法的一个实例来证明参数理论在解决NP-完全问题时的有效性,并得出一个结论:参数复杂性算法虽然好用,但也不是放之四海而皆准的算法,只有把FPT-算法充分与具体实际问题相结合才能产生出更为优越的结果,这是立足于对具体问题的深入理解和掌握的基础上的,对具体问题理解越透彻,得到的结果也会更优异。此外,通过对这一实例的具体分析,也希望更多的人能注意到它的优良特性,更多的人把参数复杂性理论运用到更多的领域。