一种在元素与颜色规模相近时的有效着色算法及其应用

摘要

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