Please enable JavaScript.
Coggle requires JavaScript to display documents.
Greedy Algorithm (algoritmo guloso) - Coggle Diagram
Greedy Algorithm (algoritmo guloso)
Algoritmo de Prim
O problema: sejam dados
n
vértices, conecte-os do jeito mais barato possível, de forma que exista um caminho entre todos os vértices do grafo. Essas conexões seriam feitas por arestas, e seus custos dependeriam dos seus respectivos pesos.
Esse problema se chama: problema de árvore geradora mínima.
Uma
árvore geradora
de um grafo conectado e não-direcionado é seu sub-grafo conectado acíclico (uma árvore) que contém todos os vértices do grafo.
Se esse grafo tiver pesos atribuídos às suas arestas, uma
árvore geradora mínima
seria sua árvore geradora de menor peso, onde o peso de uma árvore é definido como a soma de todos os pesos em todas as suas arestas.
O
problema de árvore geradora mínima
é o problema onde deve-se encontrar a árvore geradora mínima de um dado grafo conectado e com pesos.
Esse problema é resolvido com o
algoritmo de Prim
.
O algoritmo de Prim constrói a árvore geradora mínima através de uma sequência de sub-árvores de expansão.
A sub-árvore inicial nesta sequência consiste em um único vértice, selecionado arbitrariamente do grupo
V
, que contém os vértices de um grafo.
A cada iteração o algoritmo expande a árvore atual, simplesmente, juntando o vértice mais próximo, que não está na árvore, e que está conectado por uma aresta de menor peso.
O algoritmo para depois que todos os vértices estiverem na árvore sendo construída.
Já que o algoritmo expande a árvore em exatamente um vértice a cada iteração, o número total de suas iterações é de
n - 1
, onde
n
é a qtde. de vértices no grafo.
A natureza do algoritmo de Prim faz necessário fornecer, para cada vértice que não está na árvore, a informação sobre a menor aresta que conecta um vértice no grafo à um vértice da árvore.
Essa informação é fornecida atribuindo dois rótulos à um vértice: o nome do vértice de árvore mais próximo e o peso da sua aresta.
Vértices que não são adjacentes à nenhum vértice da árvore recebem o rótulo infinito, que indica sua distância "infinita" dos vértices da árvore, e, o rótulo null como nome do vértice de árvore mais próximo.
Com esses rótulos, encontrar o próximo vértice a ser adicionado à árvore
T
= (
Vᵀ, Eᵀ
) se torna uma tarefa simples de encontrar o vértice com o menor rótulo de distância no conjunto
V - Vᵀ
.
Quão eficiente é o algoritmo de Prim?
Depende da estrutura de dados escolhida para representar o grafo, e da fila de prioridade do grupo
V - Vᵀ
, sobre a qual as prioridades dos vértices são as distâncias da árvore de vértices mais próxima.
Se o grafo for representado por uma matriz de peso e sua fila de prioridade for implementada como um array desordenado, o tempo de execução do algoritmo vai estar em Θ(|
V
|²). A cada |
V
| - 1 iterações, o array implementando a fila de prioridade é atravessado para encontrar e deletar o mínimo, e então atualizar, se necessário, as prioridades dos vértices restantes.
Se o grafo for representado por uma lista de adjacência e sua fila de prioridade for implementada como uma min-heap, o tempo de execução do algoritmo vai estar em
O
(|
E
| log |
V
|). Isso porque o algoritmo deleta o menor elemento |
V
| - 1 vezes, e faz |
E
| verificações, e, possivelmente troca a prioridade de um elemento em uma min-heap de tamanho que não excede |
V
|.
Algoritmo de Kruskal
O algoritmo de Kruskal também resolve o problema de árvore geradora mínima.
Ele olha a árvore geradora mínima de um grafo conectado
G = (V, E)
, como um sub-grafo acíclico com |
V
| - 1 arestas das quais a soma de seus pesos é a menor.
Consequentemente, o algoritmo constrói a árvore geradora mínima como uma sequência de sub-grafos que se expande e são sempre acíclicas, mas não são necessariamente conectadas em estágios intermediários do algoritmo.
O algoritmo começa organizando as arestas do grafo em ordem crescente de seus pesos. Então, começando com o sub-grafo vazio, ele escaneia essa lista ordenada, adicionando a próxima aresta na lista para o sub-grafo se a inclusão não criar um ciclo, e simplesmente pulando a aresta se criar.
A cada iteração, o algoritmo de Kruskal checa se a adição da próxima aresta às arestas já selecionadas criariam um ciclo.
E, um novo ciclo é criado se, e somente se, a nova aresta conectar dois vértices que já foram conectados por um caminho.
Em vista dessas observações, é conveniente usar uma interpretação diferente do algoritmo de Kruskal.
Nós podemos considerar as operações do algoritmo como uma progressão através de uma série de florestas contendo
todos
os vértices de um dado grafo e
algumas
das suas arestas.
A floresta inicial consiste em |
V
| árvores triviais, cada uma comportando um único vértice do grafo.
A floresta final consiste em uma única árvore, que é a árvore geradora mínima.
A cada iteração o algoritmo pega a próxima aresta (
u, v
) da lista ordenada das arestas do grafo, encontra as árvores que contêm os vértices
u
e
v
, e, se essas árvores não forem as mesmas, as une em uma árvore maior adicionando a aresta (
u, v
).
Felizmente, existem algoritmos que conseguem checar se dois vértices pertencem à mesma árvore. Eles são chamados de algoritmos
union-find (união-busca)
.
Com um algoritmo union-find eficiente, o tempo de execução do algoritmo de Kruskal seria dominado pelo tempo necessário à ordenação dos pesos das arestas do grafo.
Portanto, com um algoritmo de ordenação eficiente, a eficiência temporal do algoritmo de Kruskal vai estar em
O
(|
E
| log |
E
|).
Algoritmos union-find e subconjuntos disjuntos
O algoritmo de Kruskal é uma aplicação entre várias que requerem uma partição dinâmica de um elemento
n
pertencente a um conjunto
S
em uma coleção de subconjuntos disjuntos
S1
,
S2
, ...,
S
ₖ.
Depois de ser inicializado como subconjuntos
n
de 1 elemento, cada um contendo um elemento diferente de
S
,a coleção é sujeitada a uma sequência de operações de união e busca misturadas.
Portanto, o que se tem é um tipo de dados abstrato de subconjuntos disjuntos de um conjunto finito com as seguintes operações:
makeset(x)
cria um conjunto de 1 elemento {
x
}. Presume-se que essa operação pode ser aplicada para cada um dos elementos dos conjunto
S
somente uma vez.
find(x)
retorna o subconjunto que contém
x
.
union(x, y)
constrói a união dos subconjuntos disjuntos
S
ₓ e
Sy
que contêm, respectivamente,
x
e
y
, e adiciona essa união à coleção para substituir
S
ₓ e
Sy
, que são deletados de lá.
A maioria das representações desse tipo abstrato de dados usam um elemento de cada subconjunto disjunto em uma coleção como se fosse o
representante
desse subconjunto.
Algumas implementações não colocam nenhuma condição específica nesses representantes; outras, sim, por exemplo, exigindo que o menor elemento de cada subconjunto seja usado como seu representante.
Usualmente, esse conjunto de elementos são números inteiros.
Existem duas principais alternativas para implementar essa estrutura de dados. A primeira é chamada de
quick find (busca rápida)
que otimiza a eficiência temporal da operação de busca; e a segunda é chamada de
quick union (união rápida)
que otimiza a operação de união.
Quick Find (busca rápida)
A quick find usa um array indexado pelos elementos do conjunto
S
subjacente; os valores do array indicam os representantes dos subconjuntos que contêm esses elementos.
Cada subconjunto é implementado como uma lista ligada, onde sua header contém os apontadores para o primeiro e último elemento da lista, juntamente com a qtde. de elementos na lista.
Nesse esquema, a implementação do
makeset(x)
requere a atribuição do elemento correspondente no array representativo para
x
, e a inicialização da lista ligada correspondente para um único nó com o valor
x
.
A eficiência temporal desta operação está em Θ(1), e, por conseguinte, a inicialização de
n
subconjuntos de 1 elemento está em Θ(
n
).
A eficiência do
find(x)
também está em Θ(1), pois, é necessário somente pegar o representante de
x
no array representativo.
Porém, a operação de
union(x, y)
leva mais tempo.
Uma solução direta seria anexar a lista
y
ao final da lista
x
, atualizar a informação sobre seu representante para todos os elementos da lista
y
, e então, deletar a lista
y
da coleção. Porém, essa operação estaria em Θ(
n
²).
Um jeito simples de melhorar a eficiência de uma sequência de operações de união é sempre anexar a menor lista na lista maior. Essa modificação é chamada de
union by size (união por tamanho)
.
Porém ela não melhora a eficiência no pior caso de uma única aplicação da operação de união, que vai estar em Θ(
n
). Então, o tempo de execução de qualquer sequência de operações de union-by-size, no pior caso, vai estar sempre em
O
(
n
log
n
).
Sendo assim, para a union by size, a eficiência temporal de uma sequência de no máximo
n - 1
uniões e
m
buscas está em
O
(
n
log
n + m
).
Quick union (união rápida)
É a segunda principal alternativa para implementar subconjuntos disjuntos, e representa cada subconjunto como uma árvore enraizada.
Os nós da árvore contêm os elementos do subconjunto, com a raiz da árvore sendo o representante do subconjunto; as arestas da árvore são direcionadas dos seus filhos para seus pais.
Para esta implementação, a operação
makeset(x)
requere a criação de uma árvore de um único nó, que está em Θ(1). Portanto, a inicialização de
n
subconjuntos de 1 elemento está em Θ(
n
).
A operação de
union(x, y)
é implementada anexando a raiz da árvore
y
à raíz da árvore
x
, e então, deletando a árvore
y
da coleção fazendo o apontador da sua raíz nulo).
A eficiência temporal da operação de união é claramente Θ(1).
A operação
find(x)
é desempenhada seguindo a cadeia de apontadores do nó contendo
x
até a raiz da árvore do qual o elemento é retornado como o representante do subconjunto.
Portanto, a eficiência temporal de uma única operação de busca está em
O
(
n
) porque a árvore representando um subconjunto pode se degenerar em uma lista ligada com
n
nós.
Um jeito direto de melhorar esse tempo seria sempre realizar uma operação de união anexando a árvore menor à raiz da maior árvore.
O tamanho de uma árvore pode ser medido pela sua qtde. de nós(
union by size
), ou pela sua altura(
union by rank
).
É claro que essas opções requerem um armazenamento, para cada nó, ou da qtde. de nós descendentes, ou da altura da sub-árvore enraizada naquele nó, respectivamente.
Em ambos os casos, a altura da árvore vai ser logarítmica , fazendo possível executar cada operação de busca em
O
(log
n
).
Sendo assim, para a quick union, a eficiência temporal da sequência de no máximo
n - 1
uniões e
m
buscas está em
O
(
n
+
m
log
n
).
Uma eficiência melhor pode ser obtida combinando qualquer variedade de quick union com
path compression (compressão de caminho)
. Essa modificação faz com que cada nó encontrado durante a execução da operação de busca aponte para a raiz da árvore. Essas e outra técnicas similares melhoram a eficiência para somente um pouco pior que a linear.