Ciência avança em algoritmos de cálculo de distâncias em redes

A Indian Institute of Technology Gandhinagar anunciou nesta quarta-feira, 29 de outubro, um avanço significativo em algoritmos de cálculo de distâncias em redes. Um cientista da computação conseguiu superar um problema que resistiu desde 1996, permitindo estimativas mais precisas de distâncias entre pontos conectados.

O desafio envolve encontrar o caminho mais curto entre todas as possíveis combinações de pontos em uma rede enorme, uma tarefa crucial para sistemas de transporte, comunicação e biológicos. Este problema é conhecido como o All-Pairs Shortest Paths (APSP).

Anteriormente, métodos tradicionais exigiam muito tempo de processamento e memória, especialmente em redes densamente conectadas. Em 1996, Dor, Halperin e Zwick (DHZ) desenvolveram um método que fornecia estimativas precisas em cerca de duas vezes a distância real, mas apenas para pontos suficientemente distantes.

O novo algoritmo usa uma abordagem mais inteligente ao amostrar conexões em diferentes escalas, permitindo estimativas mais precisas mesmo para pontos próximos, sem comprometer a velocidade.