Trabalho 4 - Árvores de Caminhos Mínimos e Agrupamento de Dados

Trabalho 4

Algoritmo

O algoritmo de Dijkstra, desenvolvido pelo cientista da computação holandês Edsger Dijkstra, soluciona o problema do caminho mais curto num grafo com arestas de peso não negativo. O algoritmo considera um conjunto S de caminhos mínimos, iniciado por um vértice inicial; à cada passo, é buscado nos vértices adjacentes pertencentes a S aquele que possua a menor distância relativa ao vértice inicial, o adicionando, então, a S também. Os passos são repetidos até que todos os vértices alcançáveis pelo vértice inicial estejam em S.

Execução

Tendo o algoritmo implementado, uma maneira para gerar subárvores de caminhos mínimos é atribuir custo inicial zero a um número n de vértices, mantendo o resto do algoritmo da mesma maneira como estava antes.
O resultado será um processo onde cada uma das raízes "competem" entre si para verificar qual delas se ligará ao próximo vértice do grafo; ao final da execução do algoritmo, haverão vários grupos de nós similares às MST's, com a única diferença sendo a supervisão no processo de formação desses grupos.

O código para esse algoritmo foi escrito na linguagem Python e foram utilizadas as bibliotecas NumPy e Networkx, além da IDE Anaconda.

Parte 1 do Algoritmo de Dijkstra

Parte 2 do Algoritmo de Dijkstra

Á partir dessa implementação, então, foram encontrados os seguintes resultados:

a) Um agrupamento, G1 = (0, 0, 0)

Grafo G1

b) Dois agrupamentos, G2 = (0, 0, 58)

Grafo G2

c) Três agrupamentos, G3 = (0, 29, 58)

Grafo G3

Comentários

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...

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...

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 qu...

Grafos

Pesquisar este blog