Heurísticas para o problema de partição de strings comuns mínima

Abstract

In this work, we study and propose an implementation of the Greedy Random Adaptive Search Produce (GRASP) algorithm and two other heuristics for the Minimum Common String Partition Problem (MCSP). In our implementations we use adaptations of the greedy heuristic of Chrobak et al. (2004). We performed computational experiments to evaluate the efficiency of the proposed heuristics, comparing them with heuristics known from the literature, including state-of-the-art in relation to heuristics. With the results, we concluded that our best heuristic had a much shorter execution time despite the fact that the solution quality is worse in relation to the state-of-the-art. However, the results suggest a potential in the proposed approaches for application in cases that demand a faster time of the algorithm for approximate solutions.