[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico] [Índice de assunto]

Re: Caminhos x Passeios

>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