计算最短公共超串的贪婪算法

最短公共超串问题就是对给定的子串集合找到包含每个子串的可能的串。这个问题是一个NP-完全问题。目前已有一些方法对此进行了研究。通过对各子串的分析和研究,提出了一种近似于贪婪算法的求最短公共超串问题算法,该算法可应用于解决DNA片段组装和数据压缩问题。最后给出了几个实例。

融合遗传和蚁群算法并行求解最短公共超串

依据各级缓存容量,将CPU主存中种群个体和蚂蚁个体数据划分存储到一级、二级和三级缓存中,以减少并行计算过程中数据在各级存储之间的传输开销,在CPU与GPU之间采取异步传送和不完全传送数据、GPU多个内核函数异步执行多个流的方法,设置GPU block线程数量为16的倍数、GPU共享存储器划分大小为32倍的bank,使用GPU常量存储器存储交叉概率、变异概率等需频繁访问的只读参数,将输入串矩阵和重叠部分长度矩阵只读大数据结构绑定到GPU纹理存储器,设计实现了一种多核CPU和GPU协同求解最短公共超串问题的计算、存储和通信高效的并行算法。求解多种规模的最短公共超串问题的实验结果表明,多核CPU与GPU协同并行算法比串行算法快70倍以上。