RE: Caminhos x Passeios

[Jose Coelho de Pina <coelho@ime.usp.br>]

Rubens Altimari writes:
 [...]
 > 
 > 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? 

Sabemos detectar circuitos negativos
eficientemente. Entretanto, na presença de circuitos
negativos, não sabemos encontrar caminhos mínimos
eficientemente.

 > Afinal,
 > procurar *passeios* mínimos é polinomial, e os passeios
 > são caminhos, no fim das contas...

Se _existe_ um passeio mínimo, sabemos encontrar um caminho
mínimo eficientemente. 

O problema

(1)   dados: - um grafo com comprimentos arbitrários 
              (possivelmente negativos) no arcos;     
             - um par de vértices r,s;
    encontra: um caminho de r a s de comprimento mínimo

é NP-difícil.

O problema do caminho hamiltoniano pode ser reduzido ao
problema acima. De fato, suponha que dados um grafo e um par
d vertices r e s desejamos decidir se existe um caminho
hamiltoniano de r a s. Defina o comprimento de cada arco do
grafo como sendo -1. Assim, existe um caminho hamiltoniano
de r a s se e somente se o caminho mínimo de r a s tem
comprimento -(n-1). Assim, dada uma função que resolve o
problema (1), podemos usar esta função como uma subrotina de
um programa que encontra caminhos hamiltonianos.

Notem que na redução acima o grafo fica recheado de
circuitos negativos, a menos, é claro, que o grafo dado
seja acíclico. [O problema (1) restrito a grafos acíclico
pode ser resolvido em tempo linear (usando ordenação
topológica como fizemos na aula).]

 > Aliás, comentário: achei esta parte da nomeclatura
 > bastante confusa!

Acho que a confusão vem da diferença entre os dois objetos
ser um tanto quanto tênue, enquanto a diferença do ponto de
vista algorítmico ser enorme.

 > 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...
 > 

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).


té +,
coelho


P.S. A terminologia em inglês não chega a ser padrão. Há pelo
menos duas possibilidades bem populares:

 * passeio == path  e  caminho == simple path; ou
 * passeio == walk  e  caminho == path