Repositório no Git

Todos os algoritmos implementados nesse blog estão no GitHub:

https://github.com/andlzanon/Trabalho-de-Grafos

O Problema do Caixeiro Viajante

O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização do tipo NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível. Basicamente, dado um grafo G = (V, E, w) deve-se encontrar um ciclo Hamiltoniano de custo mínimo.

Para solucionar esse problema pode ser utilizado o algoritmo Twice-Around, cujo pseudocódigo é mostrado na figura 1.

Figura 1: Pseudocódigo do algoritmo Twice-Around

Desse modo, foi elaborado um programa em Python baseado no algoritmo Twice-Around acima, no intuito de se gerar 10 soluções diferentes para o problema do caixeiro viajante e listar as 3 soluções que possuem o melhor custo e as 3 soluções que possuem o pior custo.

Inicialmente, o programa lê uma matriz de adjacências de um arquivo .txt, e a partir dela gera dois grafos, G e CopyG, como mostra a figura 2 a seguir.

Figura 2: Matriz de adjacência é transformada em grafos

Como é possível notar no trecho de código acima, o processo de transformação de matriz de adjacência é realizado 10 vezes, e são criados dois grafos iguais em cada uma das vezes para que se possa a partir deles obter o Prim, que no nosso código não mantém o peso das arestas após gerar a mst, então o CopyG é utilizado para preservar o peso das arestas das arestas iniciais.

Após serem gerados os grafos, a função twice_around é chamada e ela segue o algoritmo de mesmo nome. Inicialmente se obtém a mst do grafo G a partir do código Prim, que é praticamente igual aquele já feito pelo grupo. Depois disso, as arestas da mst são dobradas ao transformá-lo em dígrafo, o que permite que seja percorrido um circuito euleriano na árvore. Então, é definido o ciclo euleriano e ele então é percorrido de modo a se obter a soma dos pesos das arestas nele visitado. O algoritmo então retorna o peso total do ciclo euleriano e o caminho que foi percorrido. O trecho de código que representa esse processo é mostrado na figura 3.

Figura 3: Trecho do código do Twice-Around

Por fim, é criado um arquivo circuito.txt que contém os 10 circuitos gerados e o peso de cada um, como é mostrado na figura 4. Cabe lembrar que, devido ao fato do código do Prim não possuir raiz fixa, cada vez que o programa roda vão ser gerados circuitos com pesos diferentes, então será analisado os que foram gerados apenas em nosso teste.

Figura 4: Circuitos e pesos gerados

Como é possível notar pela imagem acima, as três melhores soluções são aquelas dos caminhos (0), (1) e (5) cujo peso é igual a 790. Já as três piores soluções são aquelas dos caminhos (2), (4) e (6), sendo que a do caminho (4) é a que possui o pior custo possível, 873. A diferença entre o pior custo e o melhor custo é de 83. Como já dito anteriormente, a variação do peso decorre do fato de que o Prim feito não possui raiz fixa, iniciando seu caminho de forma variada toda vez que é chamado, gerando essas pequenas variações.

A figura 5 mostra como o grafo se encontrava inicialmente e como ele ficou depois do Prim e de ser transformado em dígrafo.

Figura 5: Representa como o grafo é alterado ao longo do programa

Algoritmo Dijkstra

O Algoritmo de Dijkstra é caracterizado como sendo um algoritmo guloso e de programação dinâmica, ele garante a convergência para caminhos ótimos e sempre encontra a melhor solução. O Dijkstra é bem similar ao Algoritmo de Prim, porém aplica a técnica de relaxamento nas arestas , em que é verificado se há possibilidades de melhorar um caminho mais curto até um determinado vértice, isto é realizado com a assistência de uma fila de prioridades, definindo qual o próximo vértice a ser visitado (menor peso). Logo, este processo faz com que ele sempre escolha o melhor caminho para se chegar à um vértice a partir de uma dada raiz.

Abaixo é apresentado o pseudocódigo do Algoritmo de Dijkstra:

FIGURA 1: Pseudocódigo Dijstra.

Uma possível implementação desse algoritmo é apresentada à seguir:

FIGURA 2: Implementação do Algoritmo de Dijstra.

Implementação:

Inicialmente é atribuído a todos os vértices do grafo peso infinito, e nenhum predecessor com exceção ao vértice raiz o qual recebe peso = 0. À partir desse vértice o código verifica todos os vizinhos deste e compara o peso de cada um com o peso do vértice mais o peso da aresta entre ele e seu vizinho. Caso o peso do caminho seja menor ocorre a substituição do peso e do predecessor.

Resultados:

Abaixo são apresentados os resultados obtidos para K=1, K=2, e K=3.

K = 1:

Figura 3: Grafo K=1.

K = 2:

Figura 4: Grafo K=2.

Percebe-se uma disputa entre os vértices 10 e 5 pela conquista do maior número de vértices.

K = 3:

Figura 5: Grafo K=3.

Percebe-se uma disputa entre os vértices 10, 5 e 3 pela conquista do maior número de vértices.

Árvores Geradoras Mínimas e Comunidade

O algoritmo de Prim é um dos mais famosos da Teoria dos Grafos. Por meio dele podemos fazer uma árvore geradora mínima de um grafo. 

Para isso Prim utiliza-se de uma lista de prioridades baseada no peso de cada aresta. 

Dessa maneira, para facilitar o desenvolvimento de uma Ávore Geradora Mímina iremos mostrar um tutorial de como codificar Prim para Phyton:

