Algoritme de Christofides
El 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 representa una instància de el TSP, en a on és un grafo complet definit per: un conjunt de vèrtiçs o nodos i una funció que associa un pes o valor real positiu a cada aresta del grafo .
Descripció
[editar | editar còdic]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 apareamiento 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ó
[editar | editar còdic]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 de el 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 de el 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 apareamiento 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 apareament perfecte de mínim cost).
Degut a que O deu contindre un número par de vèrtiços, existix apareament perfecte. Siga i1, ..., i2k el (únic) camí euleriano en (O,B). És evident que tant i1, i3, ...,i2k-1 com i2, i4, ..., i2k són apareamientos 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
[editar | editar còdic]- ↑ Erica Klarreich. «Computer Scientists Take Road Less Traveled.» (en anglés). Simons Fundation. Archivat des d'el original, el 3 d'abril de 2013.
- ↑ «Definició de l'Algoritme de Christofides.» (en anglés). National Institute of Standards and Technology (NIST).
- ↑ (1976).Graduate School of Industrial Administration.(Report 388)
Referències
[editar | editar còdic]
- 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.