Método Guloso
44 pág.

Método Guloso


DisciplinaAnálise de Algoritmos191 materiais713 seguidores
Pré-visualização2 páginas
Análise de Algoritmos
MÉTODO GULOSOMÉTODO GULOSO
Bacharelado em Ciência da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Novembro de 2015
 
Sumário
\u25cf Motivação
\u25cf Exemplo de Utilização
\u25cf Elementos Fundamentais
\u25cf Leitura Recomendada
 
Motivação
\u25cf Para vários problemas de otimização, 
descobrir as melhores escolhas pode ser 
um exagero
\u25cf Podemos utilizar algoritmos mais simples e 
eficientes
\u25cf Um algoritmo guloso faz uma escolha 
ótima para as condições locais, visando 
uma solução ótima global
 
Por que Guloso?
\u25cf Os algoritmos baseados no Método Guloso 
escolhem, a cada passo, o candidato mais 
evidente que possa ser adicionado à solução
\u25cf Decisões são tomadas de forma isolada, a 
cada passo
\u25cf Estratégia   \u2192 escolher o melhor, no momento
 
SOLUÇÃO ÓTIMA LOCAL
 
Exemplo
Escalonamento de Tarefas
\u25cf Descrição: Seja T um conjunto de n 
tarefas. Associamos a cada tarefa, um 
tempo de execução e realizamos o 
escalonamento de tarefas
\u25cf Problema: Minimizar o tempo médio de 
execução das tarefas
\u25cf Sequência de decisões: escolher primeira 
tarefa, escolher segunda tarefa, ... 
 
Exemplo
Escalonamento de Tarefas
\u25cf Seja T = {(T1,15), (T2,8), (T3,3), (T4,10)}
\u25cf Considerar um único processador e alocação 
não preemptiva
\u25cf Estratégia gulosa 1: ordem de chegada
\u25cf Estratégia gulosa 2: ordem crescente de 
tempo de execução
 
Sumário
\u25cf Motivação
\u25cf Exemplo de Utilização
\u25cf Elementos Fundamentais
\u25cf Leitura Recomendada
 
Exemplo 
Árvores Espalhadas Mínimas
\u25cf Árvore é um grafo não­direcionado, conexo 
e acíclico
\u25cf Propriedades relevantes de grafos/árvores
\u25cf Qualquer grafo não­direcionado, conexo, G = 
(V,A) com |A| = |V| \u2013 1 é uma árvore
\u25cf Um grafo não­direcionado é uma árvore se e 
somente se existe um único caminho entre 
qualquer par de nós
 
