中国科技论文在线

上传时间

2006年12月01日

朱大铭，栾峻峰+，马绍汉

软件学报，2003，14（2）：183～189，-0001，（）：

-1年11月30日

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

算法，计算复杂性，进化树，基因组，翻转距离

86浏览
0点赞
0收藏
0分享
121下载
0

引用

上传时间

2006年12月01日

【期刊论文】有向基因组移位排序问题的O(n2)快速算法

朱大铭，刘晓文)，朱大铭)，马绍汉)，李子茂)，王鲁生)

计算机学报第，2004，27（10），-0001，（）：

-1年11月30日

摘要

有向基因组移位排序问题在计算生物学研究中占有重要位置。以前最好的算法时间复杂度为0（n2logn)，该文给出一个有向基因组移位排序的新多项式算法，将移位排序的时间复杂度改进为O（n2）。算法改进的关键在于找到一种寻找有效合理移位的新方法，通过在最小子排列中删除无关顶点确定一个合理移位是否有效，从而将寻找一个有效移位的时间复杂度改进为O（n），总时间复杂度由此降为O（n2）。

基因组，移位，计算生物学，算法，时间复杂度

55浏览
0点赞
0收藏
0分享
95下载
0

引用

上传时间

2006年12月01日

【期刊论文】神经网络求解图章了短路径问题的一种新方法*

朱大铭，马绍汉

软件学报，7：191～198，-0001，（）：

-1年11月30日

摘要

本文给聘种求解图最短路径问题的实用反馈式神经网络，并证明这种网络的求解稳定性。这种网络基于最小值选择网而构成，对任意有向图和无向图均能收敛到其唯一的稳定点，由此求得力产所有顶点对间的最短路最短路径长度。本文结果最神经网求解NP-难解类优化问题的一种新尝试。

神经网络,，突触权植,，稳定性,，图,，最短路径.，

48浏览
0点赞
0收藏
0分享
126下载
0

引用

上传时间

2006年12月01日

【期刊论文】基因组Translocation排序问题的改进多项式算法

朱大铭，马绍汉

计算机学报，2002，25（2）189～196，-0001，（）：

-1年11月30日

摘要

该交给出基因组Translocation排序问题的一个改进多项式算法，原算法所用存储空间为O（n），时间复杂度为O（n2），文中改进算法仍采用O（n）存储空间，时间复杂度为O（n2logn）具体地，将计算Tranalocation距离的时间复杂度由O（n3）改进为O（n2），将计算Translocation序列的时间复杂度由O（n1）改进为O（ntlogn）

算法，时间复杂度，基团组，交叉排序