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

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Bài 10 - TS. Nguyễn Văn Hiệu 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 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 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. 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) 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 Ý 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 đủ 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 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. 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; 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; 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 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 ...