Trong bài này chúng ta thảo luận giải thuật quy hoạch động để giải bài toán Người Du Lịch (Traveling Salesman Problem - TSP). Giải thuật này được đề xuất bởi Held-Karp và cũng được đề xuất độc lập bởi Bellman vào năm 1962.

Bài toán TSP
Bài toán như sau:

 
Ví dụ: Các thành phố và chi phí giữa chúng được cho bởi hình bên trái của hình dưới đây. Một hành trình tối ưu với tổng chi phí 18 được cho bởi hình bên phải.

Bài toán này có thể được giải bằng phương pháp quay lui với thời gian $O(n!)$. Trong bài này mình sẽ giới thiệu lời giải bằng quy hoạc động với thời gian $O(n^22^n)$ và thảo luận một phương pháp thực thi bằng C.

Giả sử $T[1,2,\ldots]$, $T[1]=1$, là một hành trình tối ưu đi từ thành phố $1$ đến thành phố $T[n]$ qua $n-1$ thành phố khác và quay lại $1$. Vì hành trình $T[1,2,\ldots,n]$ là tối ưu, hành trình $T[2,3,\ldots, n-1]$ đi từ $1$ tới $T[n]$ qua các thành phố $\{2,3,\ldots, n\} \setminus \{T[n]\}$ cũng phải là hành trình tối ưu. Như vậy, nếu gọi $Cost(S,i)$ là chi phí nhỏ nhất đi từ $1$ tới $i$ qua các thành phố trong tập hợp $S$ (không chứa $i$), ta có công thức đệ quy sau:

