Bài giảng Bài toán tối ưu tổ hợp -Topica

Bài giảng Bài toán tối ưu tổ hợp trình bày nội dung bài toán tối ưu tổ hợp là bài toán chỉ quan tâm đến một cấu hình “tốt nhất” theo một nghĩa nào đấy. Đây là bài toán có nhiều ứng dụng trong thực tiễn và lý thuyết tổ hợp đã đóng góp một phần đáng kể trong việc xây dựng những thuật toán hữu hiệu.
Nội dung trích xuất từ tài liệu:
Bài giảng Bài toán tối ưu tổ hợp -Topica Bài 4: Bài toán tối ưu tổ hợp BÀI 4: BÀI TOÁN TỐI ƯU TỔ HỢP Giới thiệu Bài học này trình bày nội dung bài toán tối ưu tổ hợp là bài toán chỉ quan tâm đến một cấu hình “tốt nhất” theo một nghĩa nào đấy. Đây là bài toán có nhiều ứng dụng trong thực tiễn và lý thuyết tổ hợp đã đóng góp một phần đáng kể trong việc xây dựng những thuật toán hữu hiệu. Nội dung Mục tiêu  Giới thiệu bài toán tối ưu tổ hợp Sau khi học bài này, các bạn có thể:  Bài toàn người du lịch và bài toán cái túi  Nắm được yêu cầu của bài toán tối ưu tổ  Phương pháp duyệt toàn bộ hợp, một số bài toán điển hình  Kỹ thuật đánh giá nhánh cận  Sử dụng được các phương pháp:  Phương pháp tham lam  Duyệt toàn bộ  Bài toán tìm lịch gia công trên hai máy  Đánh giá nhánh cận và thuật toán Johnson  Tham lam trong việc giải quyết bài toán tối ưu tổ hợp Thời lượng học  6 tiết v1.0 83 Bài 4: Bài toán tối ưu tổ hợp TÌNH HUỐNG DẪN NHẬP Tình huống: Bài toán người du lịch Có n thành phố (đánh số từ 1 đến n). Một người du lịch, xuất phát từ thành thành phố s, muốn đi thăm tất cả các thành phố khác, mỗi thành phố đúng một lần, rồi lại quay về nơi xuất phát. Giả thiết biết chi phí đi từ thành phố i đến thành phố j là c(i, j), 1 ≤ i, j ≤ n. Câu hỏi Hãy tìm một hành trình cho người du lịch sao cho chi phí của hành trình này là nhỏ nhất! 84 v1.0 Bài 4: Bài toán tối ưu tổ hợp 4.1. Giới thiệu bài toán Bài toán tối ưu tổ hợp không quan tâm đến việc xây dựng tất cả các cấu hình như bài toán liệt kê mà chỉ nhằm xây dựng một cấu hình “tốt” nhất theo một nghĩa nào đấy. Vì thế nó là bài toán có nhiều ý nghĩa thực tiễn hơn cả. Lời giải của nó, cũng giống như bài toán liệt kê, phải được trình bày dưới dạng một thuật giải mà theo từng bước, ta xây dựng được cấu hình cần tìm. Việc thi hành được giao cho máy tính bằng một chương trình thực hiện thuật giải đã nêu. Độ “tốt” của cấu hình phụ thuộc vào mục tiêu của bài toán và người ta phải lượng hóa chúng để có thể so sánh. Một cách thường làm là xây dựng một hàm f, ứng mỗi cấu hình X được xét với một con số, ký hiệu f(X) (gọi là giá của X). Khi đó, độ “tốt” của cấu hình được định nghĩa theo hai hướng: nếu mục tiêu của bài toán là chi phí thì cấu hình càng tốt nếu giá của nó càng nhỏ (như thế cấu hình tốt nhất là cấu hình có giá nhỏ nhất), nếu mục tiêu là hiệu quả thì cấu hình càng tốt nếu giá của nó càng lớn (như thế cấu hình tốt nhất là cấu hình có giá lớn nhất). Bài toán thứ nhất gọi là bài toán tìm min, bài toán thứ hai gọi là bài toán tìm max. Như vậy, bài toán tối ưu tổ hợp có thể phát biểu dưới hình thức toán học như sau: Tìm X  D : f (X)  min (max) trong đó D là tập hữu hạn, gồm các cấu hình thỏa mãn điều kiện của bài toán. Hàm f được gọi là hàm mục tiêu. Tập hợp D được gọi là miền xác định hay miền phương án. Mỗi phần tử của D được gọi là một phương án. Phương án tốt nhất được gọi là phương án tối ưu. Giá của phương án tối ưu được gọi là giá trị tối ưu. Chú ý rằng do D hữu hạn nên phương án tối ưu bao giờ cũng tồn tại. Có thể có nhiều phương án tối ưu, nhưng giá trị tối ưu là duy nhất. Trong mỗi bài toán cụ thể, ta phải chỉ rõ các điều kiện xác định D và cách tính hàm f (hàm f có thể tính bằng một công thức hoặc bằng một thủ tục). Mục dưới đây giới thiệu hai bài toán điển hình của tối ưu tổ hợp là bài toán người du lịch và bài toán cái túi. 4.2. Bài toán người du lịch và bài toán cái túi 4.2.1. Bài toán người du lịch Bài toán người du lịch được phát biểu như sau: “Có n thành phố (đánh số từ 1 đến n). Một người du lịch, xuất phát từ thành thành phố s, muốn đi thăm tất cả các thành phố khác, mỗi thành phố đúng một ...