Algoritmo de aproximação

Prévia do material em texto

Algoritmos de aproximação
Analise e projeto de algoritmos
Alana Costa
Kelvyn Lucas
Roger Mesquita
Algoritmo de aproximação
 Algoritmos de aproximação é desenvolvido para concentrar-se em soluções aproximadamente ótimas. Não necessariamente produzem soluções ótimas, mas é preciso estar dentro de um certo fator da solução ótima
Se concentram em problemas difíceis.
2
Algumas aplicações:
Caixeiro Viajante
Problema da mochila
Biologia computacional
Engenharia financeira
Problema: Escalonamento de maquinas
Escalonamento Ex.1
Escalonamento Ex.2
Problema
 O problema consiste em encontrar a solução ótima ou mais próximas para melhor uso do tempo e das maquinas no escalonamento.
Algoritmo de Graham
A heurística do algoritmo de Graham consiste basicamente em atribuir a tarefa a maquina menos ocupada.
No primeiro passo todas as maquinas estão desocupadas assim o primeiro processo vai para qualquer uma.
Após o primeiro passo o modelo segue com a aplicação do processo para a maquina menos ocupada.
Escalonamento Graham
m máquinas
t tarefas
Duração d [ i ] da tarefa i
T tempo
Analise do algoritmo
BUILD MIN HEAP O(m)
HEAP INCREASE KEY O(t lg m)
Delimitações para OPT
Fator de aproximação
Fator de aproximação
Fator de aproximação
Algoritmos de Aproximação
Algoritmo ALG é de aproximação se existe 2 > 0 tal que valor de
 ALG <= 2 * OPT para toda instância do problema.
2 é o fator de aproximação 
Objetivo: 2 tão perto de 1 quanto possível A
Conclusão
 O algoritmo ESCALONAMENTO-GRAHAM é uma 2-aproximação polinomial.