Thuật toán nhánh cận giải bài toán người du lịch

 THUẬT TOÁN NHÁNH CẬN GIẢI BÀI TOÁN NGƯỜI DU LỊCH
 NỘI DUNG:
 - Trình bày thuật toán nhánh cận giải bài toán người du lịch.
 - Thiết kế cấu trúc dữ liệu và giải thuật nhánh cận.
 File dữ liệu đầu vào: TRAVEL.INP có cấu trúc:
 n (số đỉnh)
 a11 a12 ... a1n (ma trận chi phí)
 a21 a22 ... a2n
 ....................
 an1 an2 ... ann
 File dữ liệu đầu ra: TRAVEL.OUT có cấu trúc:
 - Trường hợp không tồn tại chu trình Hamilton:
 NO HAMILTON CYCLE
 - Trường hợp tồn tại chu trình Hamilton:
 OPTIMAL COST: C (chi phí tối ưu)
 OPTIMAL CYCLE: (hành trình tối ưu)
 x1 x2 ... xn x1
 y1 y2 ... yn y1
 ...
 z1 z2 ... zn z1
 Ví dụ 1:
 TRAVEL.INP TRAVEL.OUT
 6 OPTIMAL COST: 104
 3 93 13 33 9 OPTIMAL CYCLE:
 4 77 42 21 16 1 4 6 3 5 2 1
 45 17 36 16 28 1 4 6 3 2 5 1
 39 90 80 56 7
 28 46 88 33 25
 3 88 18 46 92 
 Ví dụ 2:
 TRAVEL.INP TRAVEL.OUT
 4 NO HAMILTON CYCLE
 34 
 4 5 
 2 1 
 hơn. Thủ tục sẽ tiếp tục cho đến khi thu được hành trình đầy đủ, tức là phương án của 
bài toán người du lịch. Sau đó ta chỉ cần xét những tập con có cận dưới nhỏ hơn giá trị 
hàm mục tiêu tìm được.
 3. Ma trận rút gọn
 Rõ ràng tổng chi phí của một hành trình sẽ chứa đúng một phần tử trên mỗi dòng 
và mỗi cột của ma trận chi phí C = (c ij). Do đó nếu ta trừ bớt mỗi phần tử của một 
dòng (hay một cột) đi cùng một giá trị thì chi phí của tất cả hành trình sẽ giảm đi một 
lượng, vì thế hành trình tối ưu sẽ không thay đổi. Vì vậy nếu tiến hành trừ bớt các 
phần tử của mỗi dòng và mỗi cột đi một hằng số sao cho thu được ma trận không âm 
và mỗi cột cũng như mỗi dòng chứa ít nhất một số 0 , thì tổng các hằng số trừ đi đó sẽ 
cho ta cận dưới của mọi hành trình. Thủ tục trừ bớt này gọi là thủ tục rút gọn, các hằng 
số trừ ở mỗi dòng (cột) gọi là hằng số rút gọn dòng (cột), ma trận thu được gọi là ma 
trận rút gọn.
Thủ tục rút gọn:
 Đầu vào : Ma trận chi phí C = (cij)
 Đầu ra : Ma trận rút gọn và tổng hằng số rút gọn Sum
 Thuật toán:
(i) Khởi tạo :
 Sum := 0 ; (chỉ áp dụng cho ma trận chi phí ban đầu) 
(ii) Rút gọn dòng: 
 Với mỗi dòng r từ 1 đến n của ma trận C thực hiện :
 - Tìm phần tử crj = nhỏ nhất trên dòng.
 - Trừ tất cả các phần tử trên dòng đi một lượng .
 - Cộng dồn : Sum := Sum + 
(iii) Rút gọn cột: 
 Với mỗi cột c từ 1 đến n của ma trận C thực hiện :
 - Tìm phần tử cic = nhỏ nhất trên cột.
 - Trừ tất cả các phần tử trên cột đi một lượng .
 - Cộng dồn : Sum := Sum + 
 4. Phân nhánh
 Giả sử ta chọn cạnh phân nhánh (r, s). Như vậy các hành trình sẽ được chia làm 
hai tập: P1 chứa các hành trình qua (r,s) và P2 chứa các hành trình không qua (r,s).
+ Nhánh tập P1 : Cận dưới  với giá trị xuất phát có từ thủ tục rút gọn.
 - Giảm cấp ma trận chi phí C bằng cách loại dòng r và cột s.
 - Ngăn cấm tạo chu trình con : 
 Cấm cạnh (s,r) bằng cách đặt csr = .
 Nếu (r,s) là cạnh phân nhánh thứ hai trở đi thì phải xét các cạnh đã chọn nối 
trước và sau cạnh (r,s) thành dãy nối tiếp các cạnh như hình sau:
 ... ... 
 (i,j) ... (r,s) ... (k,h)
và cấm tất cả các cạnh dạng (h,i) bằng cách đặt chi = .
 Rút gọn ma trận chi phí ta có cận dưới  :=  + (tổng hằng số rút gọn).
 Ta có thể tiếp tục thủ tục phân nhánh theo nhánh này với ma trận chi phí đã PHẦN 2: THIẾT KẾ CẤU TRÚC DỮ LIỆU VÀ CÀI ĐẶT THUẬT TOÁN
