A recursive exact algorithm for the Closest String Problem

被引：0

作者：

Vilca, Omar Latorre ^{[1
]}

Júnior, Mário Salvatierra ^{[1
]}

机构：

[1] Federal University of Amazonas (UFAM), Brazil

来源：

Journal of Combinatorial Mathematics and Combinatorial Computing | 2020年 / 115卷

关键词：

Integer programming - Heuristic methods - Heuristic algorithms;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

In this paper we study the Closest String Problem (CSP). To solve the CSP involves finding a string that minimizes the maximum Hamming distance from a given set of strings with an arbitrary alphabet Its decision version is NP-complete. The Hamming distance between two strings a and 6 of equal length is calculated by simply counting the character positions in which a and b differ. In this work we propose two approaches to solve the CSP. The first is a greedy heuristic algorithm (GREEDY), the second is a recursive exact method. The algorithms are compared with an integer programming formulation for CSP. Furthermore, computational experiments in comparison tables will show die effectiveness of the proposed algorithms. © 2020 Charles Babbage Research Centre. All rights reserved.

引用

页码：111 / 125