Pular para o conteúdo principal

Trabalho 2 - Árvores Geradoras Mínimas com Prim


Trabalho 2
Algoritmo
 O algoritmo de Prim é um algoritmo greedy que tem como objetivo encontrar uma árvore geradora mínima num grafo conectado, valorado e não direcionado; ou seja, o algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimzada e todos os vértices estão interligados.

Uma Árvore Geradora Mínima de G é qualquer árvore geradora que tenha custo mínimo, ou, melhor dizendo, uma árvore geradora A de G é mínima se nenhuma outra árvore geradora deste grafo tenha custo menor do que o de A.

O projeto foi desenvolvido na linguagem Python e as bibliotecas NumPy, NetworkX e PyPlot, além da IDE Anaconda.


Algoritmo implementado



Execução

Para a execuçao do algoritmo, temos o conjunto de vértices que ainda não entraram no subgrafo, o conjunto dos vértices que já estão no subgrafo, as arestas possíveis (lista de arestas que poderiam ser incluidas, pois conectam vértices contidos no subgrafo com aquelas que ainda não estão no mesmo) e as arestas incluídas, que já estão no subgrafo. 
Utilizando essas noções e acompanhando o algoritmo , para que seja escolhida uma aresta segura deve-se observar o conjunto de arestas possíveis e selecionar aquelas que não formam ciclos com o subgrafo formado até o momento, e cujo peso é o mínimo dentre as opções. Se uma aresta atender a estes resquisitos, ela é considerada segura e o algoritmo se segue.

Árvore Geradora Mínima do Grafo G

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Trabalho 3 - Busca em Largura e Profundidade (BFS e DFS)

Trabalho 3 Contexto Antes de introduzirmos os algoritmos de Busca em Largura e Profundidade (BFS e DFS), vistos em sala de aula, é preciso relembrar o funcionamento de uma busca dentro de um grafo. Para realizar qualquer busca, é necessário trabalhar com um algoritmo que percorra todas as arestas e vértices de um dado grafo, realizando uma análise sistemática de todos os caminhos e nós encontrados. Após realizar a primeira inspeção, na ponta inicial, o algoritmo deve percorrer até encontrar a ponta final, examinando a cada passo, no máximo, uma vez cada aresta. Uma busca pode ser realizada de diversas maneiras. Nesse tópico, será introduzida a Busca em Largura (BFS) e a Busca em Profundidade (DFS). Algoritmo de Busca em Largura (BFS) A BFS inicia-se num vértice inicial V0 de um grafo G não ponderado. Seu retorno deve ser uma árvore T (BFS-tree), a qual possui os menores caminhos de V0 aos demais vértices. Através deste algoritmo, realiza-se a visita de V0 e seus demais viz...
Postar um comentário
Leia mais

Trabalho 5 - O Problema do Caixeiro Viajante

Trabalho 5 Contexto O Problema do Caixeiro Viajante (TSP) faz a seguinte pergunta: "Dada uma lista de cidades e distância entre cada par delas, qual é a distância mínima possível em que o Caixeiro Viajante poderia visitar todas as cidades exatamente uma vez e retornar à sua de origem?". Esse é um problema de nível NP-Hard (onde não há um algoritmo ótimo para a resolução do mesmo) da otimização computacional, importante em operações de pesquisa e ciência da computação teórica. Um grafo G é dito um  Grafo Hamiltoniano  se existe um ciclo no mesmo que contenha todos os seus vértices, sendo que cada vértice só aparece uma vez no ciclo, que é chamado de Ciclo Hamiltoniano; sendo assim, um grafo é hamiltoniano caso contenha um ciclo hamiltoniano. Execução O objetivo deste trabalho é, utilizando um dos algoritmos apresentados em sala para o TSP (Twice-around ou 2-otimal) e um grafo fornecido, encontrar 10 possíveis soluções para o Problema do Caixeiro Viajante e elenc...
Postar um comentário
Leia mais