Bài giảng Toán rời rạc - Bài 10: Bài toán người du lịch - Nguyễn Văn Hiệu

Nội dung text: Bài giảng Toán rời rạc - Bài 10: Bài toán người du lịch - Nguyễn Văn Hiệu

1. BÀI TOÁN NGƯỜI DU LỊCH Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn
2. Nội dung • Phát biểu bài toán • Phân tích • Ý tưởng • Thuật giải của bài toán – Thủ tục rút gọn để tính cận dưới – Thủ tục phân nhánh – Thủ tục chọn cận phân nhánh – Thủ tục chọn hai cạnh cuối cùng
3. Bài toán . Có n thành phố ký hiệu: • Hãy tìm hành trình T1, T2, , Tn (chu trình) với chi phí . Cij là chi phí từ thành phố Ti nhỏ nhất đến T j . Xuất phát từ một thành phố nào đó đi qua tất cả các thành phố mỗi thành phố đúng một lần, rồi quay trở lại thành phố xuất phát.
4. Phân tích • Xét đồ thị có trọng: . Nhận xét: G = (V, E) . Đồ thị ứng dụng có thể . Mỗi thành phố là một có hướng hoặc vô đỉnh của đồ thị hướng; . Mỗi đường đi giữa các . Các cặp đinh không có thành phố là một cạnh đường đi gán trọng số nối giữa các đỉnh của đồ ∞, thị . Tạo nên một chu trình ( đỉnh xuất phát trùng với đỉnh kết thúc)
5. Phân tích • Xét đồ thị có trọng: . Đường đi tìm được: G = (V, E) x1, x2, , xn, x1 . Mỗi thành phố là một với xi là đỉnh, đỉnh của đồ thị (x , x ) là cạnh . Mỗi đường đi giữa các i i+1 thành phố là một cạnh . Bài toán người du lịch: nối giữa các đỉnh của đồ f(x1 xn)=c[x1,x2]+ +c[xn, x1] thị min
6. Ý tưởng  Thực hiện quá trình phân nhánh Tập tất cả các hành trình  Tính giá trị cận dưới trên mỗi tập  Thủ tục cứ tiếp tục Tập hành trình cho đến lúc nhận Tập hành trình không chứa chứ (i,j) (i,j) được một hành trình đầy đủ
7. Thuật giải 1. Thủ tục rút gọn để tính cận dưới 2. Thủ tục chọn cạnh phân nhánh 3. Thủ tục phân nhánh 4. Thủ tục chọn hai cạnh cuối cùng
8. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Cơ sở lý luận Cơ sở lý luận . Hành trình của người du . Nếu trừ bớt mỗi phần tử của lịch sẽ chứa đúng một phần một cột của ma trận chi phí tử của mỗi dòng và đúng đi cùng một số b, thì độ dài một phần tử của mỗi cột của tất cả các hành trình cũng ma trận chi phí. sẽ giảm đi b. . Nếu trừ bớt mỗi phần tử của . Nhận xét một dòng của ma trận chi Hành trình tối ưu sẽ không phí đi cùng một số a , thì độ bị thay đổi dài tất cả các hành trình cũng sẽ giảm đi a.
9. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Thủ tục Khái niệm . Từ ma trận chi phí tiến hành . Thủ tục này được gọi là thủ bớt đi các phần tử của mỗi tục rút gọn; dòng và của mỗi cột đi một . Ma trận thu được gọi là ma hằng số: trận rút gọn; . Các phần tử của ma trận . Hàng số trừ ở mỗi dòng không âm; hoặc mỗi cột gọi là hằng số . Mỗi hàng chứa ít nhất một phần tử 0; rút gon; . Mỗi cột chứa ít nhất một phần tử 0;
10. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Nhận xét Thủ tục . Ma trận rút gọn: Input: ma trận chi phí C . Các phần tử của ma trận Output: không âm;  ma trận rút gọn; . Mỗi hàng chứa ít nhất một phần tử 0;  tổng hằng số rút gọn. . Mỗi cột chứa ít nhất một phần tử 0;
11. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Thủ tục a. Rút gọn dòng Input: ma trận chi phí C . Khởi tạo: Sum = 0 Output: . Ứng với mỗi dòng:  ma trận rút gọn; . Tìm phần tử nhỏ nhất của dòng: ví dụ là r  tổng hằng số rút gọn. . Trừ tất cả các phần tử trên dòng bởi phần tử r . Sum = Sum + r
12. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Thủ tục a. Rút gọn trên dòng Input: ma trận chi phí C 3 93 13 33 9 3 Output: 4 77 42 21 16 4  ma trận rút gọn;  tổng hằng số rút gọn. 45 17 36 16 28 16 39 90 80 56 7 7 28 46 88 33 25 25 3 88 18 46 92 3
13. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Thủ tục a. Rút gọn trên dòng Input: ma trận chi phí C 0 90 10 30 6 3 Output: 0 73 38 17 12 4  ma trận rút gọn;  tổng hằng số rút gọn. 29 1 20 0 12 16 32 83 73 49 0 7 3 21 63 8 0 25 0 85 15 43 89 3 Sum = 58
14. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Thủ tục b. Rút gọn trên cột Input: ma trận chi phí C Sum = 58 Output: 0 90 10 30 6  ma trận rút gọn; 0 73 38 17 12  tổng hằng số rút gọn. 29 1 20 0 12 32 83 73 49 0 3 21 63 8 0 0 85 15 43 89 15 8
15. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Thủ tục b. Rút gọn trên cột Input: ma trận chi phí C Sum = 58 Output: 0 75 10 30 6  ma trận rút gọn; 0 58 38 17 12  tổng hằng số rút gọn. 29 1 20 0 12 32 83 58 49 0 3 21 48 8 0 0 85 0 43 89 15 8 Sum = 81
16. Thuật giải 1. Thủ tục rút gọn để tính cận dưới Thủ tục b. Rút gọn cột Input: . Khởi tạo: Sum = Sum (từ Ma trận chi phí C thủ tục rút gọn hàng) Output: . Ứng với mỗi cột:  ma trận rút gọn; . Tìm phần tử nhỏ nhất của cột: ví dụ c;  tổng hằng số rút gọn. . Trừ tất cả các phần tử trên cột bởi phần tử c . Sum = Sum + c
17. Thuật giải 1. Thủ tục rút gọn để tính cận dưới 2. Thủ tục chọn cạnh phân nhánh 3. Thủ tục phân nhánh 4. Thủ tục chọn hai cạnh cuối cùng
18. Thuật giải 2. Thủ tục chọn cạnh phân nhánh Ý tưởng Thủ tục . Chọn cạnh phân nhánh (r,s) Input: sao cho cận dưới của tập Ma trận rút gọn phân nhánh không chứ Output: cạnh(r,s) tăng lớn nhất Cạnh phân nhánh (r,s)
19. Thuật giải 2. Thủ tục chọn cạnh phân nhánh Thủ tục Thủ tục Input: . Khởi tạo: 훼 := −∞ Ma trận rút gọn . Với mỗi cặp i, j với Cij = 0 (i,j =1, ,n) tính Output: . Xác định: Cạnh phân nhánh (r,s) • minr = min {Ci h :h ≠ j} (tính giá trị nhỏ nhất trên hàng i) • mins = min{Ch j :h ≠ j} (tính giá trị nhỏ nhất trên cột j) . Nếu 휶 < minr + mins, • 휶 := minr + mins, • r = i, s = j;
20. Thuật giải 2. Thủ tục chọn cạnh phân nhánh Thủ tục Thủ tục Input: r = 6, s = 3 Ma trận rút gọn 0 75 10 30 6 Output: 0 58 38 17 12 Cạnh phân nhánh (r,s) 29 1 20 0 12 32 83 58 49 0 3 21 48 8 0 0 85 0 43 89 훼 = 48
21. Thuật giải 1. Thủ tục rút gọn để tính cận dưới 2. Thủ tục chọn cạnh phân nhánh 3. Thủ tục phân nhánh 4. Thủ tục chọn hai cạnh cuối cùng
22. Thuật giải 3. Thủ tục phân nhánh Thủ tục . Giả sử ở bước 2 đã r = 6, s = 3 P chọn cạnh (r,s) để phân (81)P1 (6,3) nhánh thì đặt: P2 . P1 -hành trình đi qua (r,s) . P2 không đi qua (r,s)
23. Thuật giải 3. Thủ tục phân nhánh a. Thủ tục trên P1 a. Thủ tục trên P1 . Cận dưới là sum (giá trị từ thủ tục . Rút gọn ma trận chi phí rút gọn) . Và tính cận dưới: . Giảm cấp ma trận: sum += tổng hằng số rút gọn . Loại hàng r, . Loại cột s. => Tiếp tục thực hiện thủ tục . Ngăn cấm tạo hành trình con: phân nhánh theo nhánh này . Cấm (s, r) gán: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ư: (i,j) (r,s) (k,h) thì cấm (h,j) tức Ch i = ∞
24. Thuật giải 3. Thủ tục phân nhánh a. Thủ tục trên P1 0 75 10 30 6 0 58 38 17 12 29 1 20 0 32 83 58 49 0 3 21 48 8 0 0 85 0 43 89
25. Thuật giải 3. Thủ tục phân nhánh Thủ tục b. Thủ tục trên P2 . Cận dưới là sum (giá trị từ thủ tục . Giả sử ở bước 2 đã rút gọn) chọn cạnh (r,s) để phân . Cấm cạnh (r,s) bằng Cr s = ∞ . Thực hiện thủ tục rút gọn ma nhánh thì đặt: trận chi phí . Tính cận dưới: . P là hành trình đi qua (r,s) 1 sum += tổng hằng số rút gọn . P2 không đi qua (r,s) => Tiếp tục thực hiện phân nhánh theo nhánh này
26. Thuật giải 3. Thủ tục phân nhánh b. Thủ tục trên P2 0 75 10 30 6 0 58 38 17 12 29 1 20 0 32 83 58 49 0 3 21 48 8 0 0 85 43 89
27. Thuật giải 1. Thủ tục rút gọn để tính cận dưới 2. Thủ tục chọn cạnh phân nhánh 3. Thủ tục phân nhánh 4. Thủ tục chọn hai cạnh cuối cùng
28. Thuật giải 4. Thủ tục chọn hai cạnh cuối cùng Thủ tục Thủ tục . Sau khi đã chọn n-2 uv uv cạnh, chúng ta phải p 0 p 0 chọn tiếp hai cạnh còn q 0 lại. q 0 . Lúc này ma trận rút gọn bậc hai có 1 trong hai dạng:
29. Ví dụ minh họa 3 93 13 33 9 4 77 42 21 16 45 17 36 16 28 39 90 80 56 7 28 46 88 33 25 3 88 18 46 92
30. ĐS P (81)P1 (6,3) (4,6) (81)P11 (84)P (129) P2 (2,1) 111 (113)P 12 (1,4) (101)P112 (104)P1111 (5,1) (112)P1112 (127)P 1122 (103)P1121 (1,4) (114)P11212 (104)P11211
31. Bài tập 27 43 16 30 26 7 14 1 30 25 20 13 35 5 0 21 16 25 18 18 12 46 27 48 5 23 5 5 9 5
32. THAT’S ALL; THANK YOU What NEXT?