Grafos – 2ª Parte

Depois de na primeira parte (ver Edição 10) termos feito uma introdução ao mundo dos grafos e de termos lançado as primeiras bases para uma melhor compreensão destas estruturas, chegou a altura de perceber, realmente, que problemas podem ser resolvidos.

Pode ficar já claro que o número de algoritmos que resolvem problemas baseados em grafos é enorme, demasiado extenso para ficar completo um artigo, portanto nada melhor do que começar pelos mais simples (e importantes). Preferi manter o nome dos algoritmos e dos problemas em inglês para ser mais fácil encontrá-los numa pesquisa.

Shortest Path (o caminho mais curto)

Este é certamente um dos problemas mais simples de enunciar.

Por exemplo:

Dado um conjunto de cidades, ligadas por estradas, e o respectivo comprimento de cada uma, calcular a distância mínima a ser percorrida entre duas dadas cidades.

Podemos modelar isto com recurso a um grafo pesado, é demais evidente. Cada cidade representa um nó e cada estrada que liga dois nós representa um arco.

Primeiro de tudo, é importante reparar: o facto de existir uma estrada “directa” entre a cidade A e a cidade B, não significa que o caminho mais curto entre as duas cidades seja essa estrada. Pode existir uma cidade C, intermédia, cujo caminho mais curto passe por ela.

Vamos então ver os principais algoritmos.

Algoritmo de Dijkstra

Descrição

O algoritmo de Dijkstra é muito provavelmente o algoritmo mais conhecido no tratamento de grafos.

Este algoritmo não encontra só o caminho mais curto entre duas cidades, mas sim o caminho mais curto entre uma cidade (chamada origem) e todas as outras.

Parte da seguinte importante e simples propriedade: se de todos os arcos que saem do nó A, o arco A-B é o mais curto, então a ligação mais curta entre estes dois nós é através desse arco. Bastante óbvio, uma vez que qualquer outro caminho usando um outro arco seria obrigatoriamente maior, partindo do princípio que todos os arcos têm um peso positivo, claro.

Pseudo-código

# distancia(j) distância do nó de origem ao nó j
# pai(j) nó anterior ao j, do caminho mais curto (para podermos reconstruir o caminho) 

Para todos os nós i
    distancia(i) = infinito  # não alcancável
    visitado(i) = Falso
    pai(i) = nil      # ainda nenhum caminho até ao nó

distancia(origem) = 0 # origem -> a origem do percurso

enquanto(nos_visitados < tamanho_do_grafo)
    # encontrar o vértice não visitado com a distância mínima à origem; chamemos-lhe i
    assert (distancia(i) != infinito, "Grafo não é conexo") 

    visitado(i) = Verdadeiro # marcamos o vértice i como visitado 

    # actualizamos as distância para todos os vizinhos de i
    Para todos os vizinhos j do vértice i
        se distancia(i) + peso(i,j) < distancia(j) então
            distancia(j) = distancia(i) + peso(i,j)
            pai(j) = i

Análise de complexidade

Compreender esta secção implica ter conhecimentos de análise de complexidade que não vou explicar neste artigo.

Como podem ter constatado, o pseudo-código está “incompleto” por não explicar como encontrar o vértice não visitado de distância mínima.

Foi propositado por existirem duas possibilidades:

  • uma pesquisa linear, percorrendo todos os vértices (a mais normal), originando numa complexidade O(V2);
  • utilizar uma heap para encontrar o mínimo, tendo uma complexidade O(V log E), significativamente mais rápido se o grafo for esparso (tiver uma relação arcos/vértices baixa).

Extensões

  • Grafos direccionados não são um problema para este algoritmo.
  • Como é possível concluir partindo da descrição, grafos com arcos com pesos negativos produzem respostas incorrectas, de modo que este algoritmo não pode ser usado nessa situação, devendo-se recorrer ao algoritmo de Bellman-Ford.
  • Apesar de mais rápido (principalmente se utilizarmos uma heap), encontrar o caminho mais curto entre todos os vértices é mais simples recorrendo ao algoritmo de Floyd-Warshall.

