Otimização combinatória

Prévia do material em texto

Otimização combinatória 
A otimização combinatória é um ramo da otimização em matemática 
aplicada e ciência da computação, relacionada à pesquisa operacional, 
teoria da informação algorítmica e teoria da complexidade 
computacional. 
Também está relacionado a outros campos, como inteligência artificial 
e engenharia de software. Os algoritmos de otimização combinatória 
resolvem instâncias de problemas considerados geralmente difíceis, 
explorando o espaço de solução para essas instâncias. 
 
Os algoritmos de otimização combinatória realizam isso reduzindo o 
tamanho efetivo do espaço e explorando o espaço de busca de forma 
eficiente. 
Os algoritmos de otimização combinatória são frequentemente 
implementados em linguagens imperativas, como C e C ++, entre outros 
softwares inteligentes em linguagens de programação lógica. 
Ao estudar a teoria da complexidade computacional, é possível 
entender a importância da otimização combinatória. Os algoritmos de 
otimização combinatória são comumente relacionados a problemas NP-
difíceis. 
Esses problemas em geral não são resolvidos de forma eficiente; 
entretanto, várias abordagens da teoria da complexidade sugerem que 
certas instâncias desses problemas podem ser resolvidas de forma 
eficiente. Esses casos geralmente têm ramificações práticas muito 
importantes.