TAILIEUCHUNG - Bài giảng Toán rời rạc (Phần I: Lý thuyết tổ hợp): Chương 4 - Nguyễn Đức Nghĩa

Chương 4 trình bày những kiên thức cơ bản liên qua đến bài toán tối ưu tổ hợp như: Phát biểu bài toán, duyệt toàn bộ, thuật toán nhánh cận. . | Chương 4 BÀI TOÁN TỐI ƯU TỔ HỢP Nội dung 1. Phỏt biểu bài toỏn 2. Duyệt toàn bộ 3. Thuật toỏn nhỏnh cận 1. Phỏt biểu bài toỏn . Bài toỏn tổng quỏt . Bài toỏn người du lịch . Bài toỏn cỏi tỳi . Bài toỏn đúng thựng Trong rất nhiều vấn đề ứng dụng thực tế của tổ hợp, cỏc cấu hỡnh tổ hợp được gỏn cho một giỏ trị bằng số đỏnh giỏ giỏ trị sử dụng của cấu hỡnh đối với mục đớch sử dụng cụ thể nào đú. Khi đú xuất hiện bài toỏn: Hóy lựa chọn trong số cỏc cấu hỡnh tổ hợp chấp nhận được cấu hỡnh cú giỏ trị sử dụng tốt nhất. Cỏc bài toỏn như vậy chỳng ta sẽ gọi là bài toỏn tối ưu tổ hợp. Phỏt biểu bài toỏn Dưới dạng tổng quát bài toán tối ưu tổ hợp có thể phát biểu như sau: Tìm cực tiểu (hay cực đại) của phiếm hàm f(x) min (max), với điều kiện x D, trong đó D là tập hữu hạn phần tử. Cỏc thuật ngữ f(x) - hàm mục tiêu của bài toán, x D - phương án D - tập các phương án của bài toán. Thông thường tập D được mô tả như là tập các cấu hình tổ hợp thoả mãn một số tính chất cho trước nào đó. Phương án x* D đem lại giá trị nhỏ nhất (lớn nhất) cho hàm mục tiêu được gọi là phương án tối ưu, khi đó giá trị f* = f(x*) được gọi là giá trị tối ưu của bài toán. 1. Phỏt biểu bài toỏn . Bài toỏn tổng quỏt . Bài toỏn người du lịch . Bài toỏn cỏi tỳi . Bài toỏn đúng thựng Bài toán người du lịch (Traveling Salesman Problem – TSP) Một người du lịch muốn đi tham quan n thành phố T1, T2, ., Tn. Hành trỡnh là cỏch đi xuất phát từ một thành phố nào đó đi qua tất cả các thành phố còn lại, mỗi thành phố đúng một lần, rồi quay trở lại thành phố xuất phát. Biết cij là chi phí đi từ thành phố Ti đến thành phố Tj (i, j = 1, 2,., n), Tìm hành trình với tổng chi phí là nhỏ nhất. Sơ lược về lịch sử The origins of the TSP are obscure. In the 1920s, the mathematician and economist Karl Menger publicized it among his colleagues in Vienna. In the 1930s, the problem reappeared in the mathematical circles of Princeton. In the 1940s, it was studied by .

• Kỹ thuật lập trình
• Toán rời rạc
• Bài giảng Toán rời rạc
• Lý thuyết tổ hợp
• Bài toán tối ưu tổ hợp
• Thuật toán nhánh cận
• Phát biểu bài toán
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc