Grafos

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

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

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