Com o advento da programação linear, esses métodos foram aplicados a problemas como atribuição, fluxo máximo e transporte. Na era moderna, a otimização combinatória é útil para o estudo de algoritmos, com especial relevância para inteligência artificial, aprendizado de máquina e pesquisa operacional.
Para que serve a otimização combinatória?
Otimização combinatória é o processo de busca de máximos (ou mínimos) de uma função objetivo F cujo domínio é um espaço de configuração discreto, mas grande (em oposição a um N-dimensional espaço contínuo).
Por que a otimização combinatória é difícil?
A dificuldade surge do fato de que diferentemente da programação linear, a região factível do problema combinatório não é um conjunto convexo. Assim, devemos, em vez disso, procurar uma rede de pontos factíveis, ou no caso do caso de inteiro misto, um conjunto de semi-retas ou segmentos de linha disjuntos para encontrar uma solução ótima.
Qual é o problema de otimização combinatória?
Otimização combinatória é um tópico que consiste em encontrar um objeto ótimo a partir de um conjunto finito de objetos … Opera no domínio daqueles problemas de otimização em que o conjunto de soluções viáveis é discreto ou pode ser reduzido a discreto, e em que o objetivo é encontrar a melhor solução.
A otimização combinatória é NP-difícil?
Quando se prova que uma versão de decisão de um problema de otimização combinatória pertence à classe de problemas NP-completos, então a versão de otimização é NP-hard … O problema de otimização, ou seja, encontrar o número mínimo (mínimo k) de polígonos em forma de estrela cuja união é igual a um determinado polígono simples é NP-difícil.
