基于蚁群算法求解最短公共超序列问题

提出基于多数融合启发式与向前看策略求解多个字符串最短公共超序列问题的蚁群算法.该算法采用n只蚂蚁相互独立地建立字符串集合R的超序列.每只蚂蚁在完成一次超序列构建后更新R中每个字符上的信息素.字符串中的每一个字符所得到信息素的多少依赖于该蚂蚁构建的超序列的质量、构建解的过程中字符出现的先后顺序以及在一个构建步骤中同一个字符在不同串中出现的次数3个因素.不同实验数据集上的对比测试结果表明该算法能求得更好的解.

ACA-Based Solution of Shortest Common Supersequence Problems

An ant algorithm is proposed in this paper to solve shortest common supersequence problems based on majority merge heuristic and look-ahead strategies.In this algorithm,n ants are used to independently establish a supersequence of the character string set R,and then update the pheromone of each character in set R,which depends on the quality of the supersequence and the occurrence order and frequency of the character.Experimental results of different test data show that the algorithm can find better solutio...