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  là một trường hợp của bài toán người bán hàng trong đó  là đồ thị đầy đủ với tập hợp đỉnh  và trọng số không âm  cho tất cả các cạnh của .

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  của .
Bước 2: Đặt  là tập hợp các đỉnh có bậc lẻ trong  và tìm một cặp ghép đầy đủ  của các đỉnh trong  với tổng trọng số nhỏ nhất.
Bước 3: Hợp các cạnh của  và  thành một đa đồ thị .
Bước 4: Tìm một chu trình Euler trên  (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  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 . Do  liên thông, nó chứa các cạnh của một cây bao trùm  và do đó . Đặt  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 . 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
. Ta sẽ chứng minh tồn tại cặp ghép đầy đủ cho  với tổng trọng số không quá
 và do đó đây cũng là chặn trên cho trọng số của  (vì  là cặp ghép đầy đủ nhỏ nhất).
Do  có một số chẵn đỉnh, cặp ghép đầy đủ luôn tồn tại. Đặt
 là chu trình Euler (duy nhất) của . Rõ ràng cả
 và
 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á . Do đó .  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
 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.

Tham khảo

Thể loại:Bài toán người bán hàng
Thể loại:Giải thuật lý thuyết đồ thị
Thể loại:Cây bao trùm
Thể loại:Thuật toán xấp xỉ