基于子图的随机图点覆盖2度点核化研究

点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形予图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论:2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对顶点度概率分布为φ(χ)的随机图的参数化点覆盖问题(G,k),当k小于某一与φ(х)有关的值时,它是2-核化可决策的.仿真结果证实,该理论能够把握2度点核化的内在机制,提供随机图上这一NP完全问题的求解方法,也为参数计算在已知度分布的一类不确定问题中的应用提供了可能.     

随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.     

加权3-Set Packing问题的核心化

Packing和Matching问题是一类重要的NP难解问题,该类问题的参数算法和核心化研究受到了人们广泛的关注.主要研究了加权3-SetPacking的核心化算法.对于加权3-SetPacking问题,基于对问题结构的深入分析,提出并证明了2个简化规则.首先限定加权3-SetPacking问题实例中包含给定2个元素的集合的个数,然后在限定问题实例中包含1个给定元素的集合的个数.基于对集合个数的限定,得到问题实例中总的集合个数的上界.并基于上述性质得到2个简化规则,可得到加权3-SetPacking问题大小为27k3-36k2+12k的核,该核心化结果是加权3-SetPacking问题的首个核心化结果.得到的加权3-SetPacking的核心化过程同样适用于加权3D-Matching问题的核化,可得到与加权3-SetPacking问题同样大小的问题核.     

最多叶子生成树问题的核化算法

对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.     

基于核心化技术的点覆盖改进算法

点覆盖是一个著名的NP难解问题，在通信网络和生物信息学等领域具有重要应用。针对点覆盖的研究主要集中在启发式或近似算法，其主要不足是无法实现全局最优。核心化是处理难解问题的一种新方法。提出融合启发式操作和核心化操作的算法框架，利用核心化技术进行点覆盖启发式算法优化。核心化操作挖掘出全局最优的顶点集，而启发式操作改变网络拓扑，使下一轮核心化操作能够继续，两者交叉执行实现解精度优化。实验结果表明，提出的算法在不同网络中均能实现不同程度的优化，在几乎所有稀疏网络实例中获得了最优解。     

P2-Packing问题参数算法的改进

P_2-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O(2~(5.301k))的参数算法,其核的大小为15k.通过对P_2-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O(2~(4.142k))的参数算法,大幅度改进了目前文献中的最好结果.     

P2-Packing问题参数算法的改进

P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.     

参数计算中核心化技术及其应用

在参数计算与复杂性理论中,一个参数问题是固定参数可解的问题当且仅当该问题是可核心化的.核心化技术是参数化算法设计中应用最为广泛、有效的技术,是参数理论中的一个研究热点.通过实例分析对比了最主要的4种核心化技术的基本思想、应用特点和方法,总结了核心化技术在cover类、packing类和cut类等几个重要领域中的应用成果,展望核心化技术的进一步研究方向并加以分析讨论,针对核心化新技术研究和某些热点问题,提出了可能采取的核心优化方法和思路.     

一种基于混合策略的彩色编码算法

彩色编码是求解实际工程中难解问题的一种新兴而重要的技术.在应用该技术时,算法复杂度取决于彩色编码着色方案的规模,因此规模的大小将成为衡量彩色编码算法优劣的标准.彩色编码的研究在最近几年得到了许多有重要意义的结果.基于完全散列函数的PH算法产生的着色方案规模为O*(6.1kn),是目前世界上最好的确定彩色编码结果;彩色编码算法PBCC是一种利用组合思想针对n 2k的有效着色算法.文中以分治算法为基础,结合核心化技术,并利用PBCC算法求解子问题,提出了一种基于混合策略的彩色编码算法HABCC,并且证明了由HABCC算法产生的着色方案确实可以覆盖到所有子集,着色方案规模为|S(n,k)|2k.logkk-1.n.通过与PH算法的比较,说明了HABCC算法具有更小的着色方案规模,对彩色编码技术的实际应用具有重要的意义.     

核扩展判定及核扩展方法

给出一种判定模式识别算法能否核扩展的方法,该方法具有不被算法具体形式所限制的优点.传统核扩展方法是通过将输入数据映射到特征空间,然后在特征空间运行原始算法,得到相应的核方法.给出另外一种核扩展策略,与传统核扩展方法具有等价性.分析及试验过程都表明,本文的核扩展方法具有可行性.