Matemática no cotidiano: o navegador de satélite
O navegador por satélite é certamente uma ferramenta muito comum, e muitas vezes se assume que sua operação é simplesmente receber informações de satélites que "indicam o caminho". Na realidade, sua capacidade de estabelecer a rota para chegar a qualquer destino é o resultado de uma combinação de diferentes técnicas, que dizem respeito à capacidade de identificar com precisão onde estamos a qualquer momento, a disponibilidade de mapas rodoviários precisos e atualizados e acima de tudo, a capacidade de calcular a melhor rota para chegar ao nosso destino. Neste artigo iremos focar a nossa atenção neste último ponto, explicando que na base deste cálculo existe uma teoria matemática muito precisa, a "teoria dos grafosO que nos permite entender como é possível identificar o caminho mais curto entre dois pontos. Na prática, vemos como uma noção científica abstrata se torna o fundamento de um objeto prático, real e acima de tudo muito útil.
Primeiro, vamos começar de baixo: o que é um gráfico?
Na realidade, nada mais é do que um conjunto de elementos conectados uns aos outros: cada um dos elementos é chamado de "nó", e as conexões são chamadas de "arcos". Um exemplo de gráfico é aquele que tem como elementos uma série de cidades conectadas entre si por meio da malha rodoviária: neste caso, os nós são as cidades e os arcos são os trechos de rodovia entre as próprias cidades. Podemos imaginar um gráfico como uma série de bolas coloridas ou círculos (os nós) conectados por linhas (os arcos). Um arco pode ser orientado ou não: arco orientado é aquele que permite a passagem apenas do nó inicial ao nó chegada (e não vice-versa); arco não direcionado é aquele que permite a passagem em ambas as direções. Em nosso exemplo de navegador, uma rua pode ser considerada um arco orientado se for de mão única, enquanto pode ser considerada um arco não direcionado se for de mão dupla.
Um gráfico é considerado ponderado se um valor, denominado peso, estiver associado a cada arco. Esse valor geralmente pode ser positivo ou negativo. Referindo-nos ao exemplo anterior de cidades e rodovias, podemos obter um gráfico ponderado associando cada trecho de rodovia ao seu comprimento em quilômetros. Em um gráfico, é teoricamente possível ir do nó A ao nó B de várias maneiras diferentes, usando arcos diferentes, assim como na realidade é possível ir de uma cidade a outra usando estradas diferentes. Em seguida, chamaremos de "caminho mais curto" o "caminho mais curto" para conectar o nó A ao nó B.
Para nosso navegador de satélite, encontrar o caminho entre o ponto inicial e o ponto final é como encontrar o caminho mais curto em um gráfico. Na teoria matemática dos gráficos, o problema de calcular o caminho mais curto foi estudado e analisado de todos os pontos de vista, e muitos algoritmos foram produzidos. Um dos mais utilizados, por exemplo, é Algoritmo de Dijkstra, mas existem muitos outros. Cabe, portanto, ao fabricante do navegador escolher o algoritmo que julgar mais adequado. Nesta escolha deve certamente ser considerado que a teoria subjacente à procura do caminho mais curto entre dois nós pode ser muito complexa, especialmente quando se trata de realizar o cálculo em mapas de estradas muito complexos. Por exemplo, foi desenvolvido o algoritmo A * que procura o caminho mais curto usando uma "estimativa estatística" para cada nó; falando em “palavras difíceis”, esta estimativa representa a avaliação a priori da vantagem de passar por um nó sobre outro no caminho para o destino final. Em qualquer caso, entrar nos detalhes dos algoritmos se torna um tanto complicado e requer conhecimentos específicos; esperamos, em todo caso, ter fornecido uma visão básica do problema e talvez ter estimulado o interesse por uma teoria matemática com muitas implicações práticas na vida cotidiana.
John Calcerano