TG

Prévia do material em texto

UNIVERSIDADE FEDERAL DE ALAGOAS - UFAL
CAMPUS ARAPIRACA
GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
Maria Izabel Nunes de França
Matrícula: 20111693
Considere os Algoritmos de Prim, Kruskal e Christofides
● Descreva:
● Funcionamento
● Algoritmo de Prim: O algoritmo de Prim faz a construção da AGM de forma
incremental, escolhe um vértice arbitrário e, a cada repetição, seleciona a aresta
de menor peso que conecta um vértice da AGM a um vértice que ainda não foi
conectado. Esse processo se repete até que todos os vértices estejam conectados
à Árvore Geradora Mínima.
● Algoritmo de Kruskal: O algoritmo de Kruskal possui uma abordagem gulosa,
e funciona ordenando todas as arestas do grafo por peso crescente e adicionando
as mesmas à Árvore Geradora Mínima, desde que elas não criem um ciclo. Esse
passo deve ser repetido até que todas as arestas sejam conectadas.
● Algoritmo de Christofides: O algoritmo de Christofides utiliza o algoritmo de
Prim ou de Kruskal para gerar a AGM do grafo completo, e logo após ele realiza
a duplicação de algumas arestas que formam um ciclo com as arestas de menor
peso que não estão na AGM. Feito esse passo, ele encontrará o menor caminho
hamiltoniano no grafo que resulta após a duplicação das arestas.
● Limitações
● Algoritmo de Prim: O algoritmo de Prim não funcionam com grafos que
possuem arestas com pesos negativos, e também é muito lento para grafos que
possuem muitos vértices, já que a busca pelos vértices de menor peso pode
demorar muito, dessa forma se tornando ineficaz para essa situação.
● Algoritmo de Kruskal: O algoritmo de Kruskal pode ser ineficaz para grafos
com muitos arcos, pois a a verificação para checar se as arestas criam ciclos
pode ser muito demorada.
● Algoritmo de Christofides: O algoritmo de Christofides não garante encontrar
a AGM exata, porém apresenta uma solução aproximada com custo no máximo
50% maior que a AGM ideal. O algoritmo de Christofides pode ser ineficiente
para grafos com muitos vértices, pois encontrar o menor caminho de Hamilton é
um problema NP-difícil.
● Aplicações
● Algoritmo de Prim: O algoritmo de Prim tem as seguintes aplicações: redes de
comunicação, planejamento de rotas, problemas de menor custo em grafos
conexos.
● Algoritmo de Kruskal: O algoritmo de Kruskal tem as seguintes aplicações:
redes de transporte e problemas de otimização em grafos densos.
● Algoritmo de Christofides: O algoritmo de Cristofides tem as seguintes
aplicações: Planejamento de viagens e problemas que exigem soluções com
exatidão.
● Diferença de abordagem entre eles
Os algoritmos de Prim e Kruskal abordam a busca por árvores geradoras
mínimas de forma distinta. O algoritmo de Prim começa com um vértice inicial
e, de maneira gulosa, expande a árvore selecionando arestas de menor peso que
conectam o conjunto atual de vértices aos vértices fora dele. Essa abordagem
garante a construção de uma árvore mínima conectada. Por outro lado, Kruskal
seleciona as arestas de menor peso, evitando a formação de ciclos e garantindo
que a árvore permaneça acíclica. Essa abordagem baseada em conjuntos
disjuntos permite a construção eficiente da árvore geradora mínima,
independentemente do vértice inicial escolhido.