Problemas Modelo

Movimentos a cavalo (Knight Moves)

Problema: Dadas duas posições num tabuleiro de xadrez, determinar o número mínimo de movimentos que um cavalo deve fazer para chegar de uma casa à outra.

Análise: O tabuleiro pode ser modelado como um grafo, sabendo que existe ligação entre duas casas se um cavalo se puder deslocar entre elas (e não se forem adjacentes, como acontece por exemplo num flood-fill BFS).

Repare-se que dada uma posição sabemos imediatamente para quais se pode deslocar o cavalo, de modo que não precisamos de o representar em memória do modo “clássico”, mas usar uma representação implícita.

Percursos do caminho de ferro (Railroad Routing – USACO Training Camp 1997, Contest 1 – simplificado)

Problema: É nos dado um mapa (matriz) onde m[ i ][ j ] representa uma dada elevação nesse quilómetro quadrado. Pretendemos construir um caminho de ferro que conecte 2 pontos.

O custo normal por quilómetro é de 100€. Carris que necessitem de ganhar ou perder elevação entre quadrículas, são cobrados 100€ + 3x variação_na_elevação. Uma mudança de direcção de 90º dentro de uma quadrícula implica um custo de 40€.

Qual o custo mínimo para construir o percurso?

Análise: Este é um problema standard de shortest path.

Contudo, em vez de criarmos um nó por quadrícula, devemos criar 4, representando as 4 possíveis direcções de entrar numa dada quadrícula.

Agora podemos criar as ligações correspondentes, e resolvê-lo.

Algoritmo de Floyd-Warshall

Descrição

E se em vez do caminho mais curto entre duas cidades, pretendemos construir uma matriz de adjacência m onde m[ i ][ j ] representa o caminho mais curto da cidade i à cidade j?

Nesse caso, esta é a solução mais simples.

A ideia é a seguinte: pegando num outro vértice K, caso a distância m[ i] [ j] seja maior do que a distância m[ i ][ k ]+m[ k ][ j], podemos afirmar que encontrámos um novo caminho melhor que o anterior, e portanto podemos actualizar m[ i ][ j ].

Provar que esta formulação produz a resposta óptima já é mais complicado, e não vai ser abordado.

Pseudo-código

# dist(i,j) é a "melhor" distância até agora do vértice i ao vértice j

# Comecemos com todas as ligações passando por um único caminho

Para i = 1 até n fazer
    Para j = 1 até n fazer
        dist(i,j) = peso(i,j) 

Para k = 1 até n fazer # k é o vértice "intermédio"
    Para i = 1 até n fazer
        Para j = 1 até n fazer
            se (dist(i,k) + dist(k,j) < dist(i,j)) então # caminho mais curto
                dist(i,j) = dist(i,k) + dist(k,j)

Análise de complexidade

Este algoritmo é claramente O(V3), muito provavelmente o algoritmo com análise mais simples que existe.

Extensões

  • Para este algoritmo pesos negativos não são tão devastadores como para o algoritmo de Dijkstra.
    Desde que não existam ciclos negativos, o algoritmo funciona como pretendemos. (Caso exista um ciclo negativo ele pode ser percorrido tantas vezes quantas quisermos para ter sempre caminhos mais curtos.)

Problemas Modelo

Diâmetro de um grafo

Problema: Dado um grafo conexo, não direccionado e pesado, encontrar os dois vértices que estão mais afastados.

Análise: Calcula-se o caminho mais curto entre todos os vértices e acha-se o máximo da matriz.

Minimal Spanning Tree (árvore de extensão mínima)

Numa Minimal Spanning Tree nós procuramos o conjunto mínimo de arcos necessários para conectar todos os nós.

Suponham que trabalham numa companhia que gere uma rede de auto-estradas. Recentemente, saiu uma lei que obriga a que os camionistas percorram os seus trajectos em estradas iluminadas com postes de 10m.

