Problema do Caixeiro Viajante (ou Traveling Salesman Problem, TSP)

Entrada: um grafo completo não-orientado G = (V, E) com custos c(e) não negativos nas arestas

Solução: um circuito de custo mínimo que visita cada vértice exatamente uma vez



Algoritmo de Adição do Mais Próximo (G=(V, E), c) {

	encontre os dois vértices mais próximos 
	construa um ciclo C entre esses dois vértices
	
	enquanto V(C) != V
		seja i \in V(C) e j \in V \ V(C) o par que minimiza c(i, j)
		seja k o vértice que segue i no ciclo C
		adicionamos j em C entre i e k
	
	devolva C
}

Eficiência:

 - observe que o algoritmo escolhe, em cada iteração, o vértice fora de C que é alcançado por uma aresta de custo mínimo que tem uma ponta num vértice de C.
 
 - tivemos que fazer algo muito parecido no algoritmo de Prim e resolvemos isso usando um heap de mínimo.
 
 - a eficiência obtida com isso é \Theta(m log n), pois 
 
    - embora a iteração principal do algoritmo só ocorra \Theta(n) vezes
	
	- e remover do heap o vértice que minimiza o valor da aresta tenha custo \Theta(log n)
	
	- em cada iteração pode ser necessário atualizar no heap o valor da aresta de menor custo para todos os vértices alcançados pelo vértice removido do heap
	
	   - cada uma dessas atualizações custa \Theta(log n)
	   
	   - e podem ocorrer \Theta(m) dessas ao longo da execução de todo o algoritmo



Garantia de qualidade:

 - vamos explorar a semelhança do comportamento desse algoritmo com o algoritmo de Prim, que obtém uma árvore geradora mínima
 
 - primeiro, observe que o custo de uma árvore geradora mínima <= custo ótimo do TSP
 
 - para entender porque isso ocorre, seja
 
    - OPT o custo de um circuito que é solução ótima do TSP
	
	- Path o custo de um caminho obtido removendo uma aresta do circuito ótimo do TSP
	
	- MST uma árvore geradora mínima
	
 - note que
 
	MST <= Path , pois MST é a árvore de custo mínimo e Path é o custo de um caminho, que é uma árvore em particular
	
	Path <= OPT , pois OPT é o custo de Path mais o custo da aresta que foi removida
	
	MST <= Path <= OPT



 - Agora vamos mostrar que o custo do circuito obtido pelo algoritmo é <= 2 MST
 
 - Primeiro, observe que o algoritmo se comporta exatamente como o algoritmo de Prim (que tivesse começado em um dos vértices extremos da aresta de menor custo)
 
    - Ou seja, a sequência com que o algoritmo adiciona vértices a C é a mesma que o algoritmo de Prim adiciona vértices à árvore
 
 - Vamos focar numa iteração qualquer do algoritmo
 
    - E mostrar que o custo que o circuito aumenta nesta iteração é no máximo 2 * o custo que a árvore geradora mínima aumentaria
 
 - Observe que o algoritmo escolhe o vértice mais próximo j (que está próximo de i e será adicionado entre i e k)
 
 - Assim, o custo do circuito vai aumentar de 
 
	c(i, j) + c(j, k) - c(i, k)
	
 - No entanto, pela desigualdade triangular 
 
	c(j, k) <= c(i, j) + c(i, k) --> c(j, k) - c(i, k) <= c(i, j)

 - Portanto, o aumento no custo do circuito (lado esquerdo da seguinte inequação)
 
	c(i, j) + c(j, k) - c(i, k) <= 2 * c(i, k)
	
 - Como o lado direito da seguinte inequação é duas vezes o aumento no custo da árvore geradora mínima
 
 - Somando ao longo de todas as iterações do algoritmo (e observando que ele começa com um circuito que custa duas vezes as arestas de menor custo do grafo)
 
    - temos que o custo do circuto <= 2 * MST <= 2 * OPT
	
	- o algoritmo é 2-aproximado