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 (são simétricas e obedecem a desigualdade triangular).[1] É 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.[2] 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 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.
- 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
![]() | Dado: gráfico completo cujos das arestas obedecem a desigualdade triangular |
![]() | Calcular a árvore geradora mínima T |
![]() | Calcular o conjunto de vértices O com grau ímpar em T |
![]() | Formar a subgrafo de G usando apenas os vértices de O |
![]() | Construir um acoplamento perfeito de peso mínimo no subgrafo M |
![]() | Unir o emparelhamento e a árvore geradora T ∪ M para formar um multigrafo Euleriano. |
![]() | Calcular o ciclo Euleriano |
![]() | Remover vértices repetidos, dando a saída do algoritmo |
Referências
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), «18.1.2 The Christofides Approximation Algorithm», Algorithm Design and Applications, Wiley, pp. 513–514 .
- ↑ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.