- Lý thuyết
Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.
Tư tưởng
Dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.
Các bước trong việc liệt kê cấu hình dạng X[1…n]:
- Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
- Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]…tiếp tục như vậy cho tới bước:
- …
- ….
- Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
- Thông báo cấu hình tìm được.
Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu
Kĩ thuật nhánh cận
Vì thuật toán đệ quy/quay lui thường có độ phức tạp là cấp số mũ nên đa số bài toán sẽ không thể xử lí trong thời gian yêu cầu.
Tuy nhiên khi xét các trường hợp, ta có thể áp dụng kĩ thuật bằng cách loại bỏ sớm các nhánh không thể khả thi từ sớm để giảm bớt rất nhiều độ phức tạp của Code.
VD:
Ta có 10 công việc với thời gian cần làm và lương nhận được khác nhau. Mỗi công việc chỉ làm 1 lần.
Cho một khoảng thời gian có là T, ví dụ khi ta đã tìm được 1 khả năng:
- Trong 10 tiếng, chọn 4 công việc và kiếm được 600 nghìn
Thì khi xét 1 nhánh khác với 3 công việc, và ta nhận thấy nếu
- Thời gian còn lại / (Thời gian dành cho công việc tốt nhất) * Lương công việc cao nhất
Tức là cho dù ta làm công việc tốt nhất cho khoảng thời gian còn lại mà vẫn ít tiền hơn khả năng trên, thì không việc gì cần xét tiếp nhánh đó nữa.
|| Khi bạn đang tắc đường và cố chui vào 1 ngõ rẽ cho nhanh, nhưng bạn nhẩm cho dù đi đường vòng này nhanh nhất vẫn chậm hơn chờ tắc bình thường, thì tốt nhất nên quay đầu lại ngay chứ đừng chui vào ngõ tiếp.
Bài 1: P135SUMG – SUM5 G – Xâu đặc biệt
https://www.spoj.com/PTIT/problems/P135SUMG/
Ý tưởng:
- Tại các vị trí ‘_’ , ta thử tất cả chữ cái có thể thay vào, sau đó tiếp tục di chuyển đến các từ ngữ tiếp theo
- Cần lưu trữ lại số lượng các phụ âm, nguyên âm, số lượng chữ L hiện tại để dừng lại nếu không thỏa mãn yêu cầu
Độ phức tạp Code:
- Do đi qua từng vị trí (n) và tại mỗi vị trí có nhiều nhất 2 nhánh mới tạo ra, nên ~ 2^n
Bài 2: BCQUEEN – N – Queen
https://www.spoj.com/PTIT/problems/BCQUEEN/
Ý tưởng:
- Tại các vị trí bất kì, ta thử đặt quân hậu tại đó, sau đó tiếp tục thử
- Khi đi đến vị trí cuối cùng (cuối phải) thì dừng lại và đếm cấu hình đã thỏa mãn thêm 1
Độ phức tạp:
- Tại mỗi hàng cần lặp qua tất cả các cột rồi tại mỗi cột tiếp tục thử
- Độ phức tạp: n^2
Bài 3: P167PROC – ROUND 7C – Ký tự lặp trong 2 xâu liên tiếp
https://www.spoj.com/PTIT/problems/P167PROC/
Ý tưởng:
- Do N khá nhỏ, ta sinh hoán vị các cách sắp xếp từ
- Tại mỗi cấu hình hoán vị, ta thử lặp qua dãy sắp xếp hiện tại và đếm số lần lặp, do input đảm bảo các từ được sắp xếp sẵn nên có thể dùng tìm kiếm nhị phân để tối ưu
Độ phức tạp:
- Gọi độ dài string là L, số lượng xâu là n
- Sinh toàn bộ hoán vị : L !
- Tại mỗi hoán vị, lặp qua dãy 1 lần : n
- Tại mỗi phần tử, lặp qua tất cả vị trí và tìm kiểm nhị phân : L log(L)
- Độ phức tạp tổng : L ! n L log(L)