Como os vossos postes só têm 7m, estão numa boa alhada.

Pretendem então substituir os postes em algumas das vossas auto-estradas, aquelas necessárias para que todas as cidades possam ser abastecidas convenientemente. Qual a distância mínima de autoestrada em que terão que substituir os postes?

Existem dois algoritmos muito usados na procura da árvore de extensão mínima, neste artigo decidi não abordar o algoritmo de Kruskal.

Algoritmo de Prim

Descrição

As semelhanças entre o algoritmo de Prim e o algoritmo de Dijkstra são tantas que eu quando os aprendi facilmente os trocava.

Para tal não acontecer, efectuava sempre o seguinte raciocínio, que no fundo é a sua explicação:

  • Suponhamos que tenho todos os nós conectados, excepto um.
  • Saber qual o arco a usar de modo a conectar este nó aos restantes é fácil – posso escolher o de tamanho menor.
  • Vamos então partir de um ponto. Este ponto vai ficar unido ao resto da árvore através da ligação ao arco mais próximo. Temos agora dois pontos.
  • Qual o próximo ponto a unir? Fácil. O ponto mais próximo dos dois que ainda não foi unido.

Esta metodologia obviamente nos leva à solução óptima (e por ser tão simples preferi explicá-la ao algoritmo de Kruskal).

Pseudo-código

# dist(j) é a distância do nó j à árvore
# pai(j) representa o nó até agora conectado à MST mais próximo do nó J
Para todos os nós i
    dist(i) = infinito  # sem ligações
    intree(i) = Falso   # sem nós na árvore
    pai(i) = nil 

tamanho_da_árvore = 1   # adicionar um nó à árvore
custo_da_árvore = 0                   
intree(1) = Verdadeiro
Para todos os vizinhos j do nó i   # actualizar as distâncias
    dist(j) = peso(1,j)
    pai(j) = 1 

enquanto (tamanho_da_árvore < tamanho_do_grafo)
    # encontrar o nó com a menor distância à árvore; chamar-lhe nó i 
    # obviamente um nó que não esteja "intree"
    assert (distance(i) != infinity, "Grafo não conexo") 

    # adicionar arco pai(i),i à MST
    tamanho_da_árvore = tamanho_da_árvore + 1
    custo_da_árvore = custo_da_árvore + dist(i)
    intree(i) = Verdadeiro     # marcar o nó i como estando na árvore 

# actualizar todas as distâncias depois do nó i ter sido adicionado
para todos os vizinhos j de i
    se (dist(j) > peso(i,j))
        dist(j) = peso(i,j)
        pai(j) = i

Análise de complexidade

Tal como para o algoritmo de Dijkstra, tempo de execução O(V2).

Podemos obter O(V log E) se recorrermos a uma heap.

Extensões

  • Funciona bem com grafos não pesados.
  • Não há problema com múltiplos arcos entre dois nós (ignoramos todos menos o menor, obviamente).
  • Se sofrer outras restrições (como 2 nós não poderem estar mais afastados do que X) então fica muito difícil de alterar.
  • Não funciona com grafos direccionados (em que pretendemos que sejam fortemente conexos – seja possível aceder de um vértice a todos os outros).

Problemas modelo

Highway Building (construindo uma autoestrada)

Problema: Pretende-se construir uma rede de auto-estradas que ligue as K maiores cidades de um país.

Sendo um país pobre, eles pretendem reduzir ao máximo o custo da obra. Sabendo que o custo de uma autoestrada é proporcional ao seu comprimento, e dadas as coordenadas das cidades, quais as cidades que devemos ligar para formar a requerida via rápida? (Nota: não se podem usar outros pontos como nós.)

Análise: Um problema simples de MST, usamos as cidades como nós e consideramos todas as ligações possíveis como arcos.

Referências

  1. USACO Training Pages: http://train.usaco.org

Publicado na edição 12 (PDF) da Revista PROGRAMAR.