欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
着色算法（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（n，k）｜都不小于（[n/2]n-k）＋[（n n-k）-（[n/2] n-k）2^n-k]／（2^n-k-2）．此外，文中也采用了渐进分析技术，证明了PBCC算法生成着色方案规模为O（e^2Rootof（e^x-e^μx＋1）（n-k）在n=2k的情况下结果是O（2．62^n-k）；同时，文中也证明了n≤2k情况下着色方案规模的下界为2^n-k．
英文摘要：
Color-coding is one of the most important solutions to those problems proved to be NP-Hard. The performance of those color-coding based algorithms principally depends on the scale of the coloring schemes generated by coloring algorithms they deploy. Therefore, the ultimate objective of coloring algorithm is to provide a coloring scheme as small as possible. All existing coloring algorithms are mainly based on perfect hash functions, requiring of the number of elements n far greater than the number of colors k, and k relatively small. This paper mainly focuses on the study of effective algorithms under the circumstance where the size of element set and color set are close （n≤2k） and the analysis of performance of coloring algorithm while n≤2k. This paper proposes a novel partition based algorithm PBCC, and proves that the coloring scheme generated by PBCC can cover all the subsets. A detailed method for constructing a （20, 16）-coloring scheme with size 403 which can be applied for （l,d）-（20,16） motif finding problem is also provided. Furthermore, this paper analyzes the scale of coloring schemes generated by PB- CC, and proves that while n≤2k and n=k≥2, no algorithm can create a coloring scheme with its size ｜S（n,k）｜ less than （[n/2]n-k）＋[（n n-k）-（[n/2] n-k）2^n-k]/（2^n-k-2） At last, using asymptotic analysis, it is proved that coloring scheme generated by PBCC is of size O（e^2Rootof（e^x-e^μx＋1）（n-k）, and it is 0（2.62^n-k） when n=2k. Also, it is showen that any coloring scheme with n≤2k will be larger than 2n-k.
同期刊论文项目
同项目期刊论文
Significant linkage and association between a functional (GT)n polymorphism in promoter of the N-met
A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments an
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartit
A modified particle swarm optimization-based dynamic recurrent neural network for identifying and co
期刊信息
位置：