Algoritmo di Christofides - Christofides algorithm

L' algoritmo di Christofides o algoritmo di Christofides-Serdyukov è un algoritmo per trovare soluzioni approssimative al problema del venditore ambulante , nei casi in cui le distanze formano uno spazio metrico (sono simmetriche e obbediscono alla disuguaglianza triangolare ). È un algoritmo di approssimazione che garantisce che le sue soluzioni saranno entro un fattore 3/2 della lunghezza della soluzione ottimale, e prende il nome da Nicos Christofides e Anatoliy I. Serdyukov , che lo scoprirono indipendentemente nel 1976.

Questo algoritmo è ancora il miglior algoritmo di approssimazione temporale polinomiale che è stato accuratamente sottoposto a peer review dalla comunità scientifica pertinente per il problema del venditore itinerante sugli spazi metrici generali. Nel luglio 2020, tuttavia, Karlin, Klein e Gharan hanno pubblicato un preprint in cui hanno introdotto un nuovo algoritmo di approssimazione e hanno affermato che il suo rapporto di approssimazione è 1,5 - 10 ⁻³⁶ . Il loro metodo segue principi simili all'algoritmo di Christofides, ma utilizza un albero scelto a caso da una distribuzione casuale scelta con cura al posto dello spanning tree minimo.

Algoritmo

Sia $G = (V, w)$ un esempio del problema del venditore ambulante. Cioè, $G$ è un grafo completo sul set $V$ di vertici, e la funzione $w$ assegna un peso reale non negativo per ogni bordo del $G$ . Secondo la disuguaglianza del triangolo, per ogni tre vertici $u$ , $v$ , e $x$ , dovrebbe essere il caso che $w (uv) + w (vx) \geq w (ux)$ .

Quindi l'algoritmo può essere descritto in pseudocodice come segue.

Creare un minimo spanning tree $T$ di $G$ .
Lasciate $O$ l'insieme dei vertici con dispari laurea in $T$ . In base al lemma di handshaking , $O$ ha un numero pari di vertici.
Trovare un minimo peso perfetto accoppiamento $M$ nel sottografo indotto proposta dai vertici da $O$ .
Combina i bordi di $M$ e $T$ per formare un multigrafo $H$ connesso in cui ogni vertice ha un grado pari.
Formare un circuito euleriano in $H$ .
Trasforma il circuito trovato nel passaggio precedente in un circuito hamiltoniano saltando i vertici ripetuti ( scorciatoia ).

Rapporto di approssimazione

Il costo della soluzione prodotta dall'algoritmo è entro 3/2 dell'ottimo. Per dimostrarlo, lascia che $C$ sia il tour ottimale per i venditori ambulanti. La rimozione di un bordo da $C$ produce uno spanning tree, che deve avere un peso almeno pari a quello dello spanning tree minimo, il che implica che $w (T) \leq w (C)$ . Quindi, numerare i vertici di $O$ in ordine ciclico attorno a $C$ e partizionare $C$ in due insiemi di percorsi: quelli in cui il primo vertice del percorso in ordine ciclico ha un numero dispari e quelli in cui il primo vertice del percorso ha un numero pari . Ogni insieme di percorsi corrisponde a un abbinamento perfetto di $O$ che corrisponde ai due punti finali di ciascun percorso, e il peso di questo abbinamento è al massimo uguale al peso dei percorsi. Poiché queste due serie di percorsi partizionare i bordi di $C$ , una delle due serie è al massimo la metà del peso di $C$ , e grazie alla disuguaglianza triangolare la corrispondente corrispondente ha peso che è anche al massimo metà del peso di $C$ . La corrispondenza perfetta con peso minimo non può avere un peso maggiore, quindi $w (M) \leq w (C) / 2$ . Sommando i pesi di $T$ e $M si$ ottiene il peso del giro di Eulero, al massimo $3 w (C) / 2$ . Grazie alla disuguaglianza del triangolo, la scelta rapida non aumenta il peso, quindi anche il peso dell'uscita è al massimo $3 w (C) / 2$ .

Limiti inferiori

Esistono input al problema del venditore ambulante che fanno sì che l'algoritmo di Christofides trovi una soluzione il cui rapporto di approssimazione è arbitrariamente vicino a 3/2. Una di queste classi di input è formata da un percorso di $n$ vertici, con i bordi del percorso aventi peso $1$ , insieme a un insieme di bordi che collegano vertici a due passi di distanza nel percorso con peso $1 + ε$ per un numero $ε$ scelto vicino a zero ma positivo. Tutti i bordi rimanenti del grafico completo hanno distanze date dai percorsi più brevi in questo sottografo. Quindi lo spanning tree minimo sarà dato dal percorso, di lunghezza $n - 1$ , e gli unici due vertici dispari saranno gli estremi del percorso, la cui perfetta corrispondenza consiste in un unico bordo con peso approssimativamente $n / 2$ . L'unione dell'albero e l'abbinamento è un ciclo, senza scorciatoie possibili, e con peso di circa $3 n / 2$ . Tuttavia, la soluzione ottimale utilizza i bordi di peso $1 + ε$ insieme a due bordi peso- $1$ incidenti agli estremi del percorso e ha peso totale $(1 + ε) (n - 2) + 2$ , vicino ad $n$ per piccolo valori di $ε$ . Quindi otteniamo un rapporto di approssimazione di 3/2.

Esempio

	Dato: grafo completo i cui pesi degli archi obbediscono alla disuguaglianza del triangolo
	Calcola la $T$ minima dell'albero di $copertura$
	Calcola l'insieme dei vertici $O$ con grado dispari in $T$
	Forma il sottografo di $G$ usando solo i vertici di $O$
	Costruisci una $M di$ corrispondenza perfetta di peso minimo in questo sottografo
	Unisci l'albero $T \cup M$ corrispondente e coprente per formare un multicigrafo euleriano
	Calcola il tour di Eulero
	Rimuovi i vertici ripetuti, fornendo l'output dell'algoritmo