两元指纹向量聚类问题的复杂性与改进启发式算法

作者：刘培强; 朱大铭; 谢青松; 范辉; 马绍汉

来源：软件学报, 2008, (03): 500-510.

• 算法
• 复杂性
• 指纹向量聚类
• 基因表达谱
• 团划分

证明丢失值位数不超过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%的时间计算与原算法相同的实例.

• 出版日期2008-3-15
• 单位山东大学; 山东工商学院