Caminhos: Por que a Vida está Preenchida com tantos Desvios?
Por József Biró, András Gulyás e Zalán Heszberger
[17]Capítulo 4 Direto ao Ponto: Um Capítulo Curto sobre os Caminhos mais Curtos
Um viajante caminha no Őrség (região da Húngria) e pergunta a um homem cortando a relva na margem da floresta de Szalafő: - Quão longe fica Őriszenpéter daqui? – Cinco quilômetros em uma linha reta, mas eu posso conseguir uma viagem mais curta através dos bosques.
– György Moldova, Tökös-mákos rétes, Magvető 1982
Há algo atraente sobre caminhos mais curtos (shortest paths). Eles são tão simples e razoáveis. Eles parecem ser os caminhos mais eficientes para viajar entre os nós em uma rede. Eles requerem o menor montante de distância, tempo ou energia. Para apreendermos a ideia de caminhos mais curtos, consideremos a rede na fig. 4.1. Nessa rede, o caminho mais curto entre os nós D e H é o caminho (D → C → E → G → H), marcado com flechas vermelhas. O seu comprimento é número de arestas cruzadas, o qual é 4 e esse é o único caminho mais curto entre D e H. Flechas verdes marcam os caminhos mais curtos a partir do nó C até o nó F. Há dois caminhos mais curtos (C → B → A → F) e (C → E → G → F) e ambos têm um caminho de 3. Caminhos mais curtos são bastantes simples para computar através de umas poucas linhas de código, por exemplo, através do uso do método de Edsger W. Dijkstra [7].
 |
[18]Fig. 4.1 Caminhos mais curtos em uma rede simples.
O conceito atraente de caminhos mais curtos faz deles cidadãos de primeira classe em muitas áreas da vida. Todos tentam tomar o caminho mais curto de uma loja até o carro, ou de casa até o local de trabalho, para poupar energia e tempo. Engenheiros de redes de computadores gentilmente favorecem caminhos mais curtos por causa da baixa latência e do baixo uso de recursos deles (eles carregam o menor montante possível de roteadores e links). Caminhos mais curtos também são usados gentilmente para predizer o fluxo de informação em redes sociais, biológicas e de transporte. Pesquisadores também os usam para categorizar redes e predizerem o comportamento delas sob circunstâncias incomuns (por exemplo, testar o comportamento da Internet durante um massivo desastre natural).
Embora caminhos mais curtos sejam desejáveis, também há alguns problemas com eles. Primeiro, para encontrar os caminhos mais curtos, alguém tem de explicitamente conhecer a rede inteira. Qualquer programa computando caminhos mais curtos requer a rede inteira como uma entrada para funcionar. Para ilustrar como os caminhos mais curtos podem mudar, imagine que nós esqueçamos uma única aresta na fig. 4.1, a saber, a aresta C → G, a qual está desenhada com uma linha tracejada na fig. 4.2. Nessa rede modificada, o caminho vermelho não é mais o caminho entre D e H, uma vez que o caminho D → C → G → H é mais curto. O caminho mais curto [19]entre C e F não é nenhum dos caminhos verdes, uma vez que C → G → F é mais curto do que eles dois. Adicionalmente, nessa nova situação há apenas um caminho mais curto entre C e F.
 |
[18]Fig. 4.2 A variabilidade dos caminhos mais curtos.
Bem, fornecer a estrutura exata da rede não é um problema no caso de redes pequenas e quase estáticas (por exemplo, as Pontes de Könisberg), mas isso claramente não é uma opção para redes grandes, complexas e dinâmicas, como a Internet. Em segundo lugar, há alguma coisa estranha, alguma coisa artificial em caminhos mais curtos. Parece que caminhos mais curtos ficam muito aquém e não coincidem com a lógica natural subjacente da rede (apenas pense sobre o galo pequeno ou os usuários do sistema de proxy aberto ou as apresentações de mapas mentais). Espere um minuto! Uma rede pode ter uma lógica natural interna? Vejamos mais de perto como uma semelhante lógica pode parecer-se!
ORIGINAL:
BIRÓ, J.; GULYÁS, A.; HESZBERGER, Z. Paths: Why is life filled with so many detours? Birkhäuser Cham, 2021. p. 17-19. Disponível em: <https://link.springer.com/book/10.1007/978-3-030-47545-1>
TRADUÇÃO:
EderNB do Blog Mathesis
Licença: CC BY 4.0
Nenhum comentário:
Postar um comentário