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

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.

Seleção de Atividades

Seleção de Atividades

Seleção de Atividades

Seleção de Atividades

Seleção de Atividades

Seleção de Atividades

Seleção de Atividades

Seleção de Atividades

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;

Relação de Aproximação

● 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;

Relação de Aproximação

● 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.

Cobertura de Vértices

● 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.

.

Cobertura de Vértices

● 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.

Cobertura de Vértices

● 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 de Vértices

● Cobertura qualquer:

● Cobertura Mínima:

Cobertura de Vértices

● 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.

Cobertura 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.

Cobertura de Vértices

Cobertura de Vértices

● 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|.

Cobertura de Vértices

● 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*|

Cobertura de Vértices

● 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.