Кристофајдсов алгоритам

Циљ Кристофајдсовог хеуристичког алгоритма (названог по Никосу Кристофајдсу) јесте да се нађе решење за случајеве "проблем трговачког путника" , где тежине грана задовољавају неједнакост троугла. Нека $G=(V,w)$ буде пример ПТП (проблем трговачког путника), односно $G$ је комплетан граф скупом $V$ чворова са функцијом тежине $w$ додељујући ненегативну целобронју вредност као тежину за сваку грану $G$ .

Алгоритам

Псеудокод:

Направите минимално разапињуће стабло МРС $T$ од $G$ .
Нека $O$ буде скуп чворова непарног степена у $T$ и тражимо савршено подударање $M$ са минималном тежином комплетног графа са чворовима из $O$ .
Комбинују се гране из $M$ и $T$ да формирају мултиграф $H$ .
Формира се Ојлеров циклус у $H$ (H је Oјлеров, јер је повезан само са чворовима парног степена) .
Направи се циклус пронађен у претходном кораку , Хамилтонов, прескачући већ посећене чворове (Shortcutting).

Приближни однос

Трошкови решења које производи алгоритма су 3/2 од оптимума.

Доказ је следећи:

Нека је $A$ означавају скуп грана оптималног решење ПТП за $G$ . Зато што је $(V,A)$ повезан, он садржи неко разапињуће стабло $T$ и тада $w(A) \geq w(T)$ .

Даље нека $B$ означава скуп грана оптималног решења ПТП за комплетан граф преко чворова из $O$ .

Зато што су тежине грана троугаоне (посета више чворова не може да смањи укупне трошкове), знамо да $w(A) \geq w(B)$ .

Показали смо да постоји савршено поклапање чворова $O$ и тежина испод $w(B)/2 \leq w(A)/2$ и зато имамо исту горњу границу за $M$ (јер је $M$ савршено поклапање са минималним трошковима).

Зато што $O$ мора да садржи паран број чворова, савршено подударање постоји. Нека $e 1,..., e 2k$ буде (једини) Ојлеров пут у $(O,B)$ .

Јасно је да се $e 1, e 3,..., e 2k-1$ и $e 2, e 4,..., e 2k$ савршено поклапају , па је тежина барем једног од њих је мања или једнака $w(B)/2$ .

Тако је $w(M)+w(T) \leq w(A) + w(A)/2$ и из неједнакости троугла следи да је алгоритам 3/2-приближан.

Литература

NIST Christofides Algorithm Definition
Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.