Algoritme de Christofides

L'algoritme de Christofides és un algoritme aproximat que permet resoldre instàncies del problema del viajante de comerç (designat convencionalment pel seu acrònim en anglés, TSP) en a on els pesos de les arestas del grafo satisfan la desigualtat triangular. Va ser desenrollat en 1976 per Nicos Christofides, professor del Imperial College London.^[1]

Supongam que $G = (V, w)$ representa una instància del TSP, en a on $G$ és un grafo complet definit per: un conjunt $V$ de vèrtiçs o nodos i una funció $w$ que associa un pes o valor real positiu a cada aresta del grafo $G$ .

Descripció

A continuació, es descriuen les fases de l'algoritme en pseudocódigo:^[2]

Obtindre l'arbre recubridor mínim T de G.
Siga O el conjunt de vèrtiços de grau impar en T, trobar un emparellament perfecte M de mínim pes en el grafo complet sobre els vèrtiços de O.
Combinar les arestes de M i T per a crear el multigrafo H.
Obtindre un cicle euleriano en H (H es considera "euleriano" si és conexo i solament presenta vèrtiços de grau parell).
Obtindre un cicle hamiltoniano a partir del cicle euleriano anterior, descartant els nodos visitats (shortcutting).

Demostració

El cost de la solució obtinguda per l'algoritme és 3/2 de la solució òptima.

La prova és la següent:^[3]

Siga A el conjunt d'arestes de la solució òptima del TSP per a G. Com (V,A) és conexo, contindrà varis arbres recubridores T, i per tant, w(A) ≥ w(T). Ademés, siga B el conjunt d'arestes de la solució òptima del TSP per al grafo complet sobre els vèrtiços de O. Com els pesos associats a les arestes són "triangulars" (visitar més nodos no reduïx, en cap cas, el cost total), es té que w(A) ≥ w(B). Es demostra aixina que existix un emparellament perfecte de vèrtiços de O en pes tal que w(B)/2 &li; w(A)/2, de manera que este llímit constituïx una cota superior per a M (ya que M és un emparellament perfecte de mínim cost).

Degut a que O deu contindre un número par de vèrtiços, existix emparellament perfecte. Siga i₁, ..., i_2k el (únic) camí euleriano en (O,B). És evident que tant i₁, i₃, ...,i_2k-1 com i₂, i₄, ..., i_2k són emparellaments perfectes, i que el pes de (a lo manco) un d'ells és menor o igual que w(B)/2. Aixina, es té que w(M)+w(T) &li; w(A) + w(A)/2, i de la desigualtat triangular es deduïx que l'algoritme s'aproxima en 3/2 a l'òptim.

Referències

↑ Erica Klarreich. «Computer Scientists Take Road Less Traveled.» (en anglés). Simons Fundation. Archivat des de l'original, el 3 d'abril de 2013.
↑ «Definició de l'Algoritme de Christofides.» (en anglés). National Institute of Standards and Technology (NIST).
↑ Christofides, Nicos(1976).«Worst-case analysis of a new heuristic for the travelling salesman problem».Graduate School of Industrial Administration.(Report 388)

Referències

Este artícul conté una traducció derivada de «Algoritmo de Christofides» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[SimonF-1] Erica Klarreich. «Computer Scientists Take Road Less Traveled.» (en anglés). Simons Fundation. Archivat des de l'original, el 3 d'abril de 2013.

[2] «Definició de l'Algoritme de Christofides.» (en anglés). National Institute of Standards and Technology (NIST).

[3] Christofides, Nicos(1976).«Worst-case analysis of a new heuristic for the travelling salesman problem».Graduate School of Industrial Administration.(Report 388)

[1]

[2]

[3]