Algoritmo de Prim

Da Wikipédia, a enciclopédia livre
Ir para navegação Pular para pesquisar
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 pelo matemático tcheco Vojtěch Jarník [1] e mais tarde redescoberto e republicado pelos cientistas da computação Robert C. Prim em 1957 [2] e Edsger W. Dijkstra em 1959. [3] Portanto, às vezes também é chamado de O algoritmo de Jarník , [4] algoritmo Prim – Jarník , [5] algoritmo Prim – Dijkstra [6] ou o algoritmo DJP . [7]

Outros algoritmos bem conhecidos para este problema incluem o algoritmo de Kruskal e algoritmo de borůvka . [8] Esses algoritmos encontram a floresta de abrangência mínima em um grafo 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. [9] Em termos de sua complexidade assintótica de tempo , esses três algoritmos são igualmente rápidos para gráficos esparsos , mas mais lentos do que outros algoritmos mais sofisticados. [7] [6] 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. [10]

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 a adição à árvore, pois vincula dois nós que já estão na árvore.

Descrição

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

  1. Inicialize uma árvore com um único vértice, escolhido arbitrariamente do gráfico.
  2. 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.
  3. 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.

  1. 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 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.
  2. 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).
  3. 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 .
  4. 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 começar com qualquer vértice particular s definindo C [ s ] como um número menor que os outros valores de C(por exemplo, zero), e pode ser modificado para encontrar apenas uma única árvore geradora em vez de uma floresta geradora inteira (correspondendo mais de perto à descrição informal), parando sempre que encontrar outro vértice sinalizado como sem aresta associada.

Diferentes variações do algoritmo diferem umas das outras na forma como o conjunto Q é implementado: como uma lista encadeada 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

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
heap binário e lista de adjacência
Heap de Fibonacci e lista de adjacência

Uma implementação simples de Prim's, usando uma matriz de adjacência ou uma representação gráfica de lista de adjacências e procurando linearmente um array de pesos para encontrar a borda de peso mínimo a adicionar, requer tempo de execução O (| V | 2 ). No entanto, esse tempo de execução pode ser muito 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 de 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 d-ary heap no lugar de uma heap de Fibonacci. [10] [11]

Demonstração da prova. Neste caso, o gráfico Y 1 = 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 1 uma árvore geradora mínima do gráfico P. Se Y 1 = Y, então Y é uma árvore geradora mínima. Caso contrário, seja e a primeira aresta adicionada durante a construção da árvore Yque não está na árvore Y 1 , e V é 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 1 é 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 quando a aresta e foi adicionada à árvore Y , a aresta ftambém poderia ter sido adicionado e seria adicionado em vez da aresta e se seu peso fosse menor que e , e uma vez que a aresta f não foi adicionada, concluímos que

Seja a árvore Y 2 o gráfico obtido removendo a aresta f e adicionando a aresta e à árvore Y 1 . É fácil mostrar que a árvore Y 2 está conectada, tem o mesmo número de arestas que a árvore Y 1 , e o peso total de suas arestas não é maior que o da árvore Y 1 , 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 . Repita as etapas acima e, eventualmente, obteremos uma árvore de abrangência mínima do gráfico Pque é 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. [12] O seguinte pseudocódigo demonstra isso.

  1. Atribuir cada processador um conjunto de vértices consecutivos de comprimento .
  2. 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. Deixar, denotam as partes de C , E armazenadas no processador.
  3. Repita as etapas a seguir até que Q esteja vazio:
    1. Em cada processador: encontre o vértice tendo o valor mínimo em [] (solução local).
    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.
  4. Return F

Este algoritmo pode geralmente ser implementado em máquinas distribuídas [12] , bem como em máquinas com memória compartilhada. [13] O tempo de execução é, assumindo que as operações de redução e transmissão podem ser realizadas em. [12] Uma variante do algoritmo de Prim para máquinas de memória compartilhada, em que o algoritmo sequencial de Prim está sendo executado em paralelo, a partir de vértices diferentes, também foi explorada. [14] Deve-se, entretanto, notar que algoritmos mais sofisticados existem para resolver o problema da árvore geradora mínima distribuída de uma maneira mais eficiente.

Veja também

Referências

  1. ^ Jarník, V. (1930), "O jistém problemsu minimálním" [Sobre um certo problema mínimo], Práce Moravské Přírodovědecké Společnosti (em tcheco), 6 (4): 57-63, hdl : 10338.dmlcz / 500726.
  2. ^ Prim, RC (novembro de 1957), "Shortest connection networks And some generalizations" , Bell System Technical Journal , 36 (6): 1389-1401, Bibcode : 1957BSTJ ... 36.1389P , doi : 10.1002 / j.1538-7305.1957 .tb01515.x.
  3. ^ Dijkstra, EW (dezembro de 1959), "A note on two problems in connexion with graphs" (PDF) , Numerische Mathematik , 1 (1): 269–271, CiteSeerX 10.1.1.165.7577 , doi : 10.1007 / BF01386390 , S2CID 123284777   .
  4. ^ Sedgewick, Robert ; Wayne, Kevin Daniel (2011), Algorithms (4ª ed.), Addison-Wesley, p. 628, ISBN 978-0-321-57351-3.
  5. ^ Rosen, Kenneth (2011), Discrete Mathematics e suas aplicações (7o ed.), McGraw-Hill Science, p. 798.
  6. ^ a b Cheriton, David ; Tarjan, Robert Endre (1976), "Finding minimum spanning trees", SIAM Journal on Computing , 5 (4): 724-742, doi : 10.1137 / 0205051 , MR 0446458 .
  7. ^ a b Pettie, Seth; Ramachandran, Vijaya (janeiro de 2002), "Um algoritmo de árvore de abrangência mínima ideal" (PDF) , Journal of the ACM , 49 (1): 16–34, CiteSeerX 10.1.1.110.7670 , doi : 10.1145 / 505241.505243 , MR 2148431 , S2CID 5362916    .
  8. ^ Tarjan, Robert Endre (1983), "Capítulo 6. Árvores geradoras mínimas. 6.2. Três algoritmos clássicos", Estruturas de dados e algoritmos de rede , CBMS-NSF Regional Conference Series in Applied Mathematics, 44 , Society for Industrial and Applied Mathematics , pp . 72-77.
  9. ^ Kepner, Jeremy; Gilbert, John (2011), Graph Algorithms in the Language of Linear Algebra , Software, Environments, and Tools, 22 , Society for Industrial and Applied Mathematics , p. 55, ISBN 9780898719901.
  10. ^ a b Tarjan (1983) , p. 77
  11. ^ Johnson, Donald B. (dezembro de 1975), "Priority queues with update and Find Minimum Spanning Trees ", Information Processing Letters , 4 (3): 53–57, doi : 10.1016 / 0020-0190 (75) 90001-0.
  12. ^ a b c Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, Vipin (2003), Introdução à Computação Paralela , pp. 444-446, ISBN 978-0201648652
  13. ^ Quinn, Michael J .; Deo, Narsingh (1984), "Parallel graph algoritms", ACM Computing Surveys , 16 (3): 319-348, doi : 10.1145 / 2514.2515 , S2CID 6833839 
  14. ^ Setia, Rohit (2009), "Um novo algoritmo paralelo para o problema da árvore geradora mínima", Proc. Conferência Internacional sobre Computação de Alto Desempenho (HiPC)

Ligações externas