repare que em nenhum momento eu disse que minha solução é "a solução ótima" , mas apenas "uma solução ótima" . Deve ter ficado claro , pela liberdade de segmentação que podemos aplicar a qualquer trecho , que existe uma infinidade de soluções ótimas.
É claro também que o transporte de toda a água pelo primeiro trecho ( o de 3 nanômetros ) também pode ser executado de várias formas diferentes , com o mesmo custo. Não somente porque pode ser segmentado , mas também porque as partidas do ponto inicial não necessitam de que a carga seja de 100 L, conforme você mesmo apontou.
Entretanto, qualquer das soluções para este trecho apresenta, no mínimo, o mesmo custo que a minha, que tem apenas a vantagem de ser a mais simples.
Bem, com relação a não fazer o número mínimo de viagens para carregar 100* N litros , podemos considerar algumas coisas. Uma delas é que a água "desperdiçada" no final , se reflete em aumento astronômico de custo no início. E não existe forma mais barata de se tranportar a água do que aquela forma apresentada ( ou qualquer derivação dela , por meio de segmentação da mesma ), que é "número mínimo exigido de viagens para totalizar os N*100L , e então fazer todas as partidas relacionadas a este trecho com tanque cheio" . É a única maneira de "jogarmos mais para o início" o ponto de partida dessas 2N+1 viagens . Quaquer ponto mais distante , exigiria uma quantidade maior de viagens, e um maior "desperdício" associado . Senão, vejamos um exemplo :
Façamos o transporte de N*100 L , do ponto A para o ponto B , usando a sua política (N+2 partidas) :
Fazendo as N+2 partidas de A com tanque cheio (para minimizar o custo) , podemos percorrer o máximo de 200/(2N+5) km , de forma a totalizar os N*100 L em B .
Ou seja, precisamos de (N+2)*100 L , para percorrermos uma distância total de 200/(2N+5) km .
------------------------------------
Façamos o transporte de N*100L , do ponto A para o ponto B , distantes dos mesmos 200/(2N+5) km , usando a minha política :
1- Há um ponto P , intermediário , a partir do qual eu farei apenas N+1 partidas. Esse ponto estará , no máximo, a 100/(2N+1) km de B , e precisará de (N+1) * 100 L .
2- O transporte de A para P envolve a distância de 200/(2N+5) - 100/(2N+1) km , que será percorrida 2N+5 vezes , isto é , somente neste trecho é que usarei as N+2 partidas ( e com algum desperdício, pois não estarei de "tanque cheio" em todas elas).
Multiplicando-se os fatores, chegamos ao custo de :
200 - 100*(2N+5)/(2N+1) Litros , que deverá ser somado aos (N+1)*100 L de água que deixaremos em P.
Portanto , para percorrermos A MESMA DISTÂNCIA , gastaremos um total de
(N+2) * 100 - 400/(2N+1) Litros .
-----------------------------------------
Economizamos 400/(2N+1) Litros, certo ?
[]'s Rogério
From: João Gilberto Ponciano Pereira <[EMAIL PROTECTED]>
Olá, pessoal
Bem, Rogério, eu, como o prof. Nicolau, também tenho minhas dúvidas se ficou
provado que esta é a solução ótima. Acho que o principal motivo para isto é
o simples fato que no primeiro trecho, o dos 3 nanômetros, a última viagem é
feita sem que o camelo esteja 100% carregado. Ou seja, existe uma "folga"
onde podemos imaginar algumas soluções alternativas. (Se numa viagem, o
camelo vai com menos que 100% de carga, é possível provar que todas as
viagens daquele trecho podem ir com menos de 100% de carga).
Outra coisa que não fico confortável é com o fato de usarmos apenas N+1 viagens para 100 * N litros. Fiz algumas contas, e a degradação no rendimento entre fazer N+1 e N+2 viagens é pequena, se formos considerar o ganho em distância. Acho que, principalmente nos últimos trechos, podemos jogar com estes números, de forma a conseguirmos distâncias finais mais próximas aos exatos 10km.
-----Original Message----- From: Rogerio Ponce [mailto:[EMAIL PROTECTED] Sent: Wednesday, November 19, 2003 7:24 PM To: [EMAIL PROTECTED] Subject: Re: [obm-l] Problema do Camelo - solucao
Não gostei , e alterei "associado a este trecho" por "associado a este último trecho" : ------------------------ Olá Nicolau, repare que partimos de uma condição de contorno , que era ter 1000L no final.
O mínimo para isso , seriam 11 viagens de ida a partir da última base . Temos que adotar isso, pois só desperdiçaríamos água se aumentássemos o número de viagens para transportar a mesma quantidade de água entre a ultima base e o ponto final.
Ao escolhermos que as 11 partidas seriam "com tanque cheio" (100L) , estamos minimizando o caminho que falta percorrer do ponto inicial até essa última base , ao mesmo tempo em que também minimizamos o custo do transporte da água associado a este último trecho do caminho .
O mesmo raciocínio se aplica sucessivamente a todos os trechos. []´s Rogério.
>From: "Nicolau C. Saldanha" <[EMAIL PROTECTED]>
>...
>
>Mas também não demonstrou que a resposta é mínima, pelo menos não de forma
>clara e explícita.
>
>[]s, N.
_________________________________________________________________
_________________________________________________________________ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com
========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
