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 1 - Snakes and Ladders

Trabalho 1 Contexto Snakes and Ladders é um antigo jogo de tabuleiro indiano, que hoje faz sucesso no mundo todo. Ele é jogado por dois ou mais jogadores em um mapa quadriculado onde cada um dos quadrados possui um número. Uma certa quantidade de "escadas" (ladders) e "cobras" (snakes) é desenhada no tabuleiro, conectando dois quadrados específicos do mapa. O objetivo do jogo é ir até o final do mapa de acordo com o número tirado na moeda (um ou dois), e assim, avançando as casas. Caso caia em alguma casa onde está a base de uma escada, o jogador a sobe até a próxima posição - o semelhente acontece com as cobras, com a diferença de que o jogador desce para uma posição anterior caso caia numa casa onde está desenhada a cabeça da cobra. Objetivos Para este projeto há três objetivos especificados: 1. Apresentar o diagrama de estados da Cadeia de Markov que representa o jogo, computando, para isso, a matriz de transição de estados P. ...

Grafos

Pesquisar este blog