Giả sử một nhân viên bán hàng muốn đến thăm một số thành phố nhất định được giao cho anh ta. Anh ta biết khoảng cách của cuộc hành trình giữa mọi cặp thành phố. Vấn đề của anh ta là chọn một con đường bắt đầu từ thành phố quê hương của anh ta, đi qua mỗi thành phố chính xác một lần và trở về thành phố quê hương của anh ta một khoảng cách ngắn nhất có thể. Bài toán này liên quan mật thiết đến việc tìm một đoạn mạch Hamilton có độ dài nhỏ nhất. Nếu chúng ta biểu diễn các thành phố bằng các đỉnh và đường nối hai cạnh của các thành phố, chúng ta sẽ có được một đồ thị có trọng số trong đó, với mỗi cạnh ei một số wi (trọng số) được liên kết. Các bài viết liên quan: Một cách giải thích vật lý của phần tóm tắt trên là: coi đồ thị G như một bản đồ gồm n thành phố trong đó w (i, j) là khoảng cách giữa các thành phố i và j. Một nhân viên bán hàng muốn có chuyến tham quan các thành phố bắt đầu và kết thúc tại cùng một thành phố bao gồm việc đến thăm từng thành phố còn lại một lần và chỉ một lần. Trong đồ thị, nếu chúng ta có n đỉnh (thành phố), thì có (n-1)! Các cạnh (tuyến đường) và tổng số mạch Hamilton trong một complete graph gồm n đỉnh sẽ là Bài toán Người bán hàng làm du lịch. Cách giải Travelling Salesman ProblemTraveling Salesman Problem (TSP) là một trong những bài toán nổi tiếng trong lĩnh vực tối ưu hóa kinh tế và máy tính. Bài toán yêu cầu tìm một đường đi qua mỗi điểm trong một tập hợp các địa điểm du lịch (hay các thành phố) một lần duy nhất và kết thúc tại điểm xuất phát sao cho tổng chi phí của đường đi là nhỏ nhất. Hiện nay vẫn chưa có phương pháp nào để giải quyết bài toán TSP một cách hoàn toàn tối ưu trong thời gian chấp nhận được. Tuy nhiên, các thuật toán heuristics và metaheuristics có thể được sử dụng để tìm giải pháp gần đúng. Các phương pháp giải quyết bài toán TSP bao gồm:
Phương pháp Nearest NeighbourThủ tục này mang lại kết quả hợp lý tốt cho vấn đề nhân viên bán hàng đi du lịch. Phương pháp như sau: Bước 1: Chọn một đỉnh tùy ý và tìm đỉnh gần với đỉnh bắt đầu nhất để tạo thành đường đi ban đầu của một cạnh. Bước 2: Gọi v là đỉnh mới nhất được thêm vào đường dẫn. Bây giờ, trong số kết quả của các đỉnh không nằm trong đường dẫn, hãy chọn đỉnh gần nhất với v và thêm đường dẫn, đường nối cạnh v và đỉnh này. Lặp lại bước này cho đến khi tất cả các đỉnh của đồ thị G được đưa vào đường dẫn. Bước 3: Nối đỉnh bắt đầu và đỉnh cuối cùng bằng một cạnh và tạo thành mạch. Ví dụ: Sử dụng phương pháp hàng xóm gần nhất để giải bài toán TSP sau đây, cho đồ thị được hiển thị trong hình bắt đầu từ đỉnh v1.  Giải pháp: Chúng ta phải bắt đầu với đỉnh v1. Bằng cách sử dụng phương pháp lân cận gần nhất, việc xây dựng đỉnh bằng đỉnh của chuyến tham quan hoặc mạch Hamilton được thể hiện trong hình: 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: Problem 5: Có $n$ thành phố đánh số từ $1$ đến $n$ và các tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này ñược cho bởi mảng $C[1..n,1..n]$, ở đây $C[i,j]$ là chi phí đi đoạn đường trực tiếp từ thành phố $i$ đến thành phố $j$. Một người du lịch xuất phát từ thành phố $1$, muốn đi thăm tất cả các thành phố còn lại mỗi thành phố đúng $1$ lần và cuối cùng quay lại thành phố $1$. Hãy tìm hành trình với chi phí ít nhất cho người đó. 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: DynamicTSP($C[1,2,\ldots, n,1,2,\ldots,n]$): Cost$[{1},1] = + \infty$ for $s \leftarrow 1$ to $n-1$ do for each $S \leftarrow$ a subset of $\{1,2,\ldots, n\}$ of size $s$ Cost$[{S},1] + \infty$ for each $i \leftarrow S\setminus\{1\}$ SubtourCost$(S\setminus \{i\},i)$ opt $\leftarrow +\infty$ for $j \leftarrow 2$ to $n$ opt $\leftarrow \min\{$opt,Cost$[\{2,3,\ldots, n\}\setminus \{j\},j] + C[i,j]\}$ return opt 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 . Giả mã như sau: SubtourCost($S,i$): Cost$[S, i] \leftarrow +\infty$ for each $j \leftarrow S$ Cost$[S, i] \leftarrow \min\{$Cost$[S, i],$ Cost$[S\setminus \{j\}, j] + C[i,j]\}$ 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ã 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:
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ư:
Bạn đọc có thể tham khảo thêm ở [] 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: Problem: Cho một số nguyên $n$-bít $v$ có $k$ bít $1$. Tìm số nguyên $n$-bít $w$ tiếp sau $v$ theo thứ tự từ điển và có $k$ bít $1$. 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). int NextSet(unsigned int $v$, int $n$): unsgined int $w$ unsgined int $t \leftarrow (v | (v-1))+1$ $w \leftarrow t | ((((t \& -t) / (v \& -v))$>>$1) - 1)$ if $w$>>$n = 0$ return $w$ else return 0 Để 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: Problem: Cho một tập $S \subseteq \{1,2,\ldots, n\}$ với kích thước $|S|$, liệt kê các tập con của $S$ có kích thước $|S|-1$. 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$. GenerateSubset(int seed, $n$): node *head = NewNode() head$\rightarrow$id = seed; node *iterator $=$ head for $i \leftarrow 0$ to $n-1$ if ((seed>>$i$)&1) = 1 [[check $(i+1)$-th bit to be 1]] node *elem = NewNode() elem$\rightarrow$id $=(1$<<$i)$^seed [[set $(i+1)$-th bit of seed to 0]] elem$\rightarrow$x $=i+1$ iterator$\rightarrow$next $=$ elem; iterator $=$ iterator$\rightarrow$next. return head 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: |
