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 (são simétricas e obedecem a desigualdade triangular).. É 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.Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 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.
Algoritmo Seja 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 .
O algoritmo pode ser descrito em pseudocódigo da seguinte forma. Criar um árvore geradora mínima T de G. Seja I o conjunto de vértices de grau ímpar em T. Pelo lema do aperto de mão, I tem um número par de vértices. Encontrar um acoplamento perfeito de peso mínimo M no subgrafo induzido pelos vértices de I. Combinar as arestas de M e T para formar um multigrafo H em que cada vértice tem grau par. Formar um circuito Euleriano em H. Transformar o circuito encontrado na etapa anterior em um circuito Hamiltoniano, ignorando vértices repetidos.
Exemplo 200x200px Dado: gráfico completo cujos das arestas obedecem a desigualdade triangular200x200px Calcular a árvore geradora mínima T200x200px Calcular o conjunto de vértices O com grau ímpar em T200x200px Formar a subgrafo de G usando apenas os vértices de O200x200px Construir um acoplamento perfeito de peso mínimo no subgrafo M200x200px Unir o emparelhamento e a árvore geradora para formar um multigrafo Euleriano.218x218px Calcular o ciclo Euleriano215x215px Remover vértices repetidos, dando a saída do algoritmo
Referências
Categoria:Algoritmos de grafos