Abordagens Heurísticas para Problemas de Seleção de Strings

Abstract

Este trabalho tem como objetivo estudar três dos principais problemas de seleção de strings: Closest String Problem (CSP), Farthest String Problem(FSP) e o Distinguishing String Selection Problem (DSSP). De maneira geral, no CSP deseja-se criar, para um dado conjunto de strings, uma string alvo que seja a mais próxima de todas as strings do conjunto, enquanto no FSP a string alvo deve ser a mais distante possı́vel. O DSSP, no entanto, busca criar uma string alvo que seja a mais próxima possı́vel de um conjunto S c e simultaneamente mais distante de outro conjunto S f . Também foram estudadas as variantes dos problemas CSP, FSP e DSSP que buscam por substrings alvos e são denotadas por CSSP, FSSP e DSSSP, respectivamente. [...]