Do đó, để tính $Cost(S,i)$, ta chỉ cần đảm bảo các giá trị $C(S',j)$ với $S' = S\backslash \{j\}$ đã được tính trước. Giả mã như sau:

 
Hàm SubtourCost$(S,j)$ tính chi phí của hành trình từ $1$ đến $j$ qua mỗi thành phố trong $S$ (không chứa $j$) chính xác 1 lần và được tính theo công thức đệ quy ở trên. Giả mã như sau:

Phân tích thời gian Thời gian tính của thuật toán trên có thể được quy về thời gian cập nhật bảng Cost$[S \subseteq\{2,3,\ldots,n\}][1,2,\ldots,n]$ có kíc thước $O(n2^n)$. Mỗi phần từ của bảng được cập nhật theo thủ tục SubtourCost$(S,j)$ và mất thời gian $O(|S|) = O(n)$. Do đó tổng thời gian tính toán của thuật toán là $O(n^22^n)$.

Thực thi bằng C
Thuật toán quy hoạch động của bài toán TSP cho bởi giả mã DynamicTSP($C[1,2,\ldots, n,1,2,\ldots,n]$): không quá phức tạp. Tuy nhiên khi thực thi thuật toán bằng C hay một số ngôn ngữ khác khi mà các phép toán liên quan đến tập hợp chưa sẵn có thì có một số vấn đề chúng ta cần phải giả quyết:

1. Phương pháp sinh các tập con của $\{1,2,\ldots,n\}$
2. Mã hóa các tập con sao cho việc truy xuất bảng Cost$[S \subseteq\{2,3,\ldots,n\}][1,2,\ldots,n]$ được thực hiện một cách hiệu quả
3. Cách thức lưu trữ các tập con của một tập

Trong phần này mình thảo luận một cách để thực thi bằng $C$ với $n \leq 31$ và giới thiệu một số kĩ thuật xử lí bit. Trước hết đối với vấn đề số 2, chúng ta có thể mã hóa bằng cách gán cho mỗi tập con $S$ của $\{1,2,\ldots, n\}$ một số duy nhất, gọi là id, để việc truy xuất hay cập nhật $C[S,i]$ được hiệu qủa. Ta có thể mã hóa một tập con $S$ của tập $n$ phần tử bằng một số nguyên $n$ bít $a_1a_2\ldots a_n$, trong đó $a_i = 1$ nếu phần tử $i \in S$ và $a_i = 0$ nếu $i \not\in S$. id của $S$ chính là giá trị của số nguyên đó. Ví dụ: $n=5$, tập con $S={1,2,4}$ có thể được biểu diễn bởi số nguyên ở hình dưới đây, và có id $= 01011_2 = 11$. Việc chứng minh không có hai tập con khác nhau nào có cùng một id coi như bài tập cho bạn đọc.
.

Như vậy chúng ta đã có cách để mã hóa mỗi một tập con thành một số nguyên duy nhất tương ứng. Phần tiếp theo của bài viết dùng một số các phép toán xử lí bít. Các phép toán cơ bản gồm có: AND (&), OR (|), XOR (^), NOT (~), SHIFT LEFT (<<), SHIFT RIGHT (>>). Ví dụ một số cách xử lí bít để tính các hàm cơ bản như:

• Lũy thừa 2: $2^n = 1$<<$n$.
• Kiểm tra tính chẵn (lẻ) của số nguyên $a$: $(a\&1) == 0$ ($(a\&1) == 1$).
• Tính minimum (maximum) của hai số nguyên $x,y$: min(x,y) = y^ ((x ^ y) & -(x < y)), max(x,y) = ( x ^ ((x ^ y) & -(x < y)))

Bạn đọc có thể tham khảo thêm ở [2]

Bây giờ ta giải quyết bài toán sinh các tập con kích thước $k$ của tập hợp có kích thước $n$. Ở đây ta sẽ sinh tập con theo thứ tự từ điển. Như vậy ta có thể quy về bài toán cho một tập con $S$, tìm tập con tiếp theo có $k$ phần tử theo thứ tự từ điển. Giả sử tập con $S$ đó được cho dưới dạng mã hóa bit như trên, ta quy về bài toán:

 
Ví dụ: $n=5, k =3, v = 01011_2$, số nguyên tiếp theo sẽ là $ = 01101_2$. Ta có thể nhận thấy là nếu $v$ có $a$ ($a$ có thể bằng 0) bít cuối cùng là 0, trước đó là $b$ bít 1 (như ở hình bên trái của hình dưới đây), thì $w$ sẽ có $b-1$ bít cuối là 1, trước đó là $a+1$ bít 0 và trước $a+1$ bít 0 đó là 1 bít 1 (như hình bên phải của hình dưới đây).

Như vậy để giải bài toán trên, ta tìm cách chuyển $v$ thành $w$ giống như trong hình trên. Giả mã (gần giống với C) như sau:

 
Để bạn đọc không mất tập trung vào giải thuật chính, mình sẽ giải thích đoạn code này ở cuối bài. Code bằng C của giả mã như sau :

int next_set(unsigned int v, int n){
unsigned int w;
unsigned int t = (v |(v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
if(w >> n == 0)return w;
else return 0;
}

Bài toán tiếp theo chúng ta phải giải đó là liệt kê các tập con:

 
Với mỗi tập $S$, mình dùng danh sách liên kết để lưu các tập con của $S$ có kích thước $|S|-1$. Đầu của danh sách lưu $S$. Mỗi mắt xích gồm hai trường: trường id lưu mã của tập con $S'$ và trường x lưu phần tử $x = S\setminus S'$. Giả mã được cho ở dưới, seed là id của tập con $S$.

 
Code bằng C của giả mã:

struct node *generate_subset(unsigned int seed, int n){
struct node *head;
head = malloc( sizeof(struct node));
head->next = NULL;
head->id = seed;
struct node *iterator = head;
int i = 0;
for(i = 0; i< n; i++){
if(((seed >> i)&1) == 1){
struct node* elem =  malloc( sizeof(struct node) );
elem->id = (1<<i)^seed;
elem->x = i+1;
elem->next = NULL;
iterator->next = elem;
iterator = iterator->next;
}
}
return head;
}

Dựa vào thủ tục GenerateSubset(int seed, $n$), ta có thể tính trước mảng Subsets$[1,2,\ldots, 2^n-1]$, trong đó mỗi phần tử của mảng Subsets$[i]$ là một danh sách liên kết lưu các tập con có kích thước $|S|-1$ của tập $S$ có id là $i$. Giả mã như sau:

 
Code của giả mã bằng C:

void generate_all_subsets(struct node *subsets[], int size, int n){
int i = 0;
for(i = 1; i < size; i++){
subsets[i] = generate_subset(i,n);
}
}

Như vậy, chúng ta đã giải quyết xong bài toán mã hóa các tập con và sinh các tập con của một tập $S$ có kích thước $|S|-1$. Vấn đề còn lại chỉ là ghép các phần lại với nhau để giải quyết bài toán. Giả mã của thuật toán như sau:

 
Code bằng C của giả mã:

int dynamic_tsp (int n){
unsigned int set;
int size = 1 << n;
struct node *subsets[size];
generate_all_subsets(subsets,size, n);
struct node *subset;
struct node *iterator;
int i = 0, s = 2;
int opt_tour = INFTY;
for(s = 2; s < n; s++){
set = (1<<s)-1; // the first set of size s in lexicographic order
while(1){
if((set&1) == 0){
subset = subsets[set]; // subsets of the set "set"
iterator = subset->next; // root holds no information
while(iterator != NULL){
subtour_cost(subsets, iterator->id, iterator->x);
if(s == n-1){// save Cost[S][i] for S such that |S| = n-2
opt_tour = min(opt_tour,Cost[iterator->id][iterator->x] + C[iterator->x-1][0]);
}
iterator = iterator->next;
}
}
set = next_set(set, n);// generate next subset in lexicographic order
if(set == 0){ // no more subset
break;
}
}
}
return opt_tour;
}

Thủ tục SubtourCost(S, i) có giả mã như sau:

void subtour_cost(struct node *subsets[], int set_id, int i){
struct node *subset = subsets[set_id];
struct node *iterator = subset->next;
if(iterator->id == 0){// if the set with id set_id has only one element
Cost[set_id][i] = C[0][iterator->x-1] + C[iterator->x-1][i-1];
}else{
Cost[set_id][i] = INFTY;
while(iterator != NULL){
Cost[set_id][i] = min(Cost[set_id][i], Cost[iterator->id][iterator->x] + C[iterator->x-1][i-1]);
iterator = iterator->next;
}
}
}