tailieunhanh - 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. | TOPICA C1I HIIU law IA ÕUẬỄ If 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 Slofjk i 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 Bài toàn người du lịch và bài toán cái túi Phương pháp duyệt toàn bộ Kỹ thuật đánh giá nhánh cận Phương pháp tham lam Bài toán tìm lịch gia công trên hai máy và thuật toán Johnson Sau khi học bài này các bạn có thể Nắm được yêu cầu của bài toán tối ưu tổ hợp một số bài toán điển hình Sử dụng được các phương pháp Duyệt toàn bộ Đánh giá nhánh cận 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 83 TOPICA C1I HIIU law IA ÕUẬỄ If 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 Bài 4 Bài toán tối ưu tổ hợp . 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