Inicialmente, foi escolhido um grafo NÃO direcionado e com peso, uma vez que tais atributos são pré-requisitos para extraírmos a MST. Portanto, o dataset é relativo a este site: https://toreopsahl.com/datasets/#southernwomen em que se foi escolhido o dataset 13 "Davis Southerm Women Club".

Plotando o grafo em seu estado inicial obtivemos o seguinte grafo: 

FIGURA 1: Grafo das Davis Southerm Women Club

Com isso, inciou-se o desenvolvimento da função Prim:

FIGURA 2: Primeira parte da função Prim

Nessa FIGURA 2 é possível verificar que foi implementado um dicionário chamado Predecessor. Tal dicionário é responsável por guardar o mapa/tabela de predecessores de cada vértice visitado. Dessa maneira é configurado de maneira (x:y) em que x é um vértice e y seu predecessor.

Além disso, conforme o algoritmo todos os vértices, exceto o da raiz que tem por peso 0, inicia a lista de prioridades com valor infinito e precessor igual a None, ou seja, não possui predecessor.

Em substituição a lista de vertices visitados e evitar ficar comparando com o grafo, utilizamos este próprio como a lista. Assim após passar por um vértice esse é excluído do grafo.

É possível verificar na imagem também a função que extrai o vértice de peso mínimo, que é feita pela simples comparação com todos os vértices.

FIGURA 3: Segunda parte do algoritmo

Na FIGURA 3 é possível identificar a troca de predecessor na linha 37 ao verificar-se nos vizinhos e inserção no dicionário de predecessores na linha 41.

Além disso, ao final do algoritmo é gerado e impresso seu mapa de predecessores conforme linhas 46 e 47 além de plotar novo grafo a partir do próprio dicionário nas linhas 49 - 67

Na FIGURA 4 será possível ver a instanciação dos objetos, assim como a passagem de parâmetros.

FIGURA 4: "Main" do programa

Como resultados obtivemos a FIGURA 5 como raiz e mapa de predecessores e na FIGURA 6 a MST plotada.

FIGURA 5: Mapa de predecessores da MST 

FIGURA 6: MST gerada conforme mapa de predecessores

Grafos na busca pela Web

Grafos também são utlizados na sua busca pela Web. Todos os sites estão conectados. Por isso que Web chama Web. Web em inglês é rede. Uma rede feita de nós e arestas, logo, um grafo.

Sabendo disso o Google expandiu o conceito e percebeu que, quando buscamos algo na internet, buscamos uma lista de coisas relacionadas.

Um exemplo disso é um ator/atriz de um filme. Ao pesquisar o nome do(a) artista talvez tenha um outro artista ou diretor que você não conhecia de nome, mas que trabalhou com aquele em várias outras oportunidades. 

Pensando nisso o Google criou o Knowledge Graph. Um grafo que relaciona assuntos, pessoas e coisas e mostra para a gente a cada pesquisa que realizamos.

Neste link o próprio Google explica como é feito.

Facebook e Grafos

O facebook utiliza-se de grafos para armazenar sua rede de contatos, suas preferências e dados. Além disso, outros apps utilizam-se dessas informações sempre que você autoriza este site a obter suas informções.

Para realizar tal ação o facebook disponibiliza uma API chamada Graph API. Essa API se baseia-se em 3 pontos principais: nós, bordas e campos.

Nós são coisas como Usuário, foto, página ou comentário

Bordas são ligações entre coisas (Tá percebendo esse grafo se formando né?!)

Campos são informações dessas coisas.

Dessa maneira, o acesso é feito ao recebedor da informção coletar um token do seu nó disponibilizando essa informação.

Neste link é possível "brincar" com essa API. Para isso basta clicar no botão superior direito "Obter Token" e colocar "me" no campo de GET que ele direciona para sua página do facebook e mostra algumas informações do seu nó.

Visão Geral da Graph API neste link.

P vs NP

P vs NP é um dos problemas do Milennium. Quem o resolver ganha 1 MILHÃO DE DÓLARES. Mas qual a relação entre P vs NP e grafos?

Problemas clássicos em grafos como o do caixeiro viajante e da cobertura de vértices são problemas caracterizados como problemas NP-completo.

Mas o que é NP-completo? Um problema A é NP-completo se existe um outro problema A' NP-completo que pode ser reduzível a A.

Para entender melhor o que é P e o que é NP, NP-completo e NP-difícil, abaixo segue um ótimo vídeo explicando tudo.

Grafos em Jogos

Jogos também utilizam grafos em sua programação. O algoritmo A* é um dos mais utilizados pela indústria. No vídeo abaixo, o A* é explicado de uma forma bem didática

Grafos no Google Maps

O Google Maps utiliza-se grafos para realizar o melhor caminho de um destino até aonde queira chegar. Nesse sentido este link mostra como Dijkstra descobriu seu algoritmo, assim como este pode ser aplicado no app do Google.

Introdução à Grafos

Grafos está relacionado com nosso dia-a-dia. Grafos está nas redes sociais, no planejamento de cidades e atribuição de tarefas. O vídeo abaixo foi postado pelo canal da OBMEP, incentivando jovens de Ensino Médio a conhecerem grafos por meio de problemas clássicos da Teoria dos Grafos, e introduzindo conceitos como o de ciclos eulerianos. No vídeo também é introduzido conceito de arestas e vértices, juntamente com sua representação gráfica.