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

Algoritmo de Dijkstra

O que o algoritmo faz é criar uma fila de prioridades para organizar os vértices de modo que quanto menor o custo maior a prioridade do vértice em questão. Assim, a ideia é expandir primeiramente os menores ramos da árvore de caminhos mínimos, na expectativa de que os caminhos mínimos mais longos usarão como base os subcaminhos obtidos anteriormente.

Metodologia

Após a implementação do algoritmo, uma forma de crescer várias subárvores de caminhos mínimos é inicializar várias "sources", ou seja, atribuir custo inicial zero a um número K de vértices. O restante do algoritmo permanece intacto. O que irá acontecer é um processo de disputa entre cada uma das raízes para verificar qual delas irá conquistar cada vértice de G. Ao final da execução um vértice estará "pendurado" apenas a uma única subárvore, fazendo com que tenhamos vários grupos de nós, similar ao que acontecia com as MST's. Porém aqui há supervisão no processo de formação dos grupos, uma vez que o usuário pode definir de onde as subárvores irão iniciar o crescimento (esses pontos devem ser escolhidos de forma a definir o centro dos agrupamentos).

Questionamentos

Considerando o grafo abaixo, mostre os resultados (plote graficamente) obtidos para:

Grafo com 59 cidades da Alemanha ocidental

Através do algoritmo de Dijkstra em Python, as bibliotecas NumPy, NetworkX e Matplolib foi possível plotar os grafos.

Algoritmo de Dijkstra em Python

Plotando os grafos com agrupamento K=2 e K=3

Resultados

a) 2 agrupamentos (K = 2)
Pegando os vértices 0 e 42

b) 3 agrupamentos (K = 3)
Pegando os vértices 0, 26 e 53

Projeto 5 - O Problema do Caixeiro Viajante

Problema do Caixeiro Viajante

O Problema do Caixeiro Viajante (TSP) é um problema que possui como objetivo determinar a menor distância percorrendo várias cidades apenas uma vez cada e retornando a cidade na qual se iniciou a rota. O problema foi inspirado na necessidade de realizar entregas em locais distintos percorrendo o menor caminho, reduzindo assim o tempo e o custo das viagens.

Grafo Hamiltoniano

Um grafo G pode ser considerado hamiltoniano se existe um ciclo pertencente a G que contenha todos os seus vértices, e esses vértices devem aparecer somente uma vez no ciclo. O ciclo em questão é chamado de ciclo hamiltoniano. Ou seja, todo grafo que possui o ciclo hamiltoniano ele é um grafo hamiltoniano.

Objetivo

Desenvolver um programa que deve ler o grafo Hamiltoniano ponderado abaixo a partir de um arquivo qualquer e através de um algoritmo visto em sala (Twice-Around), obter 10 soluções diferentes para o problema do caixeiro-viajante.

Metodologia

Foi utilizada a linguagem de programação Python em conjunto com a biblioteca NetwrokX.

Após a execução do Twice-Around, o grafo obtido foi:

Liste as 3 melhores soluções e as 3 piores obtidas. Qual a diferença de custo entre a melhor e a pior? Discuta como a diferença pode ser significativa.

Melhores Soluções

Iniciando no vértice 29: 575.0
Iniciando no vértice 27: 577.0
Iniciando no vértice 13: 593.0

Piores Soluções

Iniciando no vértice 15: 682.0
Iniciando no vértice 18: 682.0
Iniciando no vértice 7: 676.0

A escolhe pelo vértice inicial pode ser bem significativa, visto que a diferença é consideravelmente grande. Há uma diferença de 10000km entre o pior e o melhor caminho.

Projeto 3 - Busca em Largura e Profundidade

Busca em Largura - BFS

A busca em largura (breadth-first search) utiliza um grafo G e começa por um vértice qualquer.  O algoritmo visita o vértice, depois visita todos os vizinhos dele, depois todos os vértices que estão à distância 2 vértice inicial, e assim por diante.  O algoritmo numera os vértices, em sequência, na ordem em que eles são descobertos.

Busca em Profundidade - DFS

O algoritmo de busca em profundidade (depth-first search) começa num nó raiz e explora seus ramos o máximo possível antes de retroceder (backtracking).

Objetivo

Implementar os algoritmos BFS e DFS para extrair as árvores BFS-tree e DFS-tree dos grafos a seguir.

Metodologia

Para a implementação foi utilizada a linguagem Python, a biblioteca NetworkX e Matplotlib para desenhar o grafo.

Busca em Largura - BFS

Busca em Profundidade - DFS

Rodando os códigos BFS e DFS, foi possível gerar as BFS-tree e DFS-tree que podem ser visualizadas abaixo.

BFS-tree do grafo karate.paj

BFS-tree do grafo dolphins.paj

DFS-tree do grafo karate.paj

DFS-tree do grafo dolphins.paj

Projeto 2: Árvore Geradora Mínima

MST - Minimum Spanning Tree

Uma MST (Árvore Geradora Mínima) de um grafo G, é qualquer árvore geradora de G que tenha o menor custo. Ou seja, uma árvore geradora de G é mínima se nenhuma outra árvore geradora tenha custa menor do que ela.

Objetivos

A partir de um dataset específico (grafo ponderado armazenado em arquivo .txt) implementar o algoritmo de Prim para extrair uma Minimum Spanning Tree (MST) do grafo G abaixo.

Grafo com 30 cidades do mundo

Algoritmo de Prim

O algoritmo de Prim tem como característica a cada passo de execução criar uma subárvore, até que ela se torne a geradora.
A implementação em Python pode ser visualizada abaixo:

Metodologia

Foi utilizada a linguagem de programação Python e as bibliotecas NumPy, NetworkX e Matplotlib para gerar o desenho do grafo.
O MST do grafo G pode ser visto abaixo:

MST do grafo G

Projeto 1 - Snakes and Ladders

Snakes and Ladders

Snakes and Ladders é um famoso jogo de tabuleiro em que a cada rodada um jogador joga uma moeda não viciada e avança 1 casa se obtiver cara ou avança 2 casas se obtiver coroa. Se o jogador para no pé da escada, então ele imediatamente sobe para o topo da escada. Se o jogador cai na boca de um cobra então ele imediatamente escorrega para o rabo. O jogador sempre inicia no quadrado de número 1. O jogo termina quando ele atinge o quadrado de número 36.

Objetivos

Encontrar o diagrama de estados da cadeia de Markov que representa o jogo, computando para isso a matriz de transição de estados P.

Desenvolver um script em Python para calcular a distribuição estacionária da cadeia de Markov homogênea em questão. Calcular a probabilidade de um jogador vencer o jogo, ou seja, qual a probabilidade de se atingir o estado 36 no longo prazo? Considere k = 100 um número suficiente de iterações no Power Method. Quais os estados mais prováveis de serem acessados?

Especificar a matriz P_ (P_barra) referente ao modelo Pagerank considerando alpha = 0.1. Considerando k = 100, aplique o Power method e compare o resultado com o obtido no item anterior.

Metodologia

Afinal, o que é uma cadeia de Markov?
Uma cadeia de Markov é uma cadeia de estados, onde o próximo estado só depende do estado atual.

Para a execução do projeto, foi utilizada a linguagem Python.

A matriz de adjacência utilizada foi:

Aplicando o Power Method com 100 iterações, os estados mais prováveis de serem acessados são:

Ordenando para facilitar a visualização

Logo é possível observar que a casa com maior chance de ser acessada é a de número 30.