of 43 /43
Algoritmos Gulosos e Aproximados Dianne Dias Silva Inael Rodrigues Jarderson Cruz

Paa algoritmos gulosos

Embed Size (px)

DESCRIPTION

Apresentação de Algoritmos Gulosos na disciplina Análise de Algoritmos do mestrado da UFG.

Text of Paa algoritmos gulosos

  • 1. Algoritmos Gulosos e AproximadosDianne Dias SilvaInael RodriguesJarderson Cruz

2. O que so algoritmos gulosos? 3. O que so algoritmos gulosos?Algoritmo guloso, ou ganancioso, uma tcnica de algoritmos para resolver problemas de otimizao, sempre realizando a escolha que parece ser amelhor no momento; fazendo uma escolha tima local, na esperana de que esta escolha leve at a soluo tima global. 4. Caractersticas dos Algoritmos Utilizados para otimizao; Um algoritmo guloso "mope"; Nunca voltam atrs; Algoritmossimples ede fcilimplementao; Nem sempre conduz solues timasglobais; Podem efetuar clculos repetitivos. 5. Elementos do Algoritmo Guloso Propriedade de escolha gulosa; Subestrutura tima. 6. Algoritmo Guloso Genrico 7. Problema do Troco 8. Problema do Troco Troco de $2.89; Moedas = { 100, 25, 10, 5 , 1 }; Min (Troco): 2 de valor 100, 3 de valor 25, 1de valor 10 e 4 de valor 1. 9. Algoritmo do Troco 10. Seleo de Atividades 11. Seleo de Atividades S = a1, a2, . . . , an um conjunto n atividadesque desejam utilizar um mesmo recurso; ai possui um tempo de incio (si) e um tempode trmino (fi); 0 si < fi < ; ai e aj so compatveis se si fj ou sj fi. 12. Seleo de Atividades 13. Seleo de Atividades 14. Seleo de Atividades 15. Seleo de Atividades 16. Seleo de Atividades 17. Seleo de Atividades 18. Seleo de Atividades 19. Seleo de Atividades 20. Algoritmo da Seleo de Atividades 21. Algoritmo da Seleo de Atividades 22. Estratgia Gulosa X ProgramaoDinmica Programao Dinmica: Escolha dependedas solues para os subproblemas (Top-down), ou seja, subproblemas menores paraos maiores; Estratgia Gulosa: No depende dassolues para os subproblemas (Bottom-up), isto , a instncia de um problema reduzida a cada iterao, atravs da escolhagulosa. 23. Problema da Mochila Problema da mochila 0-1: um ladro temque levar itens inteiros e pode levar ummesmo item apenas uma vez; Problema da mochila fracionria: o ladropode levar fraes de cada item; Pode se utilizar uma estratgia gulosa pararesolver o problema da mochila fracionria,mas no para resolver o da mochila 0-1. 24. Problema da Mochila 25. Algoritmos Aproximados Um algoritmo de aproximaoretornasolues aproximadas; So algoritmos de tempo polinomial paravrios problemas NP-completos; Tais algoritmos possuem relao deaproximao se para qualquer entrada, queindica soluo obtida est dentro do fatordefinido do custo da soluo tima; 26. Relao de Aproximao A relao de aproximao p(n) definidaem termos do custo C* de uma soluotima; Para qualquer entrada de tamanho n, ocusto C da soluo produzida pelo algoritmode aproximao est dentro de um fator p(n)da soluo tima; 27. Relao de Aproximao Estas definiesse aplicam tanto aproblemasde minimizaoquantomaximizao; Maximizao (01; Quando a relao de aproximao independente de n, a denotamos de p(n); possvel alcanar relaes deaproximao cada vez melhores, mas aocusto de mais tempo de computao. 29. Esquemas de AproximaoO esquema de aproximao um algoritmo de aproximao que toma como entrada no apenas uma instncia do problema, mas tambm um valor ;Tal que para qualquer fixo, o esquema um algoritmo de aproximao (1 + ); 30. Esquemas de Aproximao Se o esquema de aproximao executadoem tempo polinomial para qualquer > 0fixo, o chamamos de esquema deaproximao de tempo polinomial; Se o tempo de execuo polinomial em 1/quanto ao tamanho n da instncia daentrada, o chamamos de esquema deaproximao de tempo completamentepolinomial. 31. Algoritmos Aproximados Cobertura de Vrtices: Problema deDeciso; Cobertura de Vrtices Mnima: Problema deOtimizao. 32. Cobertura de Vrtices Se o problema enunciado como um problema dedeciso, chamado de o problema da cobertura devrtices: Instncia: Grafo G e um inteiro positivo K. Questo: Tem G uma cobertura de vrtices de tamanho mximo de K? O problema da cobertura de vrtices um problemados 21 problemas NP-completos de Karp. 33. Cobertura de Vrtices O problema da cobertura de vrtices mnima um problema de otimizao que consisteem encontrar a menor cobertura de vrticesem um grafo dado. INSTNCIA: Grafo G; SADA: Menor nmero K de tal forma que G temuma cobertura de vrtices de tamanho K.. 34. Cobertura de Vrtices Definio: Na Teoria dos grafos, umacobertura de vrtices de um grafo umconjunto de vertices tal que cada aresta dografo incidente, a pelo menos, um vrticedo conjunto. 35. Cobertura de Vrtices A verso de otimizao do problema decobertura de vrtices consiste em encontrara cobertura de vrtices de um grafo querequer o menor nmero de vrtices. A chamada cobertura de vrtices tima. 36. Cobertura de Vrtices Cobertura qualquer: Cobertura Mnima: 37. Cobertura de Vrtices Como seria uma heurstica plausvel paraobter uma boa cobertura de vrtices? Adicione os ns de maior grau a C at que todas asarestas estejam cobertas. Esta heurstica no uma aproximao A sua relao de aproximao cresce a uma taxalog n, em que n o nmero de vrtices. 38. Cobertura de Vrtices Para criarmos um algoritmo de aproximaoneste caso, usaremos uma tcnica queaparentemente menos sofisticada do queaquela heurstica. Comece com C Vazio; Enquanto houver alguma aresta no coberta,escolha arbitrariamente uma aresta (u,v), adiciona-aa um conjunto A, adicione u e v a C e os remova deG, juntamente com as demais arestas incidentes aelas. 39. Cobertura de Vrtices 40. Cobertura de Vrtices Quo distante do timo a cobertura devrtices obtida pode ser? A contm arestas de G, das quais, nenhumacompartilha um mesmo vrtice: um emparelhamento. Limitante: Uma cobertura de vrtices tima,obviamente contm pelo menos um vrtice ligado acada uma das arestas A: Seno alguma aresta no seria coberta; Ento |C*|>= |A|. 41. Cobertura de Vrtices A cobertura de vrtices C comtm os doisvrtices de cada aresta em A, logo:|C|=2|A| Combinando as duas equaes, temosque:|C|