Algoritmo de Prim - Prim's algorithm

Uma demonstração para o algoritmo de Prim baseado na distância euclidiana

Na ciência da computação , o algoritmo de Prim (também conhecido como algoritmo de Jarník) é um algoritmo ganancioso que encontra uma árvore geradora mínima para um gráfico não direcionado ponderado . Isso significa que ele encontra um subconjunto de arestas que forma uma árvore que inclui todos os vértices , onde o peso total de todas as arestas da árvore é minimizado. O algoritmo opera construindo esta árvore um vértice de cada vez, a partir de um vértice inicial arbitrário, em cada etapa adicionando a conexão mais barata possível da árvore para outro vértice.

O algoritmo foi desenvolvido em 1930 por Tcheca matemático vojtěch jarník e mais tarde redescoberto e republicado por cientistas da computação Robert C. Prim em 1957 e Edsger W. Dijkstra em 1959. Por isso, é também chamado às vezes o algoritmo do Jarník , algoritmo de Prim-Jarník , Prim –Dijkstra algoritmo ou o algoritmo DJP .

Outros algoritmos bem conhecidos para este problema incluem o algoritmo de Kruskal e algoritmo de borůvka . Esses algoritmos encontram a floresta de abrangência mínima em um gráfico possivelmente desconectado; em contraste, a forma mais básica do algoritmo de Prim só encontra árvores geradoras mínimas em gráficos conectados. No entanto, executando o algoritmo de Prim separadamente para cada componente conectado do gráfico, ele também pode ser usado para encontrar a floresta de abrangência mínima. Em termos de sua complexidade de tempo assintótica , esses três algoritmos são igualmente rápidos para gráficos esparsos , mas mais lentos do que outros algoritmos mais sofisticados. No entanto, para gráficos suficientemente densos, o algoritmo de Prim pode ser executado em tempo linear , atendendo ou melhorando os limites de tempo de outros algoritmos.

O algoritmo de Prim começando no vértice A. Na terceira etapa, as arestas BD e AB têm peso 2, então BD é escolhido arbitrariamente. Após essa etapa, AB não é mais um candidato para adição à árvore porque vincula dois nós que já estão na árvore.

Descrição

O algoritmo pode ser descrito informalmente como realizando as seguintes etapas:

Inicialize uma árvore com um único vértice, escolhido arbitrariamente do gráfico.
Aumente a árvore em uma borda: das bordas que conectam a árvore aos vértices que ainda não estão na árvore, encontre a borda de peso mínimo e transfira-a para a árvore.
Repita a etapa 2 (até que todos os vértices estejam na árvore).

Em mais detalhes, ele pode ser implementado seguindo o pseudocódigo abaixo.

Associe a cada vértice v do gráfico um número C [ v ] (o custo mais barato de uma conexão av ) e uma aresta E [ v ] (a aresta fornecendo a conexão mais barata). Para inicializar esses valores, defina todos os valores de C [ v ] para + ∞ (ou para qualquer número maior que o peso máximo da borda) e defina cada E [ v ] para um valor de sinalizador especial indicando que não há nenhuma borda conectando v ao anterior vértices.
Inicialize uma floresta vazia F e um conjunto Q de vértices que ainda não foram incluídos em F (inicialmente, todos os vértices).
Repita as etapas a seguir até que Q esteja vazio:
1. Encontre e remova um vértice v de Q tendo o valor mínimo possível de C [ v ]
2. Adicione v a F e, se E [ v ] não for o valor do sinalizador especial, adicione também E [ v ] a F
3. Faça um loop sobre as arestas vw conectando v aos outros vértices w . Para cada uma dessas arestas, se w ainda pertence a Q e vw tem peso menor que C [ w ], execute as seguintes etapas:
  1. Defina C [ w ] para o custo da aresta vw
  2. Defina E [ w ] para apontar para a aresta vw .
Return F

Conforme descrito acima, o vértice inicial para o algoritmo será escolhido arbitrariamente, porque a primeira iteração do loop principal do algoritmo terá um conjunto de vértices em Q que têm todos pesos iguais, e o algoritmo iniciará automaticamente uma nova árvore em F quando completa uma árvore de abrangência de cada componente conectado do gráfico de entrada. O algoritmo pode ser modificado para se iniciar com qualquer nomeadamente vértice s , definindo C [ s ] a ser um número menor do que os outros valores de C (por exemplo, zero), e pode ser modificado para encontrar apenas uma única árvore de expansão em vez de uma floresta extensa inteira (combinando mais de perto com a descrição informal) parando sempre que encontra outro vértice sinalizado como sem aresta associada.

