Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
comentada em 05/03/2022 08:18

Não entendi!?Jarreta49 posts

@JohnnyRamone se estiver certo, descobriram um jeito de resolver problemas complexos, que antes só podia ser tentando todas as alternativas sem ter que tentar todas.

@JohnnyRamone Isso mesmo que o @Paulo falou.

Um exemplo prático seria: Se você tem uma empresa de logística, com vários clientes espalhados pelo brasil e vários caminhões/veículos. Se você quiser encontrar a melhor configuração de rota para esses caminhões/carga/clientes, não existe hoje nenhum algoritmo que garanta qual é a melhor rota para o seu negocio sem que esse algoritmo gaste um tempo incrivelmente grande de cálculo.

O que inviabiliza a utilização de algoritmo exatos, então, essas soluções vem de algoritmos aproximados que dão soluções boas mas não a melhor. 

Exemplo: (generalizando o problema pra que não é da área entender)

Se vc tem um mapa completo com 5 cidades você tem 120 rotas possível para um único caminhão passar em todas a cidades. 
Se tiver 10 cidades em um mapa completo será 3628800 rotas possíveis passando por todas as cidades.
Se tiver 15 cidades em um mapa completo será 1.3 *10^12 rotas possíveis passando por todas as cidades.

Simplificações a parte: (comi um monte de detalhe)

Se você verificar cada rota em 1 milissegundo:
A primeira será resolvida em um piscar de olhos 120 ms
A segunda será 3628,8 segundos, aproximadamente 1h.
A terceira será 1307674368 segundos, aproximadamente 41 anos (se eu fiz a conta certa)

Ou seja, um pequeno acréscimo na entrada de dados faz com que o tempo de calculo exploda exponencialmente. Essa é realidade de vários problemas combinatórios. E são a dor de cabeça de programadores uns 60 anos. Na pratica são "resolvidos" com Inteligência artificial e algoritmos heurísticos ( retornam soluções boas ) mas não encontram a melhor.

O que o artigo propõe é um algoritmo para solução de um desde problemas, na proposta o tempo de solução cresce quase linearmente em relação aos dados, não exponecialmente/fatorialmente como é hoje.

E um artigo muito famoso publicado a uns 50 anos (cujo o autor ganhou o Nobel da  computação por ele, a Medalha Turing) provou que o algoritmos que resolver um desses problemas resolverá também todos da mesma classe. Ou seja, essa solução, se correta, resolverá uma série de problemas em tempo recorde.  

Ver mais

@ebitda na verdade, vai precisar de menos ram.
Esse é um daqueles problemas revolucionários que quem resolver muda o mundo em 10 anos e ninguém entende pq.