Introdução Ex.: Escalonamento Ex.: Mochila Notas Projeto e Análise de Algoritmos Algoritmos Aproximados Haroldo Gambini Santos Universidade Federal de Ouro Preto - UFOP 2 de maio de 2013 Projeto e Análise de Algoritmos, Algoritmos Aproximados 1 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Situação Ideal Notas Desejamos algoritmos que: encontrem a solução ótima em tempo polinomial para qualquer instância do problema que estamos trabalhando Enquanto P 6= N P : para problemas NP-completos temos que nos contentar com 2 desses 3 Projeto e Análise de Algoritmos, Algoritmos Aproximados 2 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Algoritmos Aproximados Algoritmo com garantia Notas de produzir soluções sempre em um fator da solução ótima. Uma heurística pode ser um algoritmo aproximado caso exista tenha sido provado que para qualquer caso possível um padrão de qualidade se mantém. Heurísticas sem essa prova não são denominadas algoritmos aproximados. Projeto e Análise de Algoritmos, Algoritmos Aproximados 3 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Alg. Aproximados - Def. Um algoritmo é dito α Notas aproximado se: polinomial; 1 o mesmo roda em tempo 2 o mesmo sempre produz uma solução dentro de um solução ótima. fator α da Convenções minimização α > 1 maximização α < 1 Projeto e Análise de Algoritmos, Algoritmos Aproximados 4 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Algoritmos Aproximados - Motivação 1 problemas NP-Difíceis precisam de soluções; 2 forma matematicamente rigorosa de se estudar heurísticas; 3 entender o quão difíceis são os problemas. Projeto e Análise de Algoritmos, Notas Algoritmos Aproximados 5 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Analisando a qualidade Notas Questão Como avaliar a distância da solução ótima se calcular a solução ótima já é altamente custoso ? Limites Para um problema de minimização(/maximização) difícil, calcular um Limite Inferior (/Superior ) pode ser fácil. Uma vez mostrado que nosso algoritmo sempre produz uma solução no máximo α vezes o custo da do limite em questão já ca provado que isso vale para a solução ótima. Ponto fundamental: qualidade do limite Projeto e Análise de Algoritmos, . Algoritmos Aproximados 6 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Exemplo: Balanceamento de carga 5 tarefas (n = 5), Notas com tempos de processamento tj : t1 = 3 t2 = 7 t3 = 5 t4 = 1 t5 = 4 3 máquinas (m = 3) Projeto e Análise de Algoritmos, Algoritmos Aproximados 7 / 19 Ex.: Escalonamento makespan Objetivo: Diminuir o Uma solução com makespan 8: M1 t1 = 3 t2 = 7 M2 M3 t5 = 4 t4=1 Ex.: Mochila Notas makespan=8 Introdução t3 = 5 M1 M2 M3 t5 = 4 t1 = 3 t2 = 7 t3 = 5 t4=1 makespan=7 tempo Uma solução com makespan 7: tempo Projeto e Análise de Algoritmos, Algoritmos Aproximados 8 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Um algoritmo guloso Notas Idéia Alocar as tarefas, uma-a-uma, colocando a nova tarefa sempre na máquina com procedure menor carga. GreedyScheduling ( t1 , . . . , tn , m ) Ti ← 0, A(i) ← ∅ ∀i ∈ 1 . . . , m ; f o r j ← 1 to n do begin Encontre k : Tk = min{1,...,m} Ti ; A(k) ← A(k) ∪ {j} ; Tk ← Tk + tj ; end end Projeto e Análise de Algoritmos, Algoritmos Aproximados 9 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Limites Inferiores para o Notas Makespan ótimo OPT Relaxação Pn j=1 tj OPT ≥ m Tarefa grande n OPT ≥ max tj j=1 Limite Inferior Pn n j=1 tj LB = max{max tj , m j=1 Projeto e Análise de Algoritmos, } Algoritmos Aproximados 10 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Teorema: GreedyScheduling é Notas 2-Aproximado. Prova: Seja Mi∗ a máquina determinante do makespan. Seja j ∗ a última tarefa alocada nessa máquina. 0 A carga Ti∗ que a máquina Mi∗ apresenta antes de j ∗ ser 0 inserida é a menor entre as cargas Ti das máquinas. 0 m · Ti∗ ≤ m X ∗ 0 Ti = i=1 Ti∗ j X n X tj ≤ j=1 tj ≤ m · LB j=1 0 = tj ∗ + Ti∗ ≤ tj ∗ + LB n ≤ max tj + LB j=1 ≤ 2 · LB ≤ 2 · OPT Projeto e Análise de Algoritmos, Algoritmos Aproximados 11 / 19 Introdução Ex.: Escalonamento Resultados ruins entre quatro tarefas (n Ex.: Mochila OPT e 2 · OPT Notas = 3) t1 = 2, t2 = 1, t3 = 15, t4 = 2 duas máquinas (m = 2) Para quais ordens GreedyScheduling oferece soluções melhores ? Projeto e Análise de Algoritmos, Algoritmos Aproximados 12 / 19 Introdução Ex.: Escalonamento GreedyScheduling Melhorado: GreedySchedulingI Ex.: Mochila Notas Idéia Alocar as tarefas em ordem tamanho, decrescente de uma-a-uma, colocando a nova tarefa sempre na máquina com menor carga. GreedySchedulingI ( t1 , . . . , tn , m ) procedure Ti ← 0, A(i) ← ∅ ∀i ∈ 1 . . . , m ; f o r j ← 1 to n do begin t0 ← a j -ésima maior tarefa ; Encontre k : Tk = min{1,...,m} Ti ; A(k) ← A(k) ∪ {t0 } ; Tk ← Tk + tt0 ; end Projeto e Análise de Algoritmos, end Algoritmos Aproximados 13 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Provando a superioridade de Notas GreedySchedulingI se n ≤ m: para resultado ótimo; n > m, novo limite: OPT ≥ tm + tm+1 ; Partindo dos resultados anteriores: Ti∗ ≤ tj ∗ + LB ≤ 2 · LB ≤ 2 · OPT E considerando que: tj∗ ≤ tm + tm+1 OPT ≤ 2 2 GreedySchedulingI é 3 2 aproximado. Projeto e Análise de Algoritmos, Algoritmos Aproximados 14 / 19 Introdução Ex.: Escalonamento Ex.: Mochila O Problema da Mochila 0/1 Notas Entrada Capacidade S n itens com lucros e pesos (l1 , p1 ), . . . , (ln , pn ) Projeto e Análise de Algoritmos, Algoritmos Aproximados 15 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Problema da Mochila 0/1 - Algoritmo Notas Guloso GreedyKnapsack1 ( S, n, (l1 , p1 ), . . . , (ln , pn ) ) Ordene os itens em ordem decrescente de plii ; procedure if Pn i=1 pi return ≤ S then P solg = ni=1 li ; else begin Encontre o maior k ∈ {1, . . . , n} tal que Pk return solg = i=1 li ; Pk i=1 ≤S; end end Projeto e Análise de Algoritmos, Algoritmos Aproximados 16 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Falhando miseravelmente Notas Considere uma mochila com grande capacidade, digamos B . Considere a existência de um item i com lucro li = 2 e peso pi = 1, juntamente com um item de lucro B e peso B . Projeto e Análise de Algoritmos, Algoritmos Aproximados 17 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Problema da Mochila 0/1 - Algoritmo Notas Guloso Corrigido GreedyKnapsack2 ( S, n, (l1 , p1 ), . . . , (ln , pn ) ) Ordene os itens em ordem decrescente de plii ; procedure if Pn i=1 pi return ≤ S then P solg = ni=1 li ; else begin Encontre o maior k ∈ {1, . . . , n} tal que P sol1 = ki=1 li ; sol2 = lk+1 ; return Pk i=1 ≤S; solg = max {sol1 , sol2 } end end Projeto e Análise de Algoritmos, Algoritmos Aproximados 18 / 19 Introdução Ex.: Escalonamento Ex.: Mochila Teorema: GreedyKnapsack2 é Notas 2-Aproximado. Prova: Considere novamente k ∈ {1, . . . , n} sendo o maior valor tal que Pk i=1 ≤ S . Os seguintes limites para a solução ótima sol∗ são válidos: k X i=1 li ≤ sol∗ ≤ k+1 X li i=1 Projeto e Análise de Algoritmos, Algoritmos Aproximados 19 / 19 Notas Notas