1. Thiết kế CTDL
 Để giải quyết các vấn đề của đồ thị bằng máy tính chúng ta cần lưu giữ đồ thị 
trong bộ nhớ của máy tính. Do đó chúng ta cần đưa ra các phương pháp biểu diễn đồ 
thị bởi các cấu trúc dữ liệu. Có nhiều phương pháp biểu diễn đồ thị: biểu diễn đồ thị 
bằng ma trận kề, ma trận liên thuộc, danh sách cạnh(cung) và danh sách kề.
 Trong đề tài này đồ thị được lưu trữ bởi ma trận vuông COST[n][n], với n là số 
đỉnh của đồ thị và COST[I][J] là chi phí đi từ đỉnh i đến đỉnh j.
Ví dụ: Đồ thì sau. 
 20
 1 2
 10 20
 5 15 5 15
 5 8
 2
 4 20 3
 25
Đồ thị trên được lưu vào ma trận như sau:
 1 2 3 4
 1 20 5 15
 2 10 15 20
 3 8 5 20
 4 5 2 25 
2. Thuật toán
 Dựa vào phần lý thuyết ở trên thuật toán nhành cận được định nghĩa bởi các 
chương trình sau:
 2.1. Hàm rút gọn
Thủ tục rút gọn:
 + Đầu vào: Ma trận chi phí C = (cij)
 + Đầu ra: Ma trận rút gọn và tổng hằng số rút gọn Sum
 + Thuật toán:
(i) Khởi tạo: Sum := 0; 
(ii) Rút gọn dòng: 
 Với mỗi dòng r từ 1 đến n của ma trận C thực hiện :
 - Tìm phần tử crj = nhỏ nhất trên dòng.
 - Trừ tất cả các phần tử trên dòng đi một lượng .
 - Cộng dồn: Sum := Sum + 
(iii) Rút gọn cột: 
 Với mỗi cột c từ 1 đến n của ma trận C thực hiện :
 - Tìm phần tử cic = nhỏ nhất trên cột. Vậy cận dưới cho tất cả hành trình là  = 0 + sum = 81 
 (nghĩa là không có hành trình có tổng chi phí nhỏ hơn 81).
 2.2. Thủ tục phân nhánh
 Giả sử ta chọn cạnh phân nhánh (r, s). Như vậy các hành trình sẽ được chia làm 
hai tập: P1 chứa các hành trình qua (r, s) và P2 chứa các hành trình không qua (r,s).
+ Nhánh tập P1 : Cận dưới  với giá trị xuất phát có từ thủ tục rút gọn.
 - Giảm cấp ma trận chi phí C bằng cách loại dòng r và cột s.
 - Ngăn cấm tạo hành trình con: 
 Cấm cạnh (s, r) bằng cách đặt csr = .
 Nếu (r, s) là cạnh phân nhánh thứ hai trở đi thì phải xét các cạnh đã chọn nối 
 trước và sau cạnh (r,s) thành dãy nối tiếp các cạnh như hình sau
 ... ... 
 (i, j) ... (r, s) ... (k, h)
 và cấm tất cả các cạnh dạng (h,i) bằng cách đặt chi = .
 Rút gọn ma trận chi phí ta có cận dưới  :=  + (tổng hằng số rút gọn).
 Ta có thể tiếp tục thủ tục phân nhánh theo nhánh này với ma trận chi phí đã 
được hiệu chỉnh và giảm 1 bậc. Việc chọn cạnh nào để phân nhánh ta sẽ bàn ở mục 
tiếp theo.
+ Nhánh tập P2: 
 - Cấm cạnh (r,s) bằng cách đặt crs = .
- Thực hiện thủ tục rút gọn với ma trận chi phí tương ứng và tính cận dưới 
 :=  + (tổng hằng số rút gọn) cho nhánh.
 Ta có thể tiếp tục thủ tục phân nhánh theo nhánh này với ma trận chi phí đã 
được hiệu chỉnh cùng cận dưới tương ứng. Việc chọn cạnh nào để phân nhánh ta sẽ 
bàn ở mục tiếp theo.
+ Ví dụ. Xét tiếp ví dụ trên. Giả sử ta chọn cạnh phân nhánh là (r,s) = (6,3). Các hành 
trình sẽ được phân thành hai nhánh:
P1 chứa các hành trình qua cạnh (6, 3) và 
P2 chứa các hành trình không qua cạnh (6, 3).
 Xét nhánh tập P1:
 - Giảm cấp ma trận chi phí C bằng cách loại dòng 6 và cột 3.
 - Ngăn cấm tạo hành trình con: 
 Cấm cạnh (3, 6) bằng cách đặt c36 = .
