Re: [obm-l] Problema do lixeiro - adendo
Olá Demétrius, obrigado pelos links, mas não é necessário nenhum conhecimento de grafos para se resolver esse problema. A forma de abordá-lo é que é o "x da questão" : nada de força bruta, seguindo o impulso de se tentar seguidamente um caminho melhor que o outro. Depois que vc pensar o suficiente a respeito, apenas olhando para a figura, vai gastar menos de 1 minuto com o lápis para desenhar um caminho ótimo (que diga-se de passagem, mede 35x100m). Abraços, Rogerio Ponce. --- Demétrius <[EMAIL PROTECTED]> escreveu: > É o mesmo problema do carteiro chinês, não?!?! > > Tem muito tempo que não executo estes algoritmos e > portanto me sinto um pouco desconfortável em entrar > em > detalhes... > > Utilize um algoritmos de busca. > > No google vc acha vários tipos de soluções! > Aqui algumas que ele me retornou... > > http://arxiv.org/pdf/cs.MS/0505031 > http://pt.wikipedia.org/wiki/Teoria_dos_grafos > http://www.universiabrasil.net/mit/6/6281J/pdf/f01-lec14.pdf > > Abraços, > Demétrius P. de Miranda > > > --- Rogerio Ponce <[EMAIL PROTECTED]> > escreveu: > > > As ruas externas tambem fazem parte, ou seja, a > > distância a ser varrida e' de 31x100m. > > > > > > --- Rogerio Ponce <[EMAIL PROTECTED]> > > escreveu: > > > Ola' pessoal, > > > um lixeiro precisa varrer todas as ruas dos 12 > > > quarteirões abaixo, comecando numa esquina > > qualquer, > > > e > > > tambem terminando em alguma esquina. > > > Considerando-se que o lado do quarteirão mede > > 100m, > > > qual a distancia minima que ele deve percorrer > > para > > > varrer todas as ruas? > > > > > > Abracos, > > > Rogerio Ponce. > > > > > > a---b---c---d---e > > > | | | | | > > > | | | | | > > > f---g---h---i---j > > > | | | | | > > > | | | | | > > > k---l---m---n---o > > > | | | | | > > > | | | | | > > > p---q---r---s---t > > > ___ Yahoo! Messenger com voz: PROMOÇÃO VOCÊ PODE LEVAR UMA VIAGEM NA CONVERSA. Participe! www.yahoo.com.br/messenger/promocao = 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 =
Re: [obm-l] Problema do lixeiro - adendo
É o mesmo problema do carteiro chinês, não?!?! Tem muito tempo que não executo estes algoritmos e portanto me sinto um pouco desconfortável em entrar em detalhes... Utilize um algoritmos de busca. No google vc acha vários tipos de soluções! Aqui algumas que ele me retornou... http://arxiv.org/pdf/cs.MS/0505031 http://pt.wikipedia.org/wiki/Teoria_dos_grafos http://www.universiabrasil.net/mit/6/6281J/pdf/f01-lec14.pdf Abraços, Demétrius P. de Miranda --- Rogerio Ponce <[EMAIL PROTECTED]> escreveu: > As ruas externas tambem fazem parte, ou seja, a > distância a ser varrida e' de 31x100m. > > > --- Rogerio Ponce <[EMAIL PROTECTED]> > escreveu: > > Ola' pessoal, > > um lixeiro precisa varrer todas as ruas dos 12 > > quarteirões abaixo, comecando numa esquina > qualquer, > > e > > tambem terminando em alguma esquina. > > Considerando-se que o lado do quarteirão mede > 100m, > > qual a distancia minima que ele deve percorrer > para > > varrer todas as ruas? > > > > Abracos, > > Rogerio Ponce. > > > > a---b---c---d---e > > | | | | | > > | | | | | > > f---g---h---i---j > > | | | | | > > | | | | | > > k---l---m---n---o > > | | | | | > > | | | | | > > p---q---r---s---t > > > > > > > > > > > > > > > > > > > > > ___ > > > > Yahoo! Messenger com voz: PROMOÇÃO VOCÊ PODE LEVAR > > UMA VIAGEM NA CONVERSA. Participe! > > www.yahoo.com.br/messenger/promocao > > > = > > 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 > > > = > > > > __ > Converse com seus amigos em tempo real com o Yahoo! > Messenger > http://br.download.yahoo.com/messenger/ > = > 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 > = > __ Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/ = 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 =
Re: [obm-l] Problema do lixeiro - adendo
As ruas externas tambem fazem parte, ou seja, a distância a ser varrida e' de 31x100m. --- Rogerio Ponce <[EMAIL PROTECTED]> escreveu: > Ola' pessoal, > um lixeiro precisa varrer todas as ruas dos 12 > quarteirões abaixo, comecando numa esquina qualquer, > e > tambem terminando em alguma esquina. > Considerando-se que o lado do quarteirão mede 100m, > qual a distancia minima que ele deve percorrer para > varrer todas as ruas? > > Abracos, > Rogerio Ponce. > > a---b---c---d---e > | | | | | > | | | | | > f---g---h---i---j > | | | | | > | | | | | > k---l---m---n---o > | | | | | > | | | | | > p---q---r---s---t > > > > > > > > > > ___ > > Yahoo! Messenger com voz: PROMOÇÃO VOCÊ PODE LEVAR > UMA VIAGEM NA CONVERSA. Participe! > www.yahoo.com.br/messenger/promocao > = > 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 > = > __ Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/ = 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 =
