O problema abaixo foi mostrado por Dalton Gerth, que durante muito tempo foi o profissional com a maior quantidade de certificações Microsoft do planeta. Basta ter em mente que lá pra 2001 ele já tinha umas 50. Ele fala sobre o problema do P versus NP, que é um problema da Ciência da Computação.
“Você foi contratado por uma empresa de transportes e precisará traçar a melhor rota entre as cidades, de um caminhão de entregas. O caminhão, passará em 4 cidades, retornando a cidade de Destino. Exemplificando. O caminhão precisará entregar em uma única viagem; as seguintes cidades informadas : São Paulo (onde o caminhão deverá INICIAR e TERMINAR o projeto), Campinas – uma cidade que ele precisará efetuar o transporte, Mogi Mirim – Outra cidade e Osaco – Última cidade. Obtendo a distância entre elas, você deverá realizar um programa, para que ele trace todas as rotas possíveis, para que você consiga extrair do computador, qual é a menor rota que ele deverá fazer.
Neste caso, teríamos algo parecido com isto:
A – Cidade Origem e Destino | B, C, D (Campinas, Mogi Mirim e Osasco)
Como quatro é o número de cidades, sendo que a cidade A, irá iniciar e terminar o trajeto, podemos fazer uma fórmula matemática básica para isto Fatorial de 3 é igual a 6 – 3! = 6
A B C D A
A B D C A
A C B D A
A C D B A
A D B C A
A D C B A
Provavelmente, após criarmos um programa simples, e colocássemos em funcionamento, um computador, resolveria estas sequência em 0,000000000000000001 segundo. Agora, foi pedido para que melhorássemos este mesmo programa. Ao invés do caminhão, seguir por três cidades, ele irá seguir para 5, 10, 15, 20 e finalmente 25 cidades. Então, fazemos o programa, com estas novas variáveis.
E, por nossa supresa, verificamos que… com 15, 20 ou 25 cidades o nosso programa Não funciona !!!!! Ele *trava* (entre aspas). Então, deixamos ele processar com 15 cidades, e vamos almoçar. Percebemos que ele demorou cerca de 20 minutos, mas conseguiu processar. Mas com 20 ou 25 não funciona de jeito nenhum.
Bom, a resposta está no problema…, que não há solução. Caso este computador conseguisse processar cerca de 52 milhões e 42 milhões de rotas por segundo (respectivamente para 20 e 25 cidades), o tempo que iríamos ter a resposta para todos é de :
20 cidades à 73 anos (estaríamos velhos, mas ele iria dar o resultado)
25 cidades à 470 milhões de anos !!! (não está escrito errado !!!)
Ou seja, deveríamos ter deixado este programa ser processado, de acordo com a escala de tempo geológica, no período Fanerozóico.”
E depois todo mundo ainda quer que a informática funcione de maneira exata. :-)
Faça seu comentário
5 comentários
Achei o texto meio sem sentido, pois nada na informática hoje é feito dessa forma.
Isso é a mesma coisa que dizer que para se saber quanto é 2 + 2, se escreve todos os numeros de 0 a 100 e se tira a prova real com cada um pra ver qual é verdadeiro.
A informática funciona de maneira exata.
O crescimento exponencial de uma sequência sempre costuma nos enganar. Nesse caso, quando vi o número de 25 cidades, não tinha idéia da grandeza do número até jogar os dados no Excel. Com 25 cidades a visitar (sem contar a de origem) são 15.511.210.043.331.000.000.000.000 (ou 1,55E+25) permutações possíveis. Considerando o tempo dado de 1,0E-18** para resolver uma permuta com 6 possibilidades de resultado e guardando as devidas proporções, seriam necessários cerca de 30 dias de processamento ininterrupto para calcularmos todas as rotas possíveis para as 25 cidades. Colocando mais uma cidade, esse tempo subiria para 2 anos. Com 27 cidades, para 58 anos, e com 28, para longos 1611 anos!
** (considerei esse valor base para todos os cálculos, por isso a diferença nos números em relação aos apresentados no texto)
Dando um outro exemplo, se alguém lhe oferecesse como prêmio uma quantia em dinheiro, na forma de duas possibilidades de investimento : na primeira você receberia R$ 0,01 que renderia 100% ao mês durante 36 meses. Na segunda você receberia R$ 100.000,00 iniciais que renderiam 10% ao mês durante os mesmos 36 meses. Qual seria a mais vantajosa?
Pois bem, nesse período os R$ 100.000,00 se tranformariam em R$ 3.091.268,05. Nada mal, mas por incrível que pareça, o mísero R$ 0,01 oferecido na primeira proposta renderia no mesmo período R$ 687.194.767,36, mais de 200 vezes a quantia ofertada na proposta anterior! Tudo por causa da maior taxa de juros, que aplicada na forma composta gera um crescimento exponencial do dinheiro.
Achei sem sentido associar problemas NP-Completos ao fato de que a informática não é exata.
Acho que muito antes pelo contrário, eles são uma ótima forma de mostrar como é importante a matemática nesse campo do conhecimento.
Hum, é tipo o problema do caixeiro viajante, né? Meudeus, eu odeio análise de algoritmo.
@Marcelo
Mas pra cada rota ele tem que calcular qual é a melhor.
Posts Novos
CURTA NO FACEBOOK
SOBRE O BLOG
O Byte Que Eu Gosto é um blog nerd/geek com tendências humorísticas. Os comentários não necessariamente refletem a opinião do autor.
ESTATÍSTICAS