Diferentes variações do algoritmo diferem umas das outras em como o conjunto Q é implementado: como uma lista vinculada simples ou matriz de vértices, ou como uma estrutura de dados de fila de prioridade mais complicada . Essa escolha leva a diferenças na complexidade de tempo do algoritmo. Em geral, uma fila de prioridade será mais rápida em encontrar o vértice v com custo mínimo, mas implicará em atualizações mais caras quando o valor de C [ w ] mudar.

Complexidade de tempo

Tocar mídia

O algoritmo de Prim tem muitas aplicações, como na geração deste labirinto, que aplica o algoritmo de Prim a um gráfico de grade ponderado aleatoriamente .

A complexidade de tempo do algoritmo de Prim depende das estruturas de dados usadas para o gráfico e para ordenar as arestas por peso, o que pode ser feito usando uma fila de prioridade . A tabela a seguir mostra as opções típicas:

Estrutura de dados de peso mínimo da borda	Complexidade de tempo (total)
matriz de adjacência , pesquisando	${\ displaystyle O (\| V \| ^ {2})}$
heap binário e lista de adjacência	${\ displaystyle O ((\| V \| + \| E \|) \ log \| V \|) = O (\| E \| \ log \| V \|)}$
Heap de Fibonacci e lista de adjacência	${\ displaystyle O (\| E \| + \| V \| \ log \| V \|)}$

Uma implementação simples de Prim's, usando uma matriz de adjacência ou uma representação de gráfico de lista de adjacência e procurando linearmente uma matriz de pesos para encontrar a borda de peso mínimo a ser adicionada, requer tempo de execução O (| V | ² ). No entanto, esse tempo de execução pode ser melhorado ainda mais usando heaps para implementar a localização de bordas de peso mínimo no loop interno do algoritmo.

Uma primeira versão aprimorada usa um heap para armazenar todas as arestas do gráfico de entrada, ordenadas por seu peso. Isso leva a um tempo de execução de pior caso O (| E | log | E |). Mas armazenar vértices em vez de arestas pode melhorar ainda mais. O heap deve ordenar os vértices pelo menor peso de aresta que os conecte a qualquer vértice na árvore geradora mínima parcialmente construída (MST) (ou infinito se essa aresta não existir). Cada vez que um vértice v é escolhido e adicionado ao MST, uma operação de diminuição da chave é realizada em todos os vértices w fora do MST parcial de modo que v esteja conectado a w , definindo a chave para o mínimo de seu valor anterior e o custo de borda de ( v , w ).

Usando uma estrutura de dados de heap binário simples , o algoritmo de Prim pode agora ser mostrado para executar no tempo O (| E | log | V |) onde | E | é o número de arestas e | V | é o número de vértices. Usando um heap Fibonacci mais sofisticado , isso pode ser reduzido a O (| E | + | V | log | V |), que é assintoticamente mais rápido quando o gráfico é denso o suficiente para | E | é ω (| V |), e o tempo linear quando | E | é pelo menos | V | log | V |. Para gráficos de densidade ainda maior (tendo pelo menos | V | ^c arestas para algum c > 1), o algoritmo de Prim pode ser executado em tempo linear de forma ainda mais simples, usando um heap d -ary no lugar de um heap de Fibonacci.

Demonstração da prova. Neste caso, o gráfico Y ₁ = Y - f + e já é igual a Y . Em geral, o processo pode precisar ser repetido.

Prova de correção

Seja P um gráfico conectado e ponderado . A cada iteração do algoritmo de Prim, uma aresta deve ser encontrada que conecta um vértice em um subgrafo a um vértice fora do subgrafo. Como P está conectado, sempre haverá um caminho para cada vértice. A saída Y do algoritmo de Prim é uma árvore , porque a aresta e o vértice adicionados à árvore Y estão conectados. Seja Y ₁ uma árvore geradora mínima do gráfico P. Se Y ₁ = Y, então Y é uma árvore geradora mínima. Caso contrário, seja e a primeira aresta adicionada durante a construção da árvore Y que não está na árvore Y ₁ , e V seja o conjunto de vértices conectados pelas arestas adicionadas antes da aresta e . Então, um ponto final da aresta e está no conjunto V e o outro não. Como a árvore Y ₁ é uma árvore geradora do gráfico P , há um caminho na árvore Y _{1 que} une os dois pontos finais. À medida que se desloca ao longo do caminho, é preciso encontrar uma aresta f aderir a um vértice no conjunto V para um que não está em conjunto V . Agora, na iteração em que a aresta e foi adicionada à árvore Y , a aresta f também poderia ter sido adicionada e seria adicionada em vez da aresta e se seu peso fosse menor que e , e como a aresta f não foi adicionada, concluímos que

