[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico]
[Índice de assunto]
Re: Caminhos x Passeios
- Subject: Re: Caminhos x Passeios
- From: "Rubens Altimari" <rubens@altimari.com.br>
- Date: Fri, 11 Jul 2003 14:02:02 -0300
>Se _existe_ um passeio mínimo, sabemos encontrar um caminho
mínimo eficientemente.
Ah, ok, agora ficou claro, obrigado.
>O problema do caminho hamiltoniano pode ser reduzido ao
problema acima.
Eu tinha visto esta observação em uma anotação de aula a que faltei (nos
famosos Cadernos da LuiÇa), e não tinha mesmo entendido a mecânica da coisa,
agora entendi... Moral: faltas em aulas que tratam de NP-dificuldade causam
NP-dúvidas...
>Você tem razão. Alternativamente pode-se falar apenas em
caminhos e quando entram circuito negativos na jogada diz-se
simplesmente que não se sabe resolver o problema
eficientemente (apesar dos caminhos estarem lá no grafo).
Parece ser esta a opção do Cormen...
Obrigado pela explicação!
Rubens