Formalização do Problema
\u25cf Entrada: grafo não­direcionado G = (V, A), 
com pesos de arestas wa
\u25cf Saída: árvore T = (V, A'), onde A' \u2286 A que 
minimiza 
\u25cf peso(T) = \u2211wa, onde a \u2208 A' 
 
Exemplo de Instância do Problema
B
1
4
4
3 4
2 4
6
5
A C E
FD
 
Aplicando o Método Guloso
\u25cf O algoritmo de Kruskal inicia com um 
grafo vazio e seleciona arestas de A de 
acordo com a regra
\u25cf Repetidamente, selecione a próxima aresta 
mais leve que não produz um ciclo
\u25cf A árvore é construída aresta por aresta   \u2192
escolhendo sempre a aresta mais barata 
no momento!
 
Tempo de Execução do Algoritmo 
de Kruskal
KRUSKAL (G, w)
Entrada: Grafo não­direcionado conexo com pesos de arestas wa
Saída: Árvore espalhada mínima definida pelas arestas T
para cada vértice v \u2208  V   O(V)\u2192
  faça construirConjunto(v) //Cria conjunto contendo apenas v
T = { }    O(1)\u2192
ordenar as arestas de A por peso crescente   O(AlgA)\u2192
para cada aresta (u,v)   A\u2208 , em ordem de peso crescente   O(A)\u2192
  faça se encontrar(u) != encontrar(v) //a qual conjunto u 
pertence? 
    entao T = T   \u22c3 {(u,v)} //adiciona aresta à arvore
      unir(u,v) //une os conjuntos contendo u e v
return T
 
Usando o Algoritmo de Kruskal
\u25cf Começamos com um grafo vazio e 
tentamos adicionar arestas em ordem 
crescente de peso (empates são 
decididos arbitrariamente)
B
6
5
2
4 1
2
3
4
4
A C E
FD
5
 
Usando o Algoritmo de Kruskal
B
6
5
2
4 1
2
3
4
4
A C E
FD
5
\u25cf Vamos iniciar por B
 
Usando o Algoritmo de Kruskal
\u25cf B­C é escolhida
B
6
5
2
4 1
2
3
4
4
A C E
FD
5
B
1
C
\u2192 
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos C
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
\u25cf C­D é escolhida
\u2192 
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
B
1
C
D
2
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos B­D
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
B-D é descartado, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos C­F
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
\u25cf C­F é escolhida
\u2192 
B
1
C
D
2
F
3
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos F
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
\u25cf E­F é escolhida
\u2192 
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
B
1
C
D
2
F
3
E
4
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos D­F
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
D-F é descartado, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos A
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
 
Usando o Algoritmo de Kruskal
\u25cf A­D é escolhida
B
6
5
4 1
2
3
4
A
FD
5
C E
\u2192 
B
1
C
D
2
F
3
E
4
A
4
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos A­B
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
A-B é descartada, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos C­E
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
C-E é descartada, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
\u25cf Consideramos A­C
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
A-C é descartada, pois 
produziria um ciclo
 
Usando o Algoritmo de Kruskal
\u25cf Resultado: árvore espalhada mínima, de 
custo 14
\u2192 
B
6
5
2
4 1
2
3
4
4
A
FD
5
C E
B
1
C
D
2
F
3
E
4
A
4
 
Sumário
\u25cf Motivação
\u25cf Exemplo de Utilização
\u25cf Elementos Fundamentais
\u25cf Leitura Recomendada
 
Elementos Fundamentais
\u25cf Propriedades exibidas pela maioria dos 
problemas aos quais podemos empregar 
o MG
\u25cf Escolha gulosa: Uma solução ótima global 
pode ser obtida a partir de escolhas ótimas 
locais (gulosas)
\u25cf Subestrutura ótima: Uma solução ótima 
contém em si, soluções ótimas para os 
subproblemas
 
Consequências da Escolha Gulosa
\u25cf A escolha pode depender das escolhas 
até o momento, mas não depende de 
nenhuma escolha futura ou de soluções 
para subproblemas
\u25cf MG faz uma escolha gulosa após outra, 
reduzindo de modo iterativo cada instância 
do problema para um problema menor
\u25cf Frequentemente, a escolha gulosa fornece 
alguma eficiência
 
Programação Dinâmica x Método 
Guloso
\u25cf PD particiona o problema em subproblemas 
dependentes (subproblemas compartilham 
subproblemas), resolvendo cada subproblema 
apenas uma vez e armazenando as soluções em uma 
estrutura de dados, para resolver o problema original
\u25cf Bottom­up
\u25cf MG obtém uma solução para um problema fazendo 
uma sequência de escolhas independentes (para 
cada decisão, a melhor opção é escolhida) para obter 
apenas um subproblema a resolver
\u25cf Top­down
 
Programação Dinâmica x Método 
Guloso
\u25cf Há sutilezas advindas do uso de 
subestrutura ótima
\u25cf Vamos considerar 2 variantes do 
problema da mochila
\u25cf Problema da mochila 0­1 (binária)
\u25cf Problema da mochila fracionária
 
Exemplo
Problema da Mochila
\u25cf Um ladrão que rouba uma loja encontra n itens: o 
i­ésimo item vale vi reais e pesa wi kg, onde vi e wi 
são inteiros
\u25cf Ele deseja levar uma carga o mais valiosa 
possível, mas pode carregar no máximo W kg em 
sua mochila
\u25cf Que itens ele deve levar?
\u25cf Mochila 0­1 (binária), em que cada item deve ser 
levado ou deixado (o ladrão não pode levar frações)
\u25cf Mochila