{\ displaystyle w (f) \ geq w (e).}

Seja a árvore Y ₂ o gráfico obtido removendo a aresta f e adicionando a aresta e à árvore Y ₁ . É fácil mostrar que a árvore Y ₂ está conectada, tem o mesmo número de arestas que a árvore Y ₁ , e o peso total de suas arestas não é maior do que o da árvore Y ₁ , portanto também é uma árvore geradora mínima do gráfico P e que contém borda de e e todas as arestas adicionados antes que durante a construção do conjunto V . Repetir os passos acima e que irá, eventualmente, obter uma cobertura mínima árvore de gráfico P que é idêntica à árvore Y . Isso mostra que Y é uma árvore de abrangência mínima. A árvore de abrangência mínima permite que o primeiro subconjunto da sub-região seja expandido em um subconjunto menor X , que assumimos ser o mínimo.

Algoritmo paralelo

A matriz de adjacência distribuída entre vários processadores para o algoritmo de Prim paralelo. Em cada iteração do algoritmo, cada processador atualiza sua parte de C inspecionando a linha do vértice recém-inserido em seu conjunto de colunas na matriz de adjacência. Os resultados são coletados e o próximo vértice a ser incluído no MST é selecionado globalmente.

O loop principal do algoritmo de Prim é inerentemente sequencial e, portanto, não pode ser paralelizável . No entanto, o loop interno , que determina a próxima aresta de peso mínimo que não forma um ciclo, pode ser paralelizado dividindo-se os vértices e arestas entre os processadores disponíveis. O pseudocódigo a seguir demonstra isso.

Atribua a cada processador um conjunto de vértices consecutivos de comprimento . ${\ displaystyle P_ {i}}$ ${\ displaystyle V_ {i}}$ ${\ displaystyle {\ tfrac {| V |} {| P |}}}$
Crie C, E, F e Q como no algoritmo sequencial e divida C, E, bem como o gráfico entre todos os processadores de forma que cada processador mantenha as arestas de entrada em seu conjunto de vértices. Deixe , denotar as partes de C , E armazenadas no processador . ${\ displaystyle C_ {i}}$ ${\ displaystyle E_ {i}}$ ${\ displaystyle P_ {i}}$
Repita as etapas a seguir até que Q esteja vazio:
1. Em cada processador: encontre o vértice com o valor mínimo em [ ] (solução local). ${\ displaystyle v_ {i}}$ ${\ displaystyle C_ {i}}$ ${\ displaystyle v_ {i}}$
2. Min-reduza as soluções locais para encontrar o vértice v com o valor mínimo possível de C [ v ] (solução global).
3. Transmita o nó selecionado para cada processador.
4. Adicionar v a F e, se E [ v ] não é o valor bandeira especial, também adicionar E [ v ] para F .
5. Em cada processador: atualização e como no algoritmo sequencial. ${\ displaystyle C_ {i}}$ ${\ displaystyle E_ {i}}$
Return F

Este algoritmo geralmente pode ser implementado em máquinas distribuídas, bem como em máquinas com memória compartilhada. Ele também foi implementado em unidades de processamento gráfico (GPUs). O tempo de execução é , supondo que as operações de redução e transmissão possam ser realizadas em . Uma variante do algoritmo de Prim para máquinas de memória compartilhada, na qual o algoritmo sequencial de Prim está sendo executado em paralelo, a partir de vértices diferentes, também foi explorada. Deve-se, no entanto, notar que existem algoritmos mais sofisticados para resolver o problema da árvore geradora mínima distribuída de uma maneira mais eficiente. ${\ displaystyle O ({\ tfrac {| V | ^ {2}} {| P |}}) + O (| V | \ log | P |)}$ ${\ displaystyle O (\ log | P |)}$

Veja também

O algoritmo de Dijkstra , um algoritmo muito semelhante para o problema do caminho mais curto
Greedoids oferecem uma maneira geral de entender a correção do algoritmo de Prim

Referências

links externos

Progresso do algoritmo de Prim em pontos distribuídos aleatoriamente
Mídia relacionada ao algoritmo de Prim no Wikimedia Commons

Languages

In other projects