Thuật toán Christofides

Thuật toán Christofides (đặt tên theo Nicos Christofides) là một thuật toán xấp xỉ cho bài toán người bán hàng trong đó trọng số các cạnh thỏa mãn bất đẳng thức tam giác. Đặt $G=(V,w)$ là một trường hợp của bài toán người bán hàng trong đó $G$ là đồ thị đầy đủ với tập hợp đỉnh $V$ và trọng số không âm $w$ cho tất cả các cạnh của $G$.

Các bước của thuật toán là như sau:
Bước 1: Tìm một cây bao trùm nhỏ nhất $T$ của $G$.
Bước 2: Đặt $O$ là tập hợp các đỉnh có bậc lẻ trong $T$ và tìm một cặp ghép đầy đủ $M$ của các đỉnh trong $O$ với tổng trọng số nhỏ nhất.
Bước 3: Hợp các cạnh của $M$ và $T$ thành một đa đồ thị $H$.
Bước 4: Tìm một chu trình Euler trên $H$ (H có chu trình Euler do nó liên thông và tất cả các đỉnh đều có bậc chẵn).
Bước 5: Biến đổi chu trình trên thành một chu trình Hamilton bằng cách duyệt qua chu trình từ đầu đến cuối và bỏ qua những đỉnh đã thăm trong quá trình duyệt.

Tỉ lệ xấp xỉ

Chu trình thuật toán tìm được có trọng số không quá 3/2 giá trị tối ưu. Kết quả này có thể chứng minh như sau.

Đặt A là tập hợp các cạnh của chu trình tối ưu cho bài toán người bán hàng cho G. Do (V,A) liên thông, nó chứa các cạnh của một cây bao trùm T' và do đó w(A) ≥ w(T') ≥ w(T). Đặt $B$ là tập hợp các cạnh của chu trình tối ưu cho bài toán người bán hàng cho tập đỉnh $O$. Do các cạnh thỏa mãn bất đẳng thức tam giác nên giá trị tối ưu không giảm khi phải thăm thêm các đỉnh mới. Vì vậy w(A) ≥ w(B). Ta sẽ chứng minh tồn tại cặp ghép đầy đủ cho $O$ với tổng trọng số không quá w(B)/2 ≤ w(A)/2 và do đó đây cũng là chặn trên cho trọng số của $M$ (vì $M$ là cặp ghép đầy đủ nhỏ nhất). Do $O$ có một số chẵn đỉnh, cặp ghép đầy đủ luôn tồn tại. Đặt e₁,...,e_2k là chu trình Euler (duy nhất) của $(O,B)$. Rõ ràng cả e₁,e₃,...,e_2k-1 và e₂,e₄,...,e_2k là các cặp ghép đầy đủ và trọng số của một trong hai cặp ghép là không quá w(B)/2. Do đó w(M)+w(T) ≤ w(A) + w(A)/2. Theo bất đẳng thức tam giác, bước 5 không làm tăng trọng số của chu trình, nên chu trình thuật toán tìm được có trọng số không quá 3/2 trọng số tối ưu.

Tham khảo

• Định nghĩa thuật toán Christofides ở NIST(tiếng Anh)
• Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Báo cáo 388, Graduate School of Industrial Administration, CMU, 1976.(tiếng Anh)