Đệ Quy Quay Lui Nhánh Cận

Đệ Quy Quay Lui Nhánh Cận Trainer: Thien Nguyen 16/09/2012 Tổng quan Đệ quy (Recursion ) Quay Lui (Backtracking) Nhánh Cận (Branch-and-Bound) 2 1. Đệ quy Đệ quy là gì? Cấu trúc Chương trình con đệ quy 3 1. Đệ quy Đệ quy là gì? Một khái niệm X được định nghĩa theo đệ quy nếu trong định nghĩa X có sử dụng ngay chính khái niệm X. VD: + Bố mẹ tôi là tổ tiên của tôi. Bố mẹ của tổ tiên tôi cũng là tổ tiên của tôi. 4 1. Đệ quy Cấu trúc: Một khái niệm đệ qui căn bản gồm hai phần. + Phần cơ sở: Định nghĩa với trường hợp đơn giản nhất, không gọi lại chính nó. + Phần đệ qui: Định nghĩa các trường hợp còn lại, và gọi lại chính khái niệm đang định nghĩa. 5 1. Đệ quy Cấu trúc: VD: + 0 là số tự nhiên. + n là số tự nhiên nếu n-1 là số tự nhiên. 6 1. Đệ quy Chương trình con đệ quy: Một chương trình con đệ qui căn bản gồm hai phần. + Phần cơ sở: thực hiện các thao tác với đối số cơ bản và không gọi lại chính nó. + Phần đệ qui: thực hiện các câu lệnh mà trong đó có ít nhất một lần gọi lại chính nó với đối số đơn giản hơn. 7 1. Đệ quy Chương trình con đệ quy: VD: int giaithua(int n) { if (n == 0) return 1; else return n * giaithua(n-1); } 8 2. Quay Lui: Khái niệm Bản Chất Phương pháp Mã giả 9 2. Quay Lui: Khái niệm: Quay lui (tiếng Anh: backtracking) là một chiến lược tìm kiếm lời giải cho các bài toán thỏa mãn ràng buộc. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán họcngười Mỹ D. H. Lehmer vào những năm 1950. -Wikipedia- 10 2. Quay Lui: Khái niệm: Quay lui là một chiến lược tìm kiếm lời giải cho các bài toán mà nghiệm của nó là một hay một tập cấu hình thỏa mãn đồng thời 2 tính chất P và Q. + P: Cách xác định một cấu hình + Q: Tính dừng của bài toán. Cấu hình là một tập v = (v1, v2, , vn), với vi thuộc tập D cho trước. 11 2. Quay Lui: Khái niệm: VD: Liệt kê tất cả các hoán vị của tập gồm n số tự nguyên dương đầu tiên theo thứ tự từ điển. N = 3: 123, 132, 213, 231, 312, 321 12 2. Quay Lui: Bản chất: Bản chất của Quay lui là một quá trình tìm kiếm theo chiều sâu (Depth-First Search). 13 2. Quay Lui: Phương pháp: Giả sử v = (v1, v2, , vn) là cấu hình cần tìm, hiện tại đã tìm được k-1 phần tử của v là v1, v2, , vk-1. Ta tìm phần tử thứ k bằng cách duyệt hết tất cả các khả năng 𝑖 ∈ 𝐷 có thể của vk, với mỗi khả năng i kiểm tra xem có thể chấp nhận được không (thỏa mãn P). Có 2 khả năng: 14 2. Quay Lui: Phương pháp (t.t): Kiểm tra vk thỏa P. Có 2 khả năng: + Nếu vk thỏa P, kiểm tra Q. Nếu thỏa Q (đk dừng) thì ta dừng tìm kiếm và xuất kết quả. Ngược lại tiếp tục tìm vk+1. + Nếu ∄𝑖 ∈ 𝐷 sao cho vk+1 = i thỏa P (ngõ cụt), ta quay lại bước xác định vk-1. 15 2. Quay Lui: Mã giả: Try(k){ For ([mỗi phương án chọn 𝑖 ∈ 𝐷 ]) If ([Chấp nhận i]){ [Chọn i cho vk]; If ([Thành công]) [Thông báo kq]; else Try(k+1); [Hủy chọn i cho vk]; } } 16 2. Quay lui VD1: Liệt kê các hoán vị của các số tự nhiên 1..N Xây dựng các khái niệm trong giải thuật - Try(k): Tìm thành phần thứ k của hoán vị - Tập giá trị của từng phần tử: D = {1,2,,N} - Chấp nhận được i: Khi i chưa được chọn trước đó. - Thực hiện bước chọn: đánh dấu i đã chọn cho vk. - Thành công: khi chọn được thành phần thứ k = N - Thông báo kết quả: Hiển thị N số của hoán vị - Hủy chọn: đánh dấu i chưa được chọn. 17 2. Quay lui VD2: Liệt kê các cách xếp N quân hậu lên bàn cờ NxN sao cho không có hai quân hậu nào ăn nhau. Xây dựng các khái niệm trong giải thuật - Try(k): Tìm vị trí dòng đặt quân hậu ở cột thứ k - Phương án chọn: i = 1, , N - Chấp nhận được i: Khi i được chọn trước vào ô (i,j) không cùng nằm trên một đường chéo với bất kì ô nào đã chọn trước đó. - Thực hiện bước chọn: đánh dấu i đã chọn và cột, hàng, đường chéo chứa nó đã đặt quân hậu. - Thành công: khi chọn được thành phần thứ k = N - Thông báo kết quả: Hiển thị số dòng theo thứ tự cột tăng dần - Hủy chọn: đánh dấu i chưa được chọn. 18 Nhánh Cận Nhánh Cận là gì? Phương Pháp Một số ví dụ Mã giả 19 Nhánh Cận Nhánh Cận là gì? Nhánh cận trong Quay lui: + là một kỹ thuật đánh giá việc tiếp tục đào sâu có tạo ra cấu hình tốt hơn cấu hình tốt nhất mà ta lưu trữ hay không. + Nhờ có Nhánh cận mà ta có thể đưa ra quyết định quay lui sớm hơn thuật toán backtracking cổ điển. 20 Nhánh Cận Phương Pháp Từ thuật toán backtracking cổ điển, khi xác định điều kiện P (điều kiện xác định cấu hình đề cử), ta sử dụng thêm một hàm đánh giá f(v1, v2,, vk-1) để xác định việc đi tiếp có hy vọng tìm ra lời giải hay không. 21 Nhánh Cận VD: Bài toán người giao hàng - Một người cần phải giao hàng tại N thành phố T1, T2, , Tn - Cij: chi phí đi từ thành phố Ti đến thành phố Tj (i=1,2,,N; j = 1,2,,N) - Yêu cầu: xác định hành trình thỏa mãn + Đi qua tất cả các thành phố, mỗi thành phố qua đúng 1 lần, rồi quay trở lại thành phố xuất phát. + Chi phí nhỏ nhất 22 Nhánh Cận VD: Bài toán người giao hàng Nhánh cận:  Lưu 1 cấu hình BEST_CONFIG  Đặt Cmin=Min{Cij: i,j={1,..,n}}  Giả sử đã đi đoạn đường T1->T2->->Ti với chi phí: Si=C1,x2+Cx2,x3++Cxi-1,xi  Số thành phố chưa đi qua: (n-i+1) thành phố.  Như vậy, để đi tiếp ta sẽ tốn chi phí Cremain > Cmin * (n-i+1)  Hàm cận: f(x1=1,,xi) = Si+(n-i+1)Cmin 23 Nhánh Cận Mã giả Try(k){ For ([mỗi phương án chọn 𝑖 ∈ 𝐷 ]) If ([Chấp nhận i]){ [Chọn i cho vk]; if (Còn hy vọng tìm ra c.hình tốt hơn BEST_CONFIG) { If ([Thành công]) [Thông báo kq]; else Try(k+1); [Hủy chọn i cho vk]; } } } 24 Cám ơn các bạn đã chú ý lắng nghe Trainer: Thien Nguyen