%0 Journal Article
%T 两元指纹向量聚类问题的复杂性与改进启发式算法
%A 刘培强？
%A 朱大铭？
%A 谢青松？
%A 范辉？
%A 马绍汉？
%J 软件学报
%P 500-510
%D 2008
%X 证明丢失值位数不超过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%的时间计算与原算法相同的实例.
%K 算法
%K 复杂性
%K 指纹向量聚类
%K 基因表达谱
%K 团划分
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20080303&flag=1