Ta nhận được ma trận chi phí tương ứng cùng cận dưới xuất phát  = 81.
 1 2 4 5 6
 1 0 2 30 6
 2 0 30 17 12
 3 29 1 12 0 
 4 32 83 49 0
 5 3 21 0 0
 Vì ma trận đã ở dạng rút gọn nên cận dưới vẫn giữ nguyên  = 81.
 Ta có thể tiếp tục thủ tục phân nhánh theo nhánh này với ma trận chi phí đã được 
hiệu chỉnh. Việc chọn cạnh nào để phân nhánh ta sẽ bàn ở mục tiếp theo. 1 2 4 5 6
 1 0 2 30 6
 2 0 30 17 12
 3 29 1 12 0 
 4 32 83 49 0
 5 3 21 0 0
 - Đặt = - .
 - Xét các cặp (i,j) có cij = 0.
 Cặp (1,2) : minr = 2; mins = 1; 
 = - < minr + mins = 3 := 3; r := 1; s := 2;
 Cặp (2,1) : minr = 12; mins = 3; 
 = 3 < minr + mins = 15 := 15; r := 2; s := 1;
 Cặp (3,5) : minr = 1; mins = 17; 
 = 15 < minr + mins = 18 := 18; r := 3; s := 5;
 Cặp (4,6) : minr = 32; mins = 0; 
 = 18 < minr + mins = 32 := 32; r := 4; s := 6;
 Các cặp (5,4) và (5,6) có tổng minr + mins < , cho nên không làm 
thay đổi và (r,s). 
 Kết quả ta chọn được cạnh phân nhánh là (4,6).
 Tập hành trình P1 sẽ được phân thành 2 nhánh:
 P11 gồm các hành trình qua cạnh (4,6) và 
 P12 gồm các hành trình không qua cạnh (4,6).
 Nhánh P12: có ma trận chi phí tương ứng như sau
 1 2 4 5 6
 1 0 2 30 6
 2 0 30 17 12
 3 29 1 12 0 
 4 32 83 49 32
 5 3 21 0 0
Thực hiện thủ tục rút gọn ta được ma trận rút gọn
 1 2 4 5 6
 1 0 2 30 6
 2 0 30 17 12
 3 29 1 12 0 
 4 0 51 17 
 5 3 21 0 0
với tổng hằng số rút gọn = 32 và cận dưới  =  + = 81 + 32 = 113.
 Nhánh P11: 
 - Loại hàng 4 và cột 6 ta có sẽ có ma trận chi phí cấp 4 tương ứng:
 1 2 4 5 3 1 0
5 21 0 
1 
Ma trận chi phí được rút gọn như sau
 2 4 5
1 0 28
3 0 0
5 20 0 
Cận dưới  =  + = 81 + 3 = 84.
 Tương tự ta tiếp tục thủ tục chọn cạnh phân nhánh, phân nhánh và rút gọn đối 
với P111.
Chọn cạnh phân nhánh (1,4), tổng hằng số rút gọn tương ứng là 28 + 0 = 28.
 Tập P1112 gồm các hành trình trong P111 không qua (1,4) sẽ có cận dưới là  
=  + 28 = 84 + 28 = 112.
 Tập P1111 gồm các hành trình trong P111 qua (1,4) sẽ có ma trận chi phí cấp 2 
tương ứng:
 2 5
3 0
5 20 
 20 
Cạnh (1,4) nối tiếp cùng các cạnh chọn trước là (6,3) , (4,6) và (2,1) thành dây
 (2,1),(1,4),(4,6),(6,3) ,
nên ta phải cấm cạnh (3,2), bằng cách đặt c32 = .
Rút gọn ma trận này ta được ma trận rút gọn
 2 5
3 0
5 0 
và cận dưới  =  + = 84 + 20 = 104.
 2.4. Chọn 2 cạnh cuối cùng Cận dưới Cận dưới
 = P =
 P2
 Tất cả hành trình
 81 hành trình không chứa (6,3) 129
 P1
 P12
 hành trình hành trình
 81 chứa (6,3) không chứa (4,6) 113
 P11
 hành trình P112 hành trình
 81 chứa (4,6) không chứa (2,1) 101
 P111
 hành trình P1112 hành trình
 84 chứa (2,1) không chứa (1,4) 112
 P1111
 hành trình 
 104 chứa (1,4) 
 Chọn tiếp hai cạnh còn lại ta có hành trình:
 p = (1,4),(4,6),(6,3),(3,5),(5,2),(2,1) và chi phí cp = 104
 Qua sơ đồ trên ta thấy các nhánh P 2 , P12 , P1112 có cận dưới lớn hơn c p = 104, 
vì thế các hành trình của các nhánh đó có tổng chi phí lớn hơn c p . Chỉ có nhánh P112 
có cận dưới là 101 nhỏ hơn cp . Tiếp theo ta tìm hành trình mới theo nhánh này.
 Nhánh P112 sẽ có ma trận chi phí cấp 4 tương ứng:
 1 2 4 5
1 0 2 30
2 30 17 17
3 29 1 0
5 3 21 0 
 3 
ở đây c21 = để cấm cạnh (2,1). Cận dưới xuất phát của P11 là  = 81.