广义落表算法与对偶落表算法

§1.引言 在铁道列车编组的计划作业中,由[1]总结提出的落表法是一种简便易行的计算方法,近年来,随着调车计划最优化问题数学理论研究的不断深入,人们发现该算法还具有其更重要的理论意义,譬如,当使用该算法按照顺序序列剖分任给定的随机排列时,所得到剖分的分部数可以达到最小。利用该性质,在研究随机排列的非顺序最优剖分时,通常     

含假结RNA二级结构类的图语法

用最小自由能法预测RNA二级结构是NP困难问题,其根本原因是假结的存在。近几年的预测算法都针具有一定结构特征的假结寻找多项式时间算法进行预测。论文针对RNA二级结构图提出一种图语法,该语法由初始结构图集和重写规则集构成,用重写规则在初始结构图上的不断重写得到的结构图都是该语法的语言。分析了5个主流RNA二级结构预测算法的目标集,给出它们的图语法,使得目标集的结构特征一目了然,目标集间的真包含关系也通过图语法直观地体现出来。     

Rivas-Eddy RNA二级结构图书嵌入分类的实现方法

书嵌入数是对图进行分类的一个拓扑标准,通常来说,计算一个图的书嵌入数及给出一种嵌入实例都是NP完全问题。针对Rivas-Eddy（R&E）类中RNA分子的二级结构图,从二级结构图的语法出发,通过其交叉关系图的点着色,构造性地得到了RNA分子二级结构图书嵌入的具体实现方法,完成了对RNA分子二级结构的书嵌入分类。该方法具有多项式时间复杂性,为求解NP完全问题提供了有益的参考。