Caminhos x Passeios

["Rubens Altimari" <rubens@altimari.com.br>]

Olá a todos,

Eu estava revendo o enunciado do EP4, e notei que tem um trecho (da parte
teórica) que estava me deixando confuso. É o seguinte:

<coelho>
É evidente que se v é acessível a partir de r, então existe um caminho
mínimo de r a s. Entretanto, encontrar caminhos mínimos é um problema
computacionamente difícil (a menos, é claro, que não tenhamos pressa em
encontrar o caminho). Encontrar um caminho mínimo de r a v é tão difícil
quanto encontrar um caminho hamiltoniano de r a v (um problema difícil pra
cachorro).

Felizmente (ou curiosamente) existem algoritmos eficientes para encontrar-se
passeios mínimos quando estes existem. Mais ainda, os passeios (mínimos)
encontrados pelos algoritmos são caminhos. Uma maneira compacta de
representar passeios/caminhos mínimos de um dado vértice r a todos os demais
vértices de um grafo é através de uma certa árvore com raiz r.
</coelho>

Fiquei com dúvida com relação ao que, exatamente, é NP-difícil: procurar
diretamente caminhos mínimos? Isto é, fazer um algoritmo de busca do caminho
mínimo que não permita (ou que detecte on-the-fly) ciclos? Afinal, procurar
*passeios* mínimos é polinomial, e os passeios são caminhos, no fim das
contas...

Aliás, comentário: achei esta parte da nomeclatura bastante confusa! Não sei
quem teve a idéia de traduzir os termos por "caminho" e "passeio", e nem sei
dizer o que me faz ficar confuso - talvez seja apenas eu, talvez seja o fato
de os termos terem origem diferente ("caminho" não tem nada a ver com
"passeio"). É curioso que, a meu ver, a bibliografia em inglês não parece
fazer tanta diferença entre um e outro, fala-se mais naturalmente em
"paths", e pronto...

Rubens