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.

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