Objeto de conferencia
Uma heurística GRASP para o Problema da Sequência mais Próxima
Registro en:
issn:1850-2865
Autor
Laux, Válber
Lyra, Adria
Institución
Resumen
O Problema da Sequência mais Próxima (PSMP) é um problema da Biologia Molecular que aparece no contexto da comparação de sequências. O objetivo é encontrar uma sequência que apresente a menor distância entre todas as sequências de um conjunto dado. O problema foi provado ser NP-difícil.
Diversos algoritmos aproximativos, exatos e heurísticos tem sido propostos.
Neste trabalho é proposto um algoritmo para o PSMP baseado na metaheurística GRASP, que apresentou soluções de boa qualidade em baixo tempo de execução nos testes realizados. Sociedad Argentina de Informática e Investigación Operativa