Paa algoritmos gulosos

Algoritmos Gulosos e AproximadosDianne Dias SilvaInael RodriguesJarderson Cruz

O que são algoritmos gulosos?

O que são algoritmos gulosos?

Algoritmo guloso, ou ganancioso, é uma técnica de algoritmos para resolver problemas de otimização, sempre realizando a escolha que parece ser a

melhor no momento; fazendo uma escolha ótima local, na esperança de que esta escolha leve até a solução ótima global.

Características dos Algoritmos

● Utilizados para otimização; ● Um algoritmo guloso é "míope";● Nunca voltam atrás;● Algoritmos simples e de fácil

implementação;● Nem sempre conduz à soluções ótimas

globais;● Podem efetuar cálculos repetitivos.

Elementos do Algoritmo Guloso

● Propriedade de escolha gulosa;

● Subestrutura ótima.

Algoritmo Guloso Genérico

Problema do Troco

Problema do Troco

● Troco de $2.89;

● Moedas = { 100, 25, 10, 5 , 1 };

● Min (Troco): 2 de valor 100, 3 de valor 25, 1 de valor 10 e 4 de valor 1.

Algoritmo do Troco

Seleção de Atividades


● S = a1, a2, . . . , an um conjunto n atividades que desejam utilizar um mesmo recurso;

● ai possui um tempo de início (si) e um tempo de término (fi);

● 0 ≤ si < fi < ∞;

● ai e aj são compatíveis se si ≥ fj ou sj ≥ fi.









Algoritmo da Seleção de Atividades

Algoritmo da Seleção de Atividades

Estratégia Gulosa X Programação Dinâmica

● Programação Dinâmica: Escolha depende das soluções para os subproblemas (Top-down), ou seja, subproblemas menores para os maiores;

● Estratégia Gulosa: Não depende das soluções para os subproblemas (Bottom-up), isto é, a instância de um problema é reduzida a cada iteração, através da escolha gulosa.

Problema da Mochila

● Problema da mochila 0-1: um ladrão tem que levar itens inteiros e pode levar um mesmo item apenas uma vez;

● Problema da mochila fracionária: o ladrão pode levar frações de cada item;

● Pode se utilizar uma estratégia gulosa para resolver o problema da mochila fracionária, mas não para resolver o da mochila 0-1.

Problema da Mochila

Algoritmos Aproximados

● Um algoritmo de aproximação retorna soluções aproximadas;

● São algoritmos de tempo polinomial para vários problemas NP-completos;

● Tais algoritmos possuem relação de aproximação se para qualquer entrada, que indica solução obtida está dentro do fator definido do custo da solução ótima;

Relação de Aproximação

● A relação de aproximação p(n) é definida em termos do custo C* de uma solução ótima;

● Para qualquer entrada de tamanho n, o custo C da solução produzida pelo algoritmo de aproximação está dentro de um fator p(n) da solução ótima;


● Estas definições se aplicam tanto a problemas de minimização quanto maximização;

● Maximização (0<C<C*): a relação C*/C o fator do custo da solução ótima é maior que o custo da solução aproximada;

● Minimização (0<C*<C): a relação C/C* o fator do custo da solução aproximada é maior que o custo da solução ótima;


● A relação de aproximação nunca é menor que 1, pois C/C*<1 implica C*/C>1;

● Quando a relação de aproximação é independente de n, a denotamos de p(n);

● É possível alcançar relações de aproximação cada vez melhores, mas ao custo de mais tempo de computação.

Esquemas de Aproximação

●O esquema de aproximação é um algoritmo de aproximação que toma como entrada não apenas uma instância do problema, mas também um valor ε;

●Tal que para qualquer ε fixo, o esquema é um algoritmo de aproximação (1 + ε);

Esquemas de Aproximação

● Se o esquema de aproximação é executado em tempo polinomial para qualquer ε > 0 fixo, o chamamos de esquema de aproximação de tempo polinomial;

