Cấu trúc dữ liệu - Phần 5 (tt)

Tài liệu tham khảo bài giảng môn Cấu trúc dữ liệu - Phần 5 Giải thuật quay lui ( tiếp theo )
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu - Phần 5 (tt) Phương pháp nhánh cận (brand and bound) GVGD: Trương Phước Hải Phương pháp nhánh và cận  Kỹ thuật quay lui duyệt tất cả khả năng theo mô hình cây phân cấp để tìm ra cấu hình 2 Phương pháp nhánh và cận  Sử dụng quay lui để tìm cấu hình tối ưu Đánh giá tất cả cấu hình để tìm ra cấu hình tối ưu: điều  này dẫn đến sự bùng nổ tổ hợp Nếu việc chọn thành phần xi không dẫn đến cấu hình tối ưu  sẽ gây lãng phí tài nguyên để tìm các thành phần tiếp theo xi+1, xi+2, ... Cần tận dụng thông tin đã biết để sớm loại bỏ cấu hình  chắc chắn không thể tối ưu 3 Phương pháp nhánh và cận  Kỹ thuật nhánh và cận (gọi tắt nhánh cận) là một dạng cải tiến của kỹ thuật quay lui áp dụng cho bài toán tối ưu Đánh giá lại giá trị tối ưu cục bộ (cận) của các nhánh sau  mỗi lần quay lui Sử dụng cận để loại bỏ những nhánh dư thừa của cây tìm  kiếm nhằm giảm chi phí: tỉa nhánh Đánh giá cận là vấn đề khó khăn nhất trong việc áp dụng  phương pháp nhánh cận 4 Phương pháp nhánh và cận  Ý tưởng Khởi tạo một cấu hình BEST cho bài toán: khởi tạo cận  Tính chi phí của các cấu hình ngay trong quá trình xây  dựng Nếu tốt hơn BEST: cập nhật cấu hình tối ưu và tiếp tục  Ngược lại quay lui để tìm phương án khác  5 Phương pháp nhánh và cận  Mô hình tổng quát của kỹ thuật nhánh cận được cải tiến từ mô hình đệ quy như sau Try(i) For (j tập khả năng của X[i]) If (chấp nhận j) Then Chọn khả năng j cho X[i] If (X[i] là cuối cấu hình) Then Else If (vẫn còn tốt hơn BEST) Then Try(i + 1) Cuối If Cuối If Cuối for Cuối Try 6 Phương pháp nhánh và cận  Khi đó giải thuật nhánh cận được thực hiện theo các bước sau NhanhVaCan() BEST = +; //Nếu biết X’ là phương án tối ưu hiện tại //BEST = f(X’); Try(0); If (BEST < +) Then Else Cuối If Cuối NhanhVaCan 7 Phương pháp nhánh và cận  Bài toán người du lịch (TSP - Travelling Salesman Problem) Một bản đồ gồm N thành phố được đánh số từ 0 đến N-1  Một du khách xuất phát tại thành phố 1 và muốn tham  quan tất cả thành phố, mỗi nơi đến đúng 1 lần rồi trở về thành phố xuất phát Biết rằng giữa 2 thành phố có thể lưu thông trực tiếp sẽ tốn  một chi phí nhất định Yêu cầu xác định hành trình du lịch với chi phí nhỏ nhất  8 Phương pháp nhánh và cận  Tổ chức dữ liệu Sử dụng mảng 2 chiều gồm N dòng, N cột để biểu diễn chi  phí đi lại giữa các thành phố: ma trận chi phí C[i][j] = v: cho biết việc đi từ thành phố i đến trực tiếp  thành phố j tốn chi phí v C[i][j] = +: cho biết không có đường đi trực tiếp từ  thành phố i đến thành phố j Sử dụng mảng 1 chiều X[0], X[1], …, X[N] để lưu trữ một  nghiệm bài toán (thứ tự thành phố thăm trong hành trình) 9 Phương pháp nhánh và cận  Ví dụ đồ thị biểu diễn và ma trận chi phí tương ứng như sau 0 1 2 3 2 0 2 0 0 3 2 1 1 3 1 3 0 1 2 1 1 2 2 1 0 4 2 4 3 3 1 2 4 0 10 Phương pháp nhánh và cận  Nhận xét x0 = 0 là thành phố xuất phát  Hành trình cần tìm có dạng  (x0 = 0, x1, x2, .., xN-1, xN = 0) Một hành trình (x1, x2, .., xN-1) là một hoán vị của các  thành phố {1, 2, …, N-1} 11 Phương pháp nhánh và cận  Cây tìm kiếm TSP theo kỹ thuật quay lui 0 3 1 2 1 2 3 1 4 1 2 2 4 2 3 1 3 1 2 4 4 2 2 1 1 3 2 3 1 2 1 2 2 1 1 3 3 0 0 0 0 0 0 9 11 6 11 6 9 12 Phương pháp nhánh và cận  Duyệt quay lui Chọn x1 là một trong các TP có thể đến trực tiếp từ x0  Chọn x2 là một trong các TP chưa tham quan và có thể đến  trực tiếp từ x3 …  Chọn xi là một trong các TP chưa tham quan và có thể đến  trực tiếp từ xi-1 (1 ≤ i ≤ N-1) 1 ...