O projeto: Mapa de Rotas

A missão do projeto

A missão é direta de enunciar e rica de resolver: dado um mapa de pontos conectados, e dois pontos específicos, ache um caminho de um até o outro. Pense num metrô. Você está na estação Centro e quer chegar na estação Parque. O programa precisa devolver a sequência de estações que leva você lá. Esse mesmo problema aparece disfarçado em muitos lugares: o aplicativo de trânsito achando a rota entre dois bairros, a rede social calculando quantos apertos de mão separam você de outra pessoa, o jogo movendo um personagem pelo labirinto até a saída. Todos são a mesma pergunta com roupas diferentes, e todos se resolvem com as estruturas e os algoritmos que você viu ao longo deste curso avançado.

O erro do iniciante é sair codando. O projetista faz o contrário: primeiro desenha o problema. E a pergunta que desbloqueia tudo é uma só. Como represento essa rede de um jeito que o programa consiga percorrer? A resposta você já conhece: um grafo. As estações viram vértices, os trechos de trilho que ligam duas estações viram arestas. Quando você olha o mapa do metrô e enxerga vértices e arestas em vez de desenho colorido, o problema deixa de ser sobre trens e vira um problema de grafo, exatamente o tipo que temos ferramenta para resolver.

O que vira vértice, o que vira aresta

Modelar bem é acertar duas escolhas: o que é vértice e o que é aresta. A regra prática é pensar no que são os pontos de interesse (viram vértices) e no que os conecta diretamente (viram arestas). No metrô, vértice é estação, aresta é o trecho que liga duas estações vizinhas. Numa rede de amizades, vértice é pessoa, aresta é a amizade entre duas pessoas. Num labirinto, cada casa livre vira um vértice e cada passo possível entre casas vizinhas vira uma aresta. Feita essa escolha, você precisa guardar o grafo de um jeito que o programa consiga consultar. A forma mais útil é a lista de adjacência: para cada vértice, uma lista dizendo com quem ele se liga.

grafo <- {
  "Centro":  ["Norte", "Feira"],
  "Norte":   ["Centro", "Parque"],
  "Feira":   ["Centro", "Porto"],
  "Parque":  ["Norte", "Porto"],
  "Porto":   ["Feira", "Parque"]
}
// vizinhos diretos de Centro:
escreva(grafo["Centro"])   // ["Norte", "Feira"]

Cada estação (vértice) aponta para a lista dos seus vizinhos. Isso é a lista de adjacência do Mapa de Rotas.

Por que começar pela modelagem

Ao longo da trilha você foi do resolver problemas soltos ao projetar soluções. Este projeto é o teste dessa mudança. Quem começa a modelagem certa quase não sofre depois: o grafo pronto praticamente entrega o algoritmo. Quem pula direto para o código costuma se enrolar, escrevendo laços confusos que tentam adivinhar conexões que nunca foram organizadas. Guardar a rede como lista de adjacência é o que permite, na próxima aula, percorrer o grafo com calma, perguntando a cada passo quais são os vizinhos do ponto atual. A modelagem não é burocracia, é a decisão que torna o resto simples.