翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.

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

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

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

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

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

Problems of computing the reversal distance between genomes are discussed. Problems of computing the reversal distance between genomes are fundamental problems of Computational Biology, these problems have important meanings in studying the biological race evolution and the bio-pharmaceuticals etc. The problem of evolutionary trees based on reversal distance between genomes and it's NPC property are especially discussed.

带式输送机胶带翻转距离的确定

根据胶带侧边伸长不超过许可伸长，推导了胶带翻转距离的计算公式。

三类三角剖分的对角线翻转距离

在对凸n(n>7)边形的三类特殊形态三角剖分研究基础上,证明三类三角剖分的对角线翻转距离,从而求得三类三角剖分对角线翻转距离的上下界,并且通过三角剖分与二叉树之间的对应关系,给出与这三类三角剖分相对应的二叉树之间的旋转距离.

带式输送机输送带翻转角度研究

带式输送机的输送带翻转运行可以有效减轻机械磨损,提高工作特性。从带式输送机翻转装置形式出发,充分考虑输送带自身的许用强度、工作张力等因素,对斜辊与垂直夹辊式翻转装置翻转长度进行了计算,并对几种计算公式进行比较分析,在此基础上推导了斜辊的安装角度,利用MATLAB绘制了翻转段任意位置输送带水平夹角与长度关系曲线,其计算结果可为现代带式输送机工程计算提供有益的参考和补充。

一种基于EFD的混合属性聚类算法

为了提高混合属性聚类效率,提出一种基于扩张翻转距离(Expand Flip Distance, EFD)的混合属性聚类算法。以信息熵及熵权法为基础,通过定义扩张属性和属性扩张量得到EFD,将其作为待聚类对象属性区分的依据,进行聚类对象的属性约简,最终对约简后的属性构建混合属性聚类模型,实现混合属性聚类。实验结果表明,所提算法获得的聚类谱系图和聚类结果均优于对比算法,验证了该算法的合理性和有效性。

带式输送机翻带装置设计要点

随着带式输送机向大型化和环保化方向发展,为提高设备整体性能和输送效率,翻带装置的应用越来越普遍。而翻转段最小距离的确定是翻带装置设计的关键,设计计算时应综合考虑输送带本身的许用强度、工作张力及下垂量的影响,同时还应避免输送带在翻转段出现折迭现象。从带式输送机翻带装置型式出发,列出几种常用的翻转段距离的计算方法,并对几种计算方法进行对比分析,根据分析结果对带式输送机翻转段的设计要点进行总结。