| 文章摘要 | 摘要 着色算法(color-coding)是求解NP难问题的重要手段之一.而在应用着色算法时，着色算法所产生的着色方案的规模极大地影响着问题的求解性能，故构造一个尽可能小的着色方案是着色算法所寻求的目标.目前存在的着色算法均基于完全散列函数，并要求元素数目n远大于颜色数目k，且k比较小，这个限制条件使得这些着色算法在一些实际情况下无法应用.该文主要研究在元素与颜色规模相近时(n2k)的有效着色算法，并着重分析在n2k情况下着色算法的性能.该文提出了一种基于划分思想的着色方案构造算法PBCC，证明了由PBCC产生的着色方案确实可以覆盖到所有的子集，并具体给出了可应用于(l,d)-(20,16) Motif查找问题的403种着色的构造方法.文章进一步分析了PBCC产生的着色方案规模，并证明了在n2k且n-k2的情况下，任何着色算法所产生的着色方案的规模｜S(n,k)｜都不小于[n/2]n-k+nn-k-[n/2]n-k2n-k/(2n-k-2).此外，文中也采用了渐进分析技术，证明了PBCC算法生成着色方案规模为O(e2Rootof(ex-eμx+1)(n-k))，在n=2k的情况下结果是O(2.62n-k)；同时，文中也证明了n2k情况下着色方案规模的下界为2n-k.
关键词：着色；着色算法；NP难问题；渐进分析；界限分析 |