Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos gulosos - Coggle Diagram
Algoritmos gulosos
Algoritmo de Prim
Sejam dados n pontos, conecte eles da forma mais barata possível de modo que exista um caminho entre qualquer par de pontos
-
Pontos são representados pelos vértices do grafo, conexões são representadas pelas arestas, e o custo das conexões são os pesos das arestas
-
-
Algoritmo de Kruskal
Assim como o algoritmo de Prim, também gera uma solução ótima para árvores geradoras mínimas
A árvore geradora mínima de um grafo ponderado conexo vai ser um subgrafo acíclico com número de arestas |V|-1, onde a soma dos pesos das arestas é o menor possível
A árvore geradora mínima é construída como uma sequência de expansões de subgrafos acíclicos, porém não necessariamente conexos
Inicialmente, ordena-se as arestas do grafo em ordem não-decrescente de pesos
A partir do subgrafo vazio, escaneia-se a lista ordenada e adiciona nele o próximo elemento se a adição dele não criar um ciclo
Se a aresta (u, v) selecionada em cada iteração tiver árvores que contém ambas, e essas árvores não forem iguais, ela é adicionada a uma árvore maior junto com as arestas u e v
-
Algoritmos que tentam resolver problemas fazendo a escolha ótima no âmbito local, com a esperança de encontrar a solução ótima global após mais iterações