1 2 3 4 5 6 x[i] 1 3 93 13 33 9 2 477422116 34517361628 4399080567 52846883325 6 388184692 s[j]
Áp dụng phương pháp rút gọn ma trận:
Bước 1: Trừ mỗi phần tử của các dòng cho các hằng số nhỏ nhất trong từ 1 2 3 4 5 6 x[i] 1 0 90 10 30 6 3 2 0733817124 32912001216 4328373490 7 5321638025 6 0851543893 s[j]
Bước 2: Ma trận mới thu được lại tiếp tục trừ các phần tử của các cột cho 1 2 3 4 5 6 x[i] 1 0 75 2 30 6 3 2 0583017124 32911201216 4328358490 7 5321480025 6085035893 s[j] 0 0 15 8 0 0
Bước 3: Tính tổng các hằng số rút gọn ở trên. Ta thu được cận dưới cho t
Bước 4: Phân tập các phương án của bài toán bằng phương án phân nhán
Chọn cạnh phân nhánh bằng cách tìm số 0 nào trong ma trận mà khi thay nó b
* Giả sử chọn cạch (6,3) "dòng 6; cột 3 " để phân nhánh - Đặt C(6,3) =
+ Mã trận rút gọn các hành trình có chứa cạnh (6,3)+ Mã trận rút gọn cá
(bỏ cột 3, dòng 6 của ma trận tạo được ở bước 2) (rút bớt mỗi phần tử + Có cận dưới = 81 + Có cận dưới = 81 + 1 2 4 5 6 x[i] 1 2 3 1 0 2 30 6 1 0 27 2 0 30 17 12 2 0 10 3 29 1 12 0 3 29 1 4 32 83 49 0 4 32 83 10 5 3 21 0 0 5 3 21 0 s[j] 6 0 85 s[j] 0 0 48
Bước 5: Ngăn cấm tạo thành hành trình con
Do đã đi theo cạnh (6,3) nên không được phép đi từ 3 đến 6 => cấm cạnh (3,6 * Tiếp tục phân nhánh
- Xét ma trận 5x5 vừa tạo được:
+ Số 0 ở vị trí (4,6) có hằng số rút gọn = 32 + 0 = 32 là lớn nhất + Cận dưới = 81
=> Hành trình chứa (6,3), (4,6): => Hành trình chứa (
(bỏ dòng 4, cột 6 của ma trận 5x5) (rút bớt mỗi phần tử 1 2 4 5 x[i] 1 2 4 1 0 2 30 1 0 2 2 0 30 17 2 0 30 3 29 1 0 3 29 1 12 5 3 21 0 4 0 51 s[j] 5 3 21 0 s[j]
- Ngăn cấm: vì cạnh (6,3) và (4,6) đã nằm trong hành trình con nên cạnh (3,4) * Tiếp tục phân nhánh -
xét ma trận 4x4 vừa tạo:
+ Số 0 ở vị trí (2,1) có hằng số rút gọn = 17 + 3 = 20 là
lớn nhất + Cận dưới = 81
=> Hành trình chứa (6,3), (4,6), (2,1): => Hành trình chứa (
(bỏ dòng 2, cột 1 của ma trận 4x4) (rút bớt mỗi phần tử
+ Ngăn cấm: Vì đã đi qua (2,1)
nên cấm cánh (1,2) => đăt (1,2) = 2 4 5 x[i] 1 2 4 1 2 30 1 0 2 3 1 0 2 15 5 21 0 3 26 1 s[j] 5 0 21 0 s[j] 3 *
Rút gọn ma trận 3x3 vừa tạo
(bớt 1 từ cột 2; bớt 2 từ dòng 1) 2 4 5 x[i] 1 0 28 2 3 0 0 5 20 0 s[j] 1
=> cận dưới của nhánh: 81 + 3 = 84 **** Tiếp tục phân nhánh
- xét ma trận 3x3 vừa được rút gọn:
+ Số 0 ở vị trí (1,4) có hằng số rút gọn = 28 + 0 = 28 là lớn nhất + Cận dưới = 84
=> Hành trình chứa (6,3), (4,6), (2,1), (1,4):
(bỏ dòng 1, cột 4 của ma trận 3x3)
+ Ngăn cấm: Vì đã đi qua (6,3) và (2,1)
nên cấm cánh (3,2) => đăt (3,2) = 2 5 x[i] 3 0 5 20 s[j]
***** Rút gọn ma trận 2x2 vừa tạo
(bớt 20 từ cột 2; gữa nguyên (không bớt) dòng 5) 2 5 x[i] 3 0 0 5 0 s[j] 20
=> cận dưới của nhánh: 84 +20 = 104
Bước 6: Kết thúc (thuật toán dừng)
- Sau khi đã chấp nhận n-2 cạnh vào hành trình thì ma trận còn lại sẽ có kích t
- Hai cạnh còn lại của hành trình sẽ không phải chọn và được kết nạp
ngay và => kết nạp hai cạnh (3,5) và (5,2) vào (6,3), (4,6), (2,1), (1,4)
ta thu được hàn 1, 4, 6, 3, 5, 2, 1 với chi phí là 104 ng dòng đó
o hằng số nhỏ nhất trong từng cột
ất cả các hành trình = 81 nh
bởi ∞ sẽ cho ta tổng hằng số rút gọn theo dòng và cột chứa nó là lớn nhất
c hành trình không chứa cạnh (6,3)
của cột 3 đi 48; không bớt gì các phần tử của dòng 6) +48=129 4 5 6 x[i] 2 30 6 30 17 12 12 0 12 49 0 0 0 35 89 0 0 0 0 6): đặt (3,6) = (6,3) không chứa (4,6):
của dòng 4 đi 32; không bớt gì các phần tử của cột 6 trong ma trận 5x5) 5 6 x[i] 30 6 17 12 0 cận dưới = 81 + 32 = 113 17 32 0 0
) không thể được đi qua => gán (3,4) =
(6,3), (4,6) nhưng không chứa (2,1):
của dòng 2 đi 17; bớt các phần tử của cột 1 đi 3) 5 x[i] 30 0
17cận dưới = 81 + 20 = 101 0 thước 2x2 o chu trình h trình: