Otimização combinatória
Otimização combinatória é um campo da matemática aplicada que
se baseia no uso conjunto de técnicas de combinatória, programação
matemática e teoria de desenvolvimento de algoritmos para resolver
problemas de otimização formulados sobre estruturas discretas. Uma
característica comum dos problemas de otimização combinatória é o
fato de que o conjunto de soluções viáveis, embora seja finito,
pode ser muito grande. Isso inviabiliza estratégias de força bruta,
como testar todos os valores de solução possíveis, e torna necessário o desenvolvimento
de métodos eficientes.
Problemas de otimização combinatória têm sido um tópico central para a
evolução de algoritmos e da teoria de complexidade
computacional. Pesquisadores têm apresentado muitas idéias criativas
para o projeto de algoritmos eficientes, baseados em conceitos e
resultados na área. A sub-área conhecida como combinatória
poliédrica, por exemplo, apresenta técnicas desenvolvidas a partir de
conceitos de programação linear, como o
método primal-dual, e
que têm se mostrado muito úteis no projeto e análise de uma variedade
de algoritmos para problemas em outros domínios. Muitas das idéias
inovadoras têm se baseado em um conjunto não muito grande de
princípios comuns, como scaling, que são simultaneamente
muito simples e muito poderosos.
Nem sempre, porém, é suficiente restringir a pesquisa de um problema
ao estudo teórico de seus aspectos e ao desenvolvimento abstrato de
algoritmos que o resolvem. Em diversos casos, existem fatores
fundamentais que só podem ser resolvidos, ou mesmo descobertos,
durante a implementação propriamente dita. Não é incomum que a
obtenção de uma eficiência próxima àquela calculada na teoria, ou
mesmo o próprio funcionamento de um algoritmo, dependa do uso de
estruturas de dados sofisticadas e técnicas de programação que não são
exatamente triviais.
Ademais, a complexidade de um algoritmo na teoria é muitas vezes um
argumento questionável para classificá-lo na prática: não são incomuns
algoritmos teoricamente eficientes mas lentos na prática, e algoritmos
cuja análise de pior caso está longe de representar seu comportamento
no caso médio. Diante dessa possibilidade, testes e experimentações
são ferramentas poderosas e úteis, e que enfatizam ainda mais a
importância da implementação.
|