Quay lui + vét cạn + lựa chọn tối ưu
Kết hợp đệ quy
I. Ý nghĩa:
- Trong nhiều trường hợp, nghiệm của bài toán là một dãy các phần tử xác định mà không tuân theo quy tắc toán học cố định. Để tìm nghiệm, cần tìm kiếm từng bước, xác định dần từng phần tử của nghiệm. Mỗi phần tử được kiểm tra xem khả năng nào là "đúng, sai" để tiếp tục lựa chọn khả năng tiếp theo.
- Nếu một khả năng không dẫn đến kết quả chấp nhận, loại bỏ khả năng đó và chuyển sang lựa chọn khác chưa được chọn. Mỗi khi chọn khả năng cho một phần tử, trạng thái của bài toán thường thay đổi. Khi quay lại lựa chọn khác, phải quay lại trạng thái trước khi chọn.
- Khi có một khả năng chấp nhận được, và phần tử chưa phải là cuối cùng, tiếp tục tìm phần tử tiếp theo.
- Nếu yêu cầu bài toán là tìm một nghiệm duy nhất, khi chọn được khả năng cho phần tử, kiểm tra xem nó có phải phần tử cuối cùng không. Nếu đúng, hiển thị nghiệm và thoát hoàn toàn khỏi thuật toán đệ quy.
- Để tối ưu hóa việc thử nghiệm, nếu có thể nhận biết điều kiện loại trừ khả năng không chấp nhận nhanh chóng thì thử nghiệm sẽ hiệu quả hơn.
- Để tìm nghiệm tối ưu, khi có một nghiệm, so sánh với nghiệm tối ưu hiện có. Nếu nghiệm mới tốt hơn, cập nhật nghiệm tối ưu. Sau khi duyệt hết các nghiệm, nghiệm tối ưu của bài toán sẽ được xác định.
Tổng kết thuật toán “duyệt trên cơ sở tìm kiếm và quay lui” - Thuật toán BackTracking:
- Duyệt toàn bộ nghiệm bằng cách tìm kiếm tiến dần, đồng thời biết quay lui khi không thể tiến.
- Có thể đặt các “mắt lọc” để tăng tốc độ tìm kiếm.
- Có thể so sánh nghiệm để chọn nghiệm tối ưu.
- Tuỳ yêu cầu bài toán, tìm một hoặc nhiều nghiệm.
Do thuật toán BackTracking xây dựng trên cơ sở tìm kiếm dần, kết quả hình thành từ kết quả trước nên có thể dùng đệ quy với các dạng sau:
II. Ba dạng đệ quy thường gặp trong thuật toán BackTracking
Dạng 1: Tìm mọi nghiệm
Procedure Tim(k: Integer);
Begin
// Vòng lặp thử các khả năng tại bước k
Begin
// Thử chọn đề cử cho bước k
// Nếu đề cử chấp nhận được thì
Begin
// Ghi nhận giá trị đề cử;
// Lưu trạng thái bài toán sau đề cử;
// Nếu chưa phải bước cuối thì Tim(K+1)
Else
// Bước cuối
// Hiện Nghiệm;
// Trả lại trạng thái bài toán trước đề cử;
End;
End;
End;
Cách khác:
Procedure Tim(k: Integer);
Begin
// Nếu bước k là sau bước cuối cùng thì Hiện nghiệm;
// Vòng lặp thử khả năng tại bước k
Begin
// Thử chọn đề cử cho bước k
// Nếu đề cử thỏa mãn bài toán thì
Begin
// Ghi nhận giá trị đề cử;
// Lưu trạng thái bài toán sau đề cử;
// Tim(k+1);
// Trả lại trạng thái bài toán trước đề cử;
End;
End;
End;
Ví dụ: Bài toán con mã đi tuần trên bàn cờ nxn, tìm cách đi qua tất cả ô, mỗi ô đi đúng một lần.
Dạng 2: Tìm một nghiệm
Procedure Tim(k: Integer);
Begin
// Vòng lặp thử mỗi khả năng của bước k
Begin
// Thử chọn đề cử
// Nếu đề cử chấp nhận được thì
Begin
// Ghi nhận giá trị đề cử;
// Lưu trạng thái bài toán sau đề cử;
// Nếu là bước cuối cùng thì
Begin
// Hiện Nghiệm;
// Thoát;
End;
// Trả lại trạng thái trước đề cử;
End;
End;
End;
Cách khác:
Procedure Tim(k: Integer);
Begin
// Nếu là bước sau bước cuối thì
Begin
// Hiện Nghiệm;
// Thoát;
End
Else:
// Vòng lặp thử khả năng tại bước k
Begin
// Thử chọn đề cử
// Nếu đề cử thỏa mãn thì
Begin
// Ghi nhận giá trị đề cử;
// Lưu trạng thái bài toán sau đề cử;
// Nếu chưa phải bước cuối thì Tim(K+1);
// Trả lại trạng thái trước đề cử;
End;
End;
End;
Dạng 3: Tìm nghiệm tối ưu
Có 3 cách:
Cách 1:
Procedure Tim(k: Integer);
Begin
// Nếu bước k là sau bước cuối cùng thì
Begin
// Nếu nghiệm mới tốt hơn nghiệm tối ưu trước thì chọn nghiệm mới làm tối ưu;
End;
// Vòng lặp thử khả năng tại bước k (kết hợp với nghiệm tối ưu để thu hẹp lựa chọn)
Begin
// Thử chọn đề cử cho bước k
// Nếu đề cử thỏa mãn thì
Begin
// Ghi nhận giá trị đề cử;
// Lưu trạng thái bài toán sau đề cử;
// Tim(k+1);
// Trả lại trạng thái bài toán trước đề cử;
End;
End;
End;
Bình luận