Algoritmul Christofides

Algoritmul Christofides sau algoritmul Christofides-Serdyukov  este un algoritm pentru găsirea de soluții aproximative la problema vânzătorului ambulant pentru cazurile în care distanțele formează un spațiu metric (simetric și satisfac inegalitatea triunghiului ) [1] . Algoritmul este un algoritm de aproximare care garantează că soluțiile sunt în 3/2 din lungimea soluției optime. Algoritmul este numit după Nikos Christofides și Anatoly Ivanovich Serdyukov, care l-au găsit în mod independent în 1976 [2] [3] [4] , și are cel mai bun coeficient de aproximare , care a fost dovedit pentru problema vânzătorului ambulant pe spații metrice generale, deși aproximări mai bune pentru unele cazuri speciale.

Algoritm

Să fie un reprezentant al problemei vânzătorului ambulant. Adică, G este un grafic complet pe mulțimea de vârfuri V , iar funcția w atribuie ponderi reale nenegative fiecărei muchii a lui G . Conform inegalității triunghiului, pentru oricare trei vârfuri u , v și x trebuie îndeplinite .

Algoritmul poate fi descris în pseudocod după cum urmează [1] .

  1. Creați un arbore de întindere minim T al graficului G .
  2. Fie O mulțimea vârfurilor cu grade impare în T . Conform lemei strângerii de mână , O are un număr par de vârfuri.
  3. Găsiți o potrivire perfectă M de greutate minimă în subgraful generat dat de vârfuri din O .
  4. Combinăm muchiile M și T pentru a forma un multigraf conex H , în care fiecare vârf are un grad par.
  5. Formăm un ciclu Euler în H .
  6. Transformăm ciclul găsit în pasul anterior într-un ciclu hamiltonian omitând vârfurile repetate ( reducere ).

Factorul de aproximare

Costul soluției obținute de algoritm se situează în 3/2 din cea optimă. Pentru a demonstra acest fapt, să presupunem că C este un tur optim al problemei vânzătorului ambulant. Îndepărtând o margine din C rezultă un arbore de întindere care trebuie să aibă o greutate nu mai mică decât greutatea arborelui de întindere minim, ceea ce implică faptul că . În continuare, numerotăm vârfurile lui O în ordine ciclică în C și împărțim C în două seturi de căi - unul are numere impare ale primului vârf în ordine ciclică, iar al doilea are numere pare. Fiecare set de căi corespunde unei potriviri perfecte a setului O care împerechează cele două puncte de capăt ale fiecărei căi, iar greutatea acestei combinații nu depășește greutatea căilor. Deoarece aceste două seturi de căi împart marginile lui C , una dintre cele două seturi are cel mult jumătate din greutatea lui C și, datorită inegalității triunghiului, potrivirea lor corespunzătoare are o pondere care este, de asemenea, cel puțin jumătate din greutatea lui C. O potrivire perfectă a greutății minime nu poate avea mai multă greutate, deci . Adăugarea greutăților lui T și M dă ponderea ciclului Euler, care nu depășește . Datorită inegalității triunghiului, reducerea nu crește ponderea, deci ponderea rezultatului nu depășește nici [1] .

Limite inferioare

Există cazuri ale problemei vânzătorului ambulant în care algoritmul Christophides găsește o soluție care este în mod arbitrar aproape de 3/2. Una dintre aceste clase de probleme este formată din n vârfuri cu ponderea muchiilor 1 , împreună cu un set de muchii care leagă vârfuri la doi pași distanță de-a lungul căii , cu ponderi , unde este ales aproape de zero, dar pozitiv. Toate marginile rămase ale graficului complet au distanțe egale cu cele mai scurte căi din acest subgraf. Apoi arborele de întindere minim va fi dat de lungimea , și doar două vârfuri impare vor fi punctele de capăt ale căii, iar potrivirea sa perfectă constă dintr-o muchie cu o greutate de aproximativ n /2 . Unirea unui arbore și o potrivire este un ciclu fără reduceri de vârf și o greutate de aproximativ . Cu toate acestea, soluția optimă folosește muchii de greutate împreună cu două muchii de greutate 1 incidente la capetele traseului, iar greutatea sa totală este , care este aproape de n pentru valori mici de . De aici obținem coeficientul de aproximare 3/2 [5] .

Exemplu

Dat: un grafic complet ale cărui ponderi laturi satisfac inegalitatea triunghiului
Calculați arborele de întindere minim T
Calculați mulțimea vârfurilor O cu grad impar în T
Formăm un subgraf al graficului G folosind doar vârfurile mulțimii O
Construim o potrivire perfectă a greutății minime M în acest subgraf
Combină potrivirea și arborele de acoperire T ∪ M pentru a forma un multigraf Euler
Calculați turul Euler
Eliminați vârfurile duplicate și obțineți traversarea rezultată

Note

  1. ↑ 1 2 3 Goodrich, Tamassia, 2015 , p. 513–514.
  2. ↑ Serdyukov A.I. On some extremal traversals in graphs  // Sisteme controlate: Jurnal. - 1978. - T. 17 . — p. 76–79 . Arhivat din original pe 7 aprilie 2020.
  3. ↑ van Bevern R., Slugina VA O notă istorică privind algoritmul de aproximare 3/2 pentru problema metrică a vânzătorului ambulant  //  Historia Mathematica. - 2020. - doi : 10.1016/j.hm.2020.04.003 . - arXiv : 2004.02437 .
  4. ↑ Christofides N. Analiza celui mai rău caz a unei noi euristice pentru problema vânzătorului ambulant  //  Management Sciences Research Report Nr. 388, Școala Absolventă de Administrare Industrială, Universitatea Carnegie-Mellon: hârtie albă. — 1976.
  5. ↑ Bläser, 2008 , p. 517–519.

Literatură

Link -uri