Bài toán tối ưu: Trong nhiều bài toán thực tế yêu cầu chúng tìm nghiệm thỏa mãn những điều kiện nào đó và nghiệm này phải tốt nhất theo tiêu chí cụ thể nào đó. Phương pháp Nhánh cận là một dạng cải tiến của phương pháp quay lui dùng để giải quyết bài toán tối ưu. | PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN – NHÁNH CẬN – Chương 5 1 Nội dung Giới thiệu Bài toán tối ưu Phương pháp Sơ đồ cài đặt Các ví dụ Hình ảnh Giới thiệu Bài toán tối ưu: Trong nhiều bài toán thực tế yêu cầu chúng tìm nghiệm thỏa mãn những điều kiện nào đó và nghiệm này phải tốt nhất theo tiêu chí cụ thể nào đó. Phương pháp Nhánh cận là một dạng cải tiến của phương pháp quay lui dùng để giải quyết bài toán tối ưu Bài toán tối ưu Phát biểu bài toán: Giả sử bài toán yêu cầu tìm phương án X=(x1, x2, , xk, ) thỏa mãn những điền kiện nào đó và phương án này là tốt nhất theo tiêu chí cụ thể nào đó. Gọi f(X) là hàm đánh giá sự tốt nhất của phương án X (f là hàm mục tiêu hay hàm chi phí) Yêu cầu: Tìm X sao cho f(X) min (max) 5 Bài toán tối ưu Nếu gọi X* là phương án tốt nhất (tối ưu) f* = f(X*) được gọi là giá trị tối ưu của bài toán Bài toán tối ưu Ví dụ 1 [Bài toán người du lịch – Traveling Salesman Problem – TSP] Cho n thành phố được đánh số từ 1 đến n và khoảng cách giữa thành phố i và thành phố j được cho bởi cij (chú ý: cij=cji) Yêu cầu: Tìm một hành trình ngắn nhất cho phép viếng thăm n thành phố, mỗi thành phố viếng thăm đúng 1 lần và quay về thành phố ban đầu. Bài toán tối ưu Mô hình toán học: Một hành trình là 1 hoán vị X=(x(1), x(2), , x(n)) của n số {1, 2, , n} Hàm mục tiêu: Yêu cầu: Bài toán tối ưu Ví dụ 2 [Bài toán phân công – Job Assignment Problem – JAP] Có n công việc và n nhân viên. Gọi cij là chi phí để trả cho nhân viên i khi làm công việc j. Yêu cầu: Tìm cách phân công n nhân viên làm n việc trên sao cho tổng chi phí là nhỏ nhất (một nhân viên chỉ làm 1 việc, một việc chỉ do 1 nhân viên làm). Bài toán tối ưu Mô hình toán học: Một cách phân công n nhân viên làm n việc là 1 hoán vị X=(x(1), x(2), , x(n)) của n số {1, 2, , n} Hàm mục tiêu: Yêu cầu: 10 Bài toán tối ưu Ví dụ 3 [Bài toán cái túi – 0-1 Knapsack problem] Cho n loại đồ vật được đánh số từ 1 đến n, đồ vật thứ i có giá trị vi và trọng lượng wi. Cho trước cái túi có trọng lượng tối đa mà | PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN – NHÁNH CẬN – Chương 5 1 Nội dung Giới thiệu Bài toán tối ưu Phương pháp Sơ đồ cài đặt Các ví dụ Hình ảnh Giới thiệu Bài toán tối ưu: Trong nhiều bài toán thực tế yêu cầu chúng tìm nghiệm thỏa mãn những điều kiện nào đó và nghiệm này phải tốt nhất theo tiêu chí cụ thể nào đó. Phương pháp Nhánh cận là một dạng cải tiến của phương pháp quay lui dùng để giải quyết bài toán tối ưu Bài toán tối ưu Phát biểu bài toán: Giả sử bài toán yêu cầu tìm phương án X=(x1, x2, , xk, ) thỏa mãn những điền kiện nào đó và phương án này là tốt nhất theo tiêu chí cụ thể nào đó. Gọi f(X) là hàm đánh giá sự tốt nhất của phương án X (f là hàm mục tiêu hay hàm chi phí) Yêu cầu: Tìm X sao cho f(X) min (max) 5 Bài toán tối ưu Nếu gọi X* là phương án tốt nhất (tối ưu) f* = f(X*) được gọi là giá trị tối ưu của bài toán Bài toán tối ưu Ví dụ 1 [Bài toán người du lịch – Traveling Salesman Problem – TSP] Cho n thành phố được đánh số từ 1 đến n và khoảng cách giữa thành phố i và
