Algoritmo de Christofides - Christofides algorithm

O algoritmo de Christofides ou algoritmo de Christofides – Serdyukov é um algoritmo para encontrar soluções aproximadas para o problema do caixeiro viajante , em instâncias onde as distâncias formam um espaço métrico (são simétricas e obedecem à desigualdade do triângulo ). É um algoritmo de aproximação que garante que suas soluções estarão dentro de um fator de 3/2 do comprimento ótimo da solução e é nomeado após Nicos Christofides e Anatoliy I. Serdyukov , que o descobriram independentemente em 1976.

Este algoritmo ainda se destaca como o melhor algoritmo de aproximação de tempo polinomial que foi completamente revisado por pares pela comunidade científica relevante para o problema do caixeiro viajante em espaços métricos gerais. Em julho de 2020, no entanto, Karlin, Klein e Gharan lançaram uma pré-impressão na qual introduziram um novo algoritmo de aproximação e afirmaram que sua razão de aproximação é 1,5 - 10 ⁻³⁶ . Seu método segue princípios semelhantes ao algoritmo de Christofides, mas usa uma árvore escolhida aleatoriamente de uma distribuição aleatória cuidadosamente escolhida no lugar da árvore geradora mínima.

Algoritmo

Seja $G = (V, w)$ uma instância do problema do caixeiro viajante. Ou seja, $G$ é um grafo completo sobre o conjunto $V$ de vértices, ea função $w$ atribui um peso real, não negativo para cada aresta de $G$ . De acordo com a desigualdade do triângulo, para cada três vértices $u$ , $v$ e $x$ , deve ser o caso que $w (uv) + w (vx) \geq w (ux)$ .

Então, o algoritmo pode ser descrito em pseudocódigo como segue.

Criar uma árvore mínimo abrangendo $T$ de $G$ .
Deixe- $O$ ser o conjunto de vértices com estranha grau em $T$ . Pelo lema do aperto de mão , $O$ tem um número par de vértices.
Encontrar um mínimo de peso correspondência perfeita $M$ no subgráfico induzida dada pelos vértices de $S$ .
Combine as arestas de $M$ e $T$ para formar um multigrafo $H$ conectado no qual cada vértice tem grau par.
Formam um circuito euleriana em $H$ .
Transforme o circuito encontrado na etapa anterior em um circuito hamiltoniano pulando vértices repetidos ( atalho ).

Razão de aproximação

O custo da solução produzida pelo algoritmo está dentro de 3/2 do ótimo. Para provar isso, deixe $C$ ser o tour ideal do caixeiro viajante. Remover uma aresta de $C$ produz uma árvore geradora, que deve ter peso pelo menos igual ao da árvore geradora mínima, implicando que $w (T) \leq w (C)$ . Em seguida, numere os vértices de $O$ em ordem cíclica em torno de $C$ e divida $C$ em dois conjuntos de caminhos: aqueles em que o primeiro vértice de caminho em ordem cíclica tem um número ímpar e aqueles em que o primeiro vértice de caminho tem um número par . Cada conjunto de caminhos corresponde a uma correspondência perfeita de $O$ que corresponde aos dois pontos finais de cada caminho, e o peso dessa correspondência é no máximo igual ao peso dos caminhos. Uma vez que estes dois conjuntos de caminhos particionar os bordos de $C$ , um dos dois conjuntos tem, no máximo, a metade do peso de $C$ , e graças à sua desigualdade do triângulo correspondente correspondente tem um peso que também é, no máximo, a metade do peso de $C$ . A correspondência perfeita de peso mínimo não pode ter peso maior, então $w (M) \leq w (C) / 2$ . Somando os pesos de $T$ e $M$ dá o peso do passeio de Euler, no máximo $3 w (C) / 2$ . Graças à desigualdade do triângulo, o atalho não aumenta o peso, então o peso da saída também é no máximo $3 w (C) / 2$ .

Limites inferiores

Existem entradas para o problema do caixeiro viajante que fazem com que o algoritmo de Christofides encontre uma solução cuja razão de aproximação seja arbitrariamente próxima de 3/2. Uma dessas classes de entradas é formada por um caminho de $n$ vértices, com as bordas do caminho tendo peso $1$ , juntamente com um conjunto de arestas conectando vértices a duas etapas de distância no caminho com peso $1 + ε$ para um número $ε$ escolhido próximo a zero, mas positivo. Todas as arestas restantes do gráfico completo têm distâncias fornecidas pelos caminhos mais curtos neste subgrafo. Então, a árvore geradora mínima será dada pelo caminho, de comprimento $n - 1$ , e os dois únicos vértices ímpares serão os pontos finais do caminho, cuja combinação perfeita consiste em uma única aresta com peso aproximadamente $n / 2$ . A união da árvore e do casamento é um ciclo, sem atalhos possíveis, e com peso aproximado de $3 n / 2$ . No entanto, a solução ideal usa as arestas de peso $1 + ε$ junto com duas arestas de peso- $1$ incidentes aos pontos finais do caminho, e tem peso total $(1 + ε) (n - 2) + 2$ , próximo de $n$ para pequenos valores de $ε$ . Portanto, obtemos uma razão de aproximação de 3/2.

Exemplo

	Dado: gráfico completo cujos pesos das arestas obedecem à desigualdade do triângulo
	Calcule a árvore geradora mínima $T$
	Calcule o conjunto de vértices $O$ com grau ímpar em $T$
	Forme o subgrafo de $G$ usando apenas os vértices de $O$
	Construa uma correspondência perfeita de peso mínimo $M$ neste subgrafo
	Unir correspondência e árvore de abrangência $T \cup M$ para formar um multigrafo Euleriano
	Calcule o passeio de Euler
	Remova vértices repetidos, dando a saída do algoritmo