Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

Tecnologia
heberfa  
em 04/03/22 13:01

Comentários

Último comentário 1º comentário do autor Só moderadores Só quem eu sigo Ordenar por gostei
JohnnyRamone  
em 04/03/2022 14:29
; 8; ; 1;
0 '; 0';
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time - #1 de 5
Paulo  
em 04/03/2022 15:14
@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.
; 2; ; 1;
0 '; 0';
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time - #2 de 5
heberfa  
em 04/03/2022 18:32
@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.  
; 7; ; 0;
0 '; 0';
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time - #3 de 5
ebitda  
em 04/03/2022 19:35
; 2; ; 0;
0 '; 0';
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time - #4 de 5
Paulo  
em 05/03/2022 08:18
@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.
; 3; ; 0;
0 '; 0';
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time - #5 de 5

4 usuários comentaram este tópico.
Clique para ir para o primeiro comentário do usuário.

Ações Pesquisa Videos Livros Análise de Carteira Desconto FAQs Orientação Esportiva Ofertas e Serviços Bastter System Boletim IR Podcasts Revista Tecnologia - Ajuda Eu Assinar Ações Pesquisa Videos Livros Análise de Carteira Desconto FAQs Ofertas e Serviços Orientação Esportiva Boletim BS Podcasts IR Tecnologia Ajuda eu Revista Assinar Assinar

BastterZap