Heurísticas em Otimização Combinatória

Prévia do material em texto

Alysson M. Costa – ICMC/USPAlysson M. Costa – ICMC/USP
Tópicos em otimização 
combinatória
Heurísticas (Introdução)
Slides quase que integralmente baseados em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Slide baseado em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Heurísticas
Slide baseado em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Heurísticas
� Muitas vezes são baseadas em procedimentos simples, 
fáceis de implementar e fáceis de “justificar”.
� Muito aceitas em contextos práticos. (Métodos 
implementados em pacotes comerciais – e.g., para 
resolução de problemas de roteamento de veículos –
muitas vezes obtém soluções a 10, 20% das melhores 
soluções possíveis). 
� Discussão: se em muitos contextos, 1% pode significar 
milhares de reais, porque tais soluções são aceitas ?
Alysson M. Costa – ICMC/USP
Heurísticas
A l g u
m a
s
Slide baseado em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Heurísticas
Slide baseado em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Heurísticas
Slide baseado em material da professora Vitória Pureza - UFSCAR
Ex.:
Alysson M. Costa – ICMC/USP
Heurísticas
Slide baseado em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Visão geral sobre os tipos de heurísticas
Slide baseado em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Visão geral sobre os tipos de heurísticas
Slide baseado em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Visão geral sobre os tipos de heurísticas
Slide baseado em material da professora Vitória Pureza - UFSCAR
Alysson M. Costa – ICMC/USP
Visão geral sobre os tipos de heurísticas
Slide baseado em material da professora Vitória Pureza - UFSCAR