Title求进化距离的改进算法
Authors谢扬
王攻本
Affiliation北京大学计算机科学与技术系
北京大学分校
Keywords算法
Seller算法
进化距离
空间复杂性
Issue Date1991
Publisher北京大学学报 自然科学版
Citation北京大学学报(自然科学版).1991,(01),43-50.
Abstract本文在Seller算法的基础上提出了一个新的求进化距离的改进算法。该法通过计算来求出一条最短路径,去掉了指针矩阵。并且在求最短路径时采用了分支与定界、对角线方向扩展、相邻对角线传递等技术。从而不仅使改进算法的空间耗费由Seller算法的平方级(O(m×n))降为线性级(O(m+n)),并且其时间耗费仍能保持Fickett算法的结果。该算法已在IBM-PC/AT上实现。
URIhttp://hdl.handle.net/20.500.11897/153175
ISSN0479-8023
Indexed中国科学引文数据库(CSCD)
Appears in Collections:信息科学技术学院

Files in This Work
Adobe PDF

Web of Science®



Checked on Last Week

百度学术™



Checked on Current Time




License: See PKU IR operational policies.