Re: [obm-l] Problema do lixeiro - adendo

[Rogerio Ponce <rogerioponce-obm@xxxxxxxxxxxx>]

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 <demas1976@yahoo.com.br> 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 <rogerioponce-obm@yahoo.com.br>
> escreveu:
> 
> > As ruas externas tambem fazem parte, ou seja, a
> > distância a ser varrida e' de 31x100m.
> > 
> >  
> > --- Rogerio Ponce <rogerioponce-obm@yahoo.com.br>
> > 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
=========================================================================