THUẬT TOÁN ỨNG DỤNG ĐỆ QUY QUAY LUI 1 Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn NộI dung  Đệ quy quay lui  Tổng quan đệ quy quay lui  Bài toán liệt kê xâu nhị phân  Bài toán liệt kê nghiệm nguyên dương phương trình tuyến tính  Bài toán liệt kê TSP  Bài toán liệt kê hành trình taxi  Bài toán liệt kê CBUS  Bài toán liệt kê BCA  Bài toán liệt kê CVRP  Thuật toán nhánh và cận  Tổng quan nhánh và cận  Bài toán tối ưu TSP  Bài toán tối ưu hành trình taxi  Bài toán tối ưu CBUS  Bài toán tối ưu BCA  Bài toán tối ưu CVRP 2 Đệ quy quay lui  Phương pháp dùng để liệt kê các cấu hình tổ hợp cũng như giải bài toán tối ưu tổ hợp  Liệt kê: liệt kê tất cả các bộ x = (x1,x2,…, xN) trong đó xi  Ai - tập rời rạc, đồng thời (x1,x2,..., xN) thỏa mãn các ràng buộc C cho trước  Tối ưu tổ hợp: trong số các bộ (phương án) x = (x1,x2,…, xN) trong đó xi  Ai - tập rời rạc, đồng thời (x1,x2,..., xN) thỏa mãn các ràng buộc C cho trước, cần tìm phương án có f(x) → min(max)  Thử lần lượt từng giá trị cho mỗi biến  Chiến lược chọn biến, ví dụ x1, x2, x3,…, xN  Chiến lược chọn giá trị cho biến, ví dụ từ nhỏ đến lớn hoặc ngược lại 3 Đệ quy quay lui () x1 = v1 . . . . (v1) x2 = u1 x1 = vk x1 = v2 x2 = uq . . . . (v1,uq) x3 = w1 x3 = wh . . . . (v1,uq, wh) . . . . 4 . . . . Đệ quy quay lui  Tại mỗi thời điểm, ta có phương án bộ phận (x1 = v1, x2 = v2, …, xk-1 = vk-1) → cần thử duyệt tiếp các khả năng cho xk ? try(k){// thử giá trị cho xk forall v  Ak do{ if(check(v,k)) then{// kiểm tra ràng buộc C của bài toán xk = v; [cập nhật các cấu trúc dữ liệu liên quan] if(k = N) then solution(); else try(k+1); [khôi phục trạng thái các cấu trúc dữ liệu khi quay lui] } } } . . . . 5 Liệt kê xâu nhị phân độ dài N #include