Algoritmos de Aproximação
Prof. Flávio Keidi Miyazawa
Um ramo da Otimização Combinatória
Problemas de otimização, na sua forma geral, têm como objetivo maximizar ou minimizar uma função definida sobre um certo domínio. A teoria clássica de otimização trata do caso em que o domínio é infinito. Já no caso dos chamados problemas de otimização combinatória, o domínio é tipicamente finito; além disso, em geral é fácil listar os seus elementos e também testar se um dado elemento pertence a esse domínio. Ainda assim, a idéia ingênua de testar todos os elementos deste domínio na busca pelo melhor mostra-se inviável na prática, mesmo para instâncias de tamanho moderado.Como exemplos clássicos de problemas de otimização combinatória podemos citar o problema do caixeiro viajante, o problema da mochila, o problema da cobertura mínima por conjuntos, o problema da floresta de Steiner e o problema de encontrar um conjunto independente máximo em um grafo. No sentido técnico, todos são NP-difíceis. Estes, e diversos outros de mesma natureza, são porém, de grande interesse pois surgem em aplicações práticas na indústria, tais como em projeto de redes de telecomunicação e de circuitos VLSI, problemas de empacotamento, problemas de localização de centros distribuidores, problemas de escalonamento, problemas de roteamento de veículos, etc. Outras áreas de aplicação incluem estatística (análise de dados), economia (matrizes de entrada/saída), física (determinação de estados de energia mínima), biologia molecular (alinhamento de DNA, inferência de padrões), etc.
O que é um Algoritmo de Aproximação
Em linhas gerais, Algoritmos de aproximação são algoritmos que não necessariamente produzem uma solução ótima, mas soluções que estão dentro de um certo fator da solução ótima.O desenvolvimento de algoritmos de aproximação surgiu em resposta à impossibilidade de se resolver satisfatoriamente diversos problemas de otimização NP-difíceis. Estamos nos referindo aqui à impossibilidade, sob a hipótese de que P<>NP, de se encontrar algoritmos eficientes para esses problemas.
Nessa situação, parece razoável sacrificar a otimalidade em troca da garantia de uma solução aproximada computável eficientemente. Certamente, o interesse é, apesar de sacrificar a otimalidade, fazê-lo de forma que ainda possamos dar boas garantias sobre o valor da solução obtida, procurando ganhar o máximo em termos de eficiência computacional.
Esse compromisso entre perda de otimalidade e ganho em eficiência é o paradigma dos algoritmos de aproximação.
Técnicas
Algumas das técnicas que têm sido usadas em algoritmos de aproximação são:Algumas das técnicas acima são bem recentes e estão despertando bastante interesse dos pesquisadores, sendo atualmente foco de intensas pesquisas e estudos na área.Métodos Combinatórios
Flávio Keidi Miyazawa's Homepage