一类NP—完全问题在阈图上的解

本文给出了判定阈图是否为哈密顿图的多项式时间算法,并证明了阈图上STEINER树问题是NP-完全的,给出解答它的多项式时间近似算法。     

新型专家系统设计

分析了单纯用产生式规则与单纯用人工神经网络设计专家系统各自的优缺点，指出同时使用产生式规则与人工神经网络来设计专家系统，能使专家系统应用到更广泛的领域中，并提出了三种设计方案，讨论了实现的可行性。     

实例序列条数为常数9的翻转距离星树问题

讨论翻转距离星树问题，证明实例中有向符号序列个数为9时，翻转距离星树问题是NP-难解问题，并给出了一个该问题的多项式时间近似算法．     

目标序列部分确定的翻转距离星树问题

讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时,若目标序列符号顺序固定,且有部分符号方向给定,则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP-难解问题.同时,还给出了该问题的多项式时间近似算法.     

计算生物学中有关基因组翻转距离的NPC问题

1 基因组翻转距离问题的提出 20世纪80年代末,Jeffrey Palmer及其同事在对比甘蓝与芜箐甘蓝的基因序列时发现,排列形成两种基因序列的分子几乎完全相同,只是这些分子在两种基因中的排列顺序不一样。这一发现以及其后的研究表明,基因重组是生物演化过程中的一个基本特征。基因重组研究中多次遇到要用尽可能少的次数将一条基因序列中的片断翻转连接成新的基因的问题,这就是后来由D.Sankoff等提出的基因组翻转距离问题,或抽象为有向符号序列的翻转距离问题,D.Sankoff等猜测该问题是NP难解问题,然而他们没能给出证明。     

随机算法的一般性原理

最近十几年来,国际上对随机算法(randomized algo-rithm)的研究有了巨大进展。在此期间,随机算法从一个计数理论的工具发展到今天在许多类型的算法中都得到了广泛应用,显示了随机算法本身强大的生命力。所谓随机算法,就是在执行过程中要做出随机选择的算法。随机算法有两种不同类型:其一是总能给出正确的解,两次运行之间唯一的区别是运行时间不同,我们把这种随机算法叫做Las Vegas算法;其二是有时会产生不正确解的算法,然而我们能够界定产生不正确解的概率,我们把这种随机算法叫做Monte Carlo算法。这两种算法哪种更好些,要看它应用于哪类问题,Las Vegas算法可以看成是Monte Carlo算法当错误的概率为零的情况。     

两元指纹向量聚类问题的复杂性与改进启发式算法

证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figueroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2p)减小为O(m·(n·p 1)·2p),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2p)减小为O(m·2p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.     

一种基于PCA和系统成团法的聚类软件设计

提出一种基于主分量分析和系统成团法的快速聚类方法.通过构造主分量空间将分散在一组变量上的高维天体光谱投影到两个主分量上,每一个主分量都是原始变量的线性组合,主分量之间互为正交关系,在剔除冗余信息的同时,得到二维坐标;以此为输入,使用系统成团法进行聚类分析研究,实现高维天体光谱的快速自动分类处理.以上述方法为基础设计天体光谱自动分类软件,实现海量光谱的快速、准确分类.     

一个求解结构SAT问题的高效局部搜索算法

逻辑表达式可满足性(SAT)问题是第一个被证明的NP完全问题.它也是解决人工智能和计算理论中许多实际问题的基础.人们发现,对于某些类型的SAT问题,局部搜索算法要比一些传统的算法(例如Davis-Putnam过程)更为有效.在本文中,我们主要讨论如何用局部搜索算法求解结构SAT问题.我们对一个典型的局部搜索算法GSAT+walk做了改进与扩展.首先,我们除去了GSAT+walk中GSAT部分的"平移";其次,我们给每一个子句赋权,并在GSAT+walk的搜索过程中动态地调整子句的权.文中给出的实验结果表明改进后的新算法对于求解结构SAT问题非常有效.     

A polynomial-time algorithm for reducing the number of variables in MAX SAT problem

Maximum satisfiability (MAX SAT) problem is an optimization version of the satisfiability (SAT) problem. This problem arises in certain applications in expert systems and knowledge base revision. MAX SAT problem is NP-hard Some algorithms can solve this problem, but they are not adapted to the special cases where the number of variables is larger than the number of clauses. Usually, the number of variables has great impact on the efficiency of these algorithms. Thus, a polynomial-time algorithm is proposed to reduce the number of variables. Let T be any instance of the MAX SAT problem. The algorithm transforms T into another instance P of which the number of variables is smaller than the number of clauses of T. Using other algorithms, the optimal solution to P can be found, and it can be used to construct the optimal solution of T. Therefore, this algorithm is an efficient preprocessing step.