Tenho uma amiga virtual, a Ananda Menali, que sempre me pergunta: “Por que os títulos das coisas que você escreve são tão esquisitos e complexos?”. Pois é, isso se deve porque na linha de pesquisa em que me encontro inscrito no PPGI (Programa de Pós-Graduação em Informática) na UniRio (Universidade Federal do Estado do Rio de Janeiro) o negócio é assim: complicado! Existe uma divisão na parte de Engenharia de Software onde temos o pessoal da área soft, que trata de processos e nós da área hard, que tratamos de desenvolvimento. Apesar da brincadeira o trabalho em ambos os campos é bem pesado. Numa pós graduação Strictu Senso em TI, não tem como os títulos dos trabalhos serem normais né Ananda? ;)
Na parte hard da coisa, que é a minha praia, temos um grupo de pesquisa em Engenharia de Software Orientada a Buscas (SBSE – Search Based Software Engineering), onde realizamos pesquisas de otimização combinatória. Todas as pesquisas são direcionadas à desenvolvimento de aplicações e gerência de projetos. Otimização combinatória é um “troço” de doido. Das pesquisas que estão em andamento, apenas duas já fecharam. Eu sou da terceira turma do programa e só o pessoal da primeira turma conseguiu defender. A pesquisa que eu acompanhei trata de um método para propor uma organização para a equipe de testes com o objetivo de atender à correção de bugs. Achei o assunto muito interessante afinal sou desenvolvedor e trabalho com isso diariamente. Ela motivou meu trabalho no campo de otimização. Mas então: o que é otimização combinatória? Vamos falar português?
Para falar de otimização primeiro precisamos falar de problemas e suas classes. Existem duas classes de problemas que os dividem em tipo P e NP. Problemas do tipo P são aqueles para os quais existem soluções que podem ser encontradas num tempo exeqüível. Tempo exequível significa, de fato, viável. Matematicamente estamos falando de tempo polinomial, ou seja, o crescimento do tempo pode ser descrito por um polinômio. Dada uma instância (uma entrada) N do problema, o tempo para encontrar a solução é algum polinômio do tipo 2N. Português: você leva duas vezes o tamanho da entrada para resolver o problema. Sendo assim se a entrada tem tamanho 3 a solução é encontrada em 6. Crescimento alto, sem dúvida. Porém exeqüível, polinomial.
Porém, esse é um grupo restrito de problemas. Problemas de otimização são problemas complexos por natureza, afinal o objetivo é melhorar uma solução, otimizar. É aí então que entram os problemas do tipo NP. Problemas do tipo NP são aqueles para os quais não há solução em tempo polinomial, ou seja, não pode ser descrito por um polinômio. Esse tipo de problema possui características que fazem com que o tempo para encontrar uma solução cresça exponencialmente. Usando o mesmo exemplo se a equação que descreve o crescimento do tempo de um problema NP é 2N, então para uma entrada de tamanho 3 temos 23 que é 8. Conforme o tamanho da instância do problema cresce, o tempo para encontrar a solução vai se tornando inviável. Aplicações práticas de alguns problemas não permitem que eles demorem muito para encontrar uma resposta. Um exemplo clássico na área é o da Mochila binária. Encher uma mochila com itens que tem peso e valor, sabendo que não pode ultrapassar a carga da mochila é fácil. Existem N métodos que podem fazer isso. Agora encontrar o melhor grupo de itens de forma que maximize o valor e minimize o peso já não é tão simples. Se permitirmos também colocar na mochila frações desses itens, o problema fica tão complexo que vai para um grupo específico de problemas chamado NP-Hard. Agora imaginem que seria necessário, por exemplo, 8 horas para encontrar a forma otimizada (solução ótima) de encher a mochila. Quem usaria uma solução dessas? Na prática você colocaria os melhores itens que coubessem e pronto, já está bom! Em geral uma solução boa (próxima da ótima) já atende bem ao problema.
Levando em consideração essas duas características podemos concluir que se existir um método que encontre uma solução boa num tempo melhor do que varrer todas as opções, podemos aplicá-lo. Esse raciocínio permitiu a criação de métodos quem encontram boas soluções com alguma garantia de distância da solução ótima. Esses métodos usam heurísticas para chegar nesses resultados. Através da implementação de algoritmos heurísticos é possível, por exemplo, que um roteador decida uma determinada rota boa num tempo bom. Determinar um rota tem que ser algo rápido e explorar todas as possibilidades é inviável. Portanto usa-se uma heurística e aceita-se um certo nível de qualidade da solução.
Acho que para esse post já está bom. Falamos dos tipos de problemas e sobre a SBSE. Num próximo falo da minha pesquisa e de como estou evoluindo com ela.
Alguns links relacionados:
SBSE Repository
Programa de Pós-Graduação em Informática – Unirio
2nd International Symposium on Search Based Software Engineering
Comment