Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/58960
Title in Portuguese: Heurísticas para o problema de partição de strings comuns mínima
Author: Silva, Wallesson Cavalcante da
Advisor(s): Araújo, Paulo Henrique Macêdo de
Co-advisor(s): Dias, Fábio Carlos Sousa
Keywords: Algoritmos heurísticos
Biologia computacional
Heurística
Issue Date: 2020
Citation: SILVA, Wallesson Cavalcante da. Heurísticas para o problema de partição de strings comuns mínima. 2020. 45 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação)-Universidade Federal do Ceará, Campus de Quixadá, Quixadá, 2020.
Abstract in Portuguese: Neste trabalho, estudamos e propomos uma implementação do algoritmo Greedy Random Adaptive Search Produce (GRASP) e outras duas heurísticas para o problema de Partição de Strings Comuns Mínima (em inglês, Minimum Common String Partition Problem ou MCSP). Utilizamos em nossas implementações adaptações da heurística gulosa de Chrobak et al. (2004). Realizamos experimentos computacionais para avaliar a eficiência das heurísticas propostas, comparando-as com heurísticas conhecidas da literatura, incluindo o estado-da-arte em relação a heurísticas. Com os resultados, concluímos que nossa melhor heurística apresentou um tempo de execução muito menor apesar de a qualidade da solução ser pior em relação ao estado-da-arte. Porém, os resultados sugerem um potencial nas abordagens propostas para a aplicação em casos que demandam um tempo mais rápido do algoritmo para soluções aproximadas.
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.
URI: http://www.repositorio.ufc.br/handle/riufc/58960
metadata.dc.type: TCC
Appears in Collections:CIÊNCIA DA COMPUTAÇÃO-QUIXADÁ - Monografias

Files in This Item:
File Description SizeFormat 
2021_tcc_wcsilva.pdf539,03 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.