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

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

Алгоритам

Псеудокод:

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

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

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

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

Нека је Шаблон:Math означавају скуп грана оптималног решење ПТП за Шаблон:Math. Зато што је Шаблон:Math повезан, он садржи неко разапињуће стабло Шаблон:Math и тада Шаблон:Math.

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

Зато што су тежине грана троугаоне (посета више чворова не може да смањи укупне трошкове), знамо да Шаблон:Math.

Показали смо да постоји савршено поклапање чворова $O$ и тежина испод Шаблон:Math и зато имамо исту горњу границу за $M$ (јер је $M$ савршено поклапање са минималним трошковима).

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

Јасно је да се Шаблон:Math и Шаблон:Math савршено поклапају , па је тежина барем једног од њих је мања или једнака Шаблон:Math.

Тако је Шаблон:Math и из неједнакости троугла следи да је алгоритам 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.