Estudos de estruturas de dados eficientes para abordar o problema de otimização U-curve

Resumo

O problema de otimização U-curve pode ser utilizado para modelar problemas em diversas áreas; por exemplo, o problema de seleção de características em Reconhecimento de Padrões. Um algoritmo ótimo para abordar o problema U-curve é o U-Curve-Search (UCS). Esse algoritmo alcançou resultados promissores na solução desse problema, pois computa poucas vezes a função custo; porém, em sua atual implementação, UCS tem problemas de escalabilidade, o que se deve em grande medida à utilização de listas duplamente encadeadas para armazenar o controle do espaço de busca já percorrido pelo algoritmo. Dessa forma, propomos neste projeto de Iniciação Científica a investigação do uso de diagramas de decisão binária reduzidos e ordenados (ROBDDs) como solução de estrutura de dados para controlar o espaço de busca já percorrido pelo algoritmo UCS. Utilizaremos ROBDDs para desenvolver uma nova versão do UCS, que será implementada e testada utilizando o arcabouço featsel. Realizaremos testes com instâncias artificiais e também dados de problemas reais, tais como o desenho de W-operadores. Esperamos que a nova versão do algoritmo UCS seja eficiente também do ponto de vista de consumo de tempo computacional, tornando o algoritmo competitivo para resolver problemas práticos que possam ser descritos como um problema U-curve. (AU)