intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Toán rời rạc: Bài 10 - TS. Nguyễn Văn Hiệu

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST
Báo xấu
153
lượt xem 26
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhằm giúp các bạn chuyên ngành Toán học có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu, mời các bạn cùng tham khảo nội dung bài 10 "Bài toán người du lịch" thuộc bài giảng Toán rời rạc dưới đây. Nội dung bài giảng trình bày về: Phát biểu bài toán, phân tích, ý tưởng, thuật giải của bài toán người du lịch.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Bài 10 - TS. 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 Tj  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ị (xi, xi+1) là cạnh  Mỗi đường đi giữa các 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) được một hành trình (i,j) đầ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:  Tìm phần tử nhỏ nhất của cột:  ma trận rút gọn; 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2