Algoritmo de Christofides
O algoritmo de Christofides é um algoritmo para encontrar soluções aproximadas para o problema do caixeiro-viajante, nos casos em que as distâncias formam um espaço métrico . É um algoritmo de aproximação que garante que suas soluções estão a um fator máximo de 3/2 do tamanho da solução ótima. Seu nome vem do autor Nicos Christofides, que publicou o algoritmo em 1976. Até 2017 esta é a melhor razão de proximação já comprovada para o problema do caixeiro viajante em espaços métricos, embora aproximações melhores sejam conhecidas para alguns casos especiais.
Seja G = (V,w) uma instância do problema do caixeiro viajante. Isto é, G é um grafo completo com o conjunto de vértices V, e a função w atribui um peso (valor real não-negativo) a cada aresta de G. De acordo com a desigualdade triangular, para três vértices u, v e x quaisquer, é válido dizer que w(uv) + w(vx) ≥ w(ux). O algoritmo pode ser descrito em pseudocódigo da seguinte forma.