● Se o tempo de execução é polinomial em 1/ε quanto ao tamanho n da instância da entrada, o chamamos de esquema de aproximação de tempo completamente polinomial.

Algoritmos Aproximados

● Cobertura de Vértices: Problema de Decisão;

● Cobertura de Vértices Mínima: Problema de Otimização.

Cobertura de Vértices

● Se o problema é enunciado como um problema de decisão, é chamado de o problema da cobertura de vértices:○ Instância: Grafo G e um inteiro positivo K.○ Questão: Tem G uma cobertura de vértices de

tamanho máximo de K?

● O problema da cobertura de vértices é um problema dos 21 problemas NP-completos de Karp.

http://pt.wikipedia.org/wiki/Problema_de_decis%C3%A3o

http://pt.wikipedia.org/wiki/Problema_de_decis%C3%A3o

http://pt.wikipedia.org/w/index.php?title=Problemas_NP-completos_de_Karp&action=edit&redlink=1

http://pt.wikipedia.org/w/index.php?title=Problemas_NP-completos_de_Karp&action=edit&redlink=1


● O problema da cobertura de vértices mínima é um problema de otimização que consiste em encontrar a menor cobertura de vértices em um grafo dado.○ INSTÂNCIA: Grafo G;○ SAÍDA: Menor número K de tal forma que G tem

uma cobertura de vértices de tamanho K.

.

http://pt.wikipedia.org/w/index.php?title=Problema_de_otimiza%C3%A7%C3%A3o&action=edit&redlink=1


● Definição: Na Teoria dos grafos, uma cobertura de vértices de um grafo é um conjunto de vertices tal que cada aresta do grafo é incidente, a pelo menos, um vértice do conjunto.


● A versão de otimização do problema de cobertura de vértices consiste em encontrar a cobertura de vértices de um grafo que requer o menor número de vértices.○ A chamada cobertura de vértices ótima.


● Cobertura qualquer:

● Cobertura Mínima:


● Como seria uma heurística plausível para obter uma boa cobertura de vértices?○ Adicione os nós de maior grau a C até que todas as

arestas estejam cobertas.

● Esta heurística não é uma aproximação○ A sua relação de aproximação cresce a uma taxa

log n, em que n é o número de vértices.


● Para criarmos um algoritmo de aproximação neste caso, usaremos uma técnica que aparentemente é menos sofisticada do que aquela heurística.○ Comece com C Vazio; ○ Enquanto houver alguma aresta não coberta,

escolha arbitrariamente uma aresta (u,v), adiciona-a a um conjunto A, adicione u e v a C e os remova de G, juntamente com as demais arestas incidentes a elas.



● Quão distante do ótimo a cobertura de vértices obtida pode ser?○ A contém arestas de G, das quais, nenhuma

compartilha um mesmo vértice:■ É um emparelhamento.

○ Limitante: Uma cobertura de vértices ótima, obviamente contém pelo menos um vértice ligado a cada uma das arestas A:■ Senão alguma aresta não seria coberta;■ Então |C*|>= |A|.


● A cobertura de vértices C comtém os dois vértices de cada aresta em A, logo:

|C|=2|A|

● Combinando as duas equações, temos que:

|C|<=2|C*|


● Desta forma, este é um algoritmo de aproximação 2 de cobertura de vértices○ O tamanho da cobertura de vértice retornada é no

máximo 2 vezes maior do que a cobertura de vértices ótima.

● Ainda, o algoritmo é polinomial○ Consiste em remoção e adição de arestas e adição

de elementos em um conjunto.● Surpreedentemente, este é um dos

melhores algoritmos de aproximação para cobertura de vértices.

Referências Bibliográficas

● CORMEN, T. H., LEISERSON, C, E., RIVEST, R. L. e STEIN, C. “Algoritmos: Teoria e Prática”. 2ª ed. Ed. Campus, 2002.

● ZIVIANI, Nivio. "Projeto de Algoritmos com Implementações em Pascal e C". 3ª ed. Ed. Pioneira Thomson Learning, 2010.

Technology

Paa algoritmos gulosos