Thuật Toán Quay Lui & Nhánh Cận

1. Cầu nối kiến trúc: Recursion $\to$ Divide & Conquer $\to$ state-space search $\to$ Dynamic Programming

Để có cái nhìn toàn cảnh về các phương pháp giải thuật lớn trong Lập trình thi đấu:

• Divide & Conquer: $\text{Bài toán lớn} \longrightarrow \text{Các bài toán con riêng biệt}$.
• Backtracking / State-Space Search: $\text{Trạng thái hiện tại} \longrightarrow \text{Các nhánh quyết định thử nghiệm (Choices)}$.
• Dynamic Programming: $\text{Nhiều đường đi khác nhau} \longrightarrow \text{Cùng một State Identity (Overlapping States)} \implies \text{Memoization / Bảng DP}$.

2. Bản chất trạng thái (state definition & state identity)

Khái niệm state (trạng thái) & state identity:

Định nghĩa: State (Trạng thái) là tập thông tin tối thiểu cần thiết để xác định chính xác các lựa chọn tiếp theo và kết quả có thể đạt được từ trạng thái hiện tại. * Không phải mọi biến xuất hiện trong hàm đệ quy đều là thành phần của State Identity; chỉ những thông tin có thể làm thay đổi các lựa chọn hoặc kết quả của phần còn lại mới cần thiết.

• Trong cài đặt DFS / Quay lui: State bao gồm cả dữ liệu cấu hình đang xây dựng và các đại lượng tích lũy (current_value, current_cost).
• Khi chuyển sang Quy Hoạch Động (DP): Ta chắt lọc những biến thực sự tạo nên "State Identity" (ví dụ: dp[index][remaining_weight] hoặc dp[city][mask]), còn giá trị mục tiêu trở thành giá trị lưu trong bảng DP thay vì là tham số đệ quy.

Quy luật cốt lõi: Không phải cứ có State là có thể chuyển sang DP. Để chuyển sang DP, bài toán bắt buộc phải có State Identity gọn gàng + Hiện tượng trùng lặp trạng thái (Overlapping Subproblems) + Cấu trúc con tối ưu (Optimal Substructure).

3. Khung phương pháp luận: Design-time framework vs runtime pattern

1. Khung thiết kế thuật toán (design-time framework):

1. Define State: Xác định các biến trạng thái tối thiểu cần thiết để mô tả bài toán.
2. Generate Candidates: Xác định danh sách các lựa chọn khả dĩ tại mỗi bước đi.
3. Define Feasibility: Thiết lập điều kiện ràng buộc hợp lệ (Feasibility Pruning).
4. Define Bound: Thiết lập hàm cận dưới $LB$ hoặc cận trên $UB$ nếu là bài toán tối ưu (Branch & Bound).
5. Define Transition & Restoration: Thiết lập quy tắc chuyển trạng thái (Choose), gọi đệ quy (Explore) và hoàn tác (Unchoose).

2. Khung thực thi mã nguồn (runtime pattern):

void search(State state) {
    if (isGoal(state)) {
        processSolution(state);
        return;
    }
    for (const auto &candidate : getCandidates(state)) {
        if (!isFeasible(state, candidate)) continue; // Feasibility Pruning

        if (boundSaysImpossible(state, candidate)) continue; // Optimality Pruning (B&B)

        choose(state, candidate);  // 1. Chuyển sang State_new
        search(state);             // 2. Đi sâu vào nhánh con (Explore)
        unchoose(state, candidate);// 3. Hoàn tác về State_before (Restoration)
    }
}

4. Khung tư duy mental model: Hai sơ đồ cốt lõi của lesson 12

Quy trình 1: Luồng ra quyết định quay lui thuần túy (backtracking)

Quy trình 2: Luồng ra quyết định nhánh cận (Branch & Bound)

5. Bất biến trung tâm: State restoration invariant

Quy luật cốt lõi: Choose-Explore-Unchoose là một pattern cài đặt phổ biến. Bản chất kỹ thuật sâu sắc là Bất biến Khôi phục Trạng Thái (State Restoration Invariant):

$\text{State}_{\text{before}} \xrightarrow{\text{Choose}} \text{State}_{\text{new}} \xrightarrow{\text{Explore}} \text{Subtree} \xrightarrow{\text{Unchoose}} \text{State}_{\text{before}}$ Sau khi khám phá xong một nhánh con và hàm con return, trạng thái phải được trả về nguyên vẹn 100% như trước khi bước vào nhánh đó, đảm bảo nhánh kế tiếp bắt đầu từ cùng một trạng thái cha.

6. Phân biệt cắt tỉa ràng buộc (feasibility) vs cắt tỉa tối ưu (Branch & Bound)

• BACKTRACKING: "Xây dựng nghiệm từng bước + quay lui khi cần (có thể không cần pruning như sinh nhị phân)"
• FEASIBILITY PRUNING: "Cắt những trạng thái chắc chắn không thể dẫn tới nghiệm hợp lệ"
• BRANCH AND BOUND: "Framework tìm kiếm tối ưu trên không gian trạng thái, kết hợp hàm Cận (Bound) để cắt tỉa nhánh không thể tốt hơn best hiện tại"

Lưu ý mở rộng: Trong chuyên đề này, ta triển khai Branch & Bound trên nền DFS / Backtracking để nắm vững nguyên lý. Về tổng quát, Branch & Bound là một framework tìm kiếm tối ưu có thể triển khai bằng Best-First Search với hàng đợi ưu tiên priority_queue hoặc BFS.

Định nghĩa chuẩn xác: $OPT(\text{state})$ vs $best$ hiện tại:

• $OPT(\text{state})$: Giá trị tốt nhất thực sự có thể đạt được khi hoàn thành nghiệm từ trạng thái hiện tại.
• $best$ (hoặc $best\_so\_far$ / $incumbent$): Nghiệm tốt nhất đã tìm thấy trên toàn bộ các nhánh đã khám phá tính đến thời điểm hiện tại (chưa chắc là nghiệm tối ưu toàn cục cho đến khi duyệt xong).

Nguyên tắc thiết lập hàm bound chuẩn xác:

1. Với bài toán Cực Tiểu Hóa (Minimization - ví dụ TSP, Đổi tiền ít xu nhất, Job Assignment): * Ta duy trì hàm Cận Dưới $LB(\text{state}) \le OPT(\text{state})$. * Điều kiện cắt tỉa: Nếu $LB(\text{state}) \ge \text{best}$, thì $OPT(\text{state}) \ge LB(\text{state}) \ge \text{best} \implies$ Cắt tỉa ngay! * Ví dụ: $best = 100$. Nếu tại một nhánh ta tính được $LB = 105 \implies$ Cắt tỉa ngay vì $OPT \ge 105 > 100$. Nếu $LB = 95 \implies$ Không được cắt tỉa vì $OPT$ có thể là $95, 98$ tốt hơn $100$.

2. Với bài toán Cực Đại Hóa (Maximization - ví dụ Cái túi Knapsack $0/1$): * Ta duy trì hàm Cận Trên $UB(\text{state}) \ge OPT(\text{state})$. * Điều kiện cắt tỉa: Nếu $UB(\text{state}) \le \text{best}$, thì $OPT(\text{state}) \le UB(\text{state}) \le \text{best} \implies$ Cắt tỉa ngay!

Mối liên hệ giữa Heuristic Ordering & Branch and Bound: Heuristic ordering giúp tìm ra nghiệm tốt sớm hơn $\implies best$ được cải thiện nhanh hơn $\implies$ Hàm Bound cắt tỉa được nhiều nhánh hơn $\implies$ Thuật toán B&B chạy nhanh hơn vượt trội!

7. Phân loại 4 cấp độ kỹ thuật trong tìm kiếm toàn vẹn

8. Cầu nối sâu sang DP: Từ cây tìm kiếm (search tree) đến đồ thị trạng thái (state DAG)

• Duyệt cây thuần túy (Tree Search): Phải tính toán lại trạng thái E nhiều lần ở các nhánh con khác nhau.
• Quan điểm Đồ thị (State DAG View): E chỉ là một đỉnh duy nhất trong không gian trạng thái.
• Quy Hoạch Động (Dynamic Programming / Memoization): Trong những bài toán mà State Identity có số lượng trạng thái đa thức theo kích thước input, Memoization/DP có thể giảm một cây tìm kiếm hàm mũ xuống $\text{Số trạng thái} \times \text{Chi phí chuyển trạng thái}$; ví dụ Knapsack đạt $\mathcal{O}(N \cdot W)$ khi $W$ là tham số giới hạn. Với các bài như TSP, Bitmask DP đạt $\mathcal{O}(N^2 \cdot 2^N)$ nhanh hơn rất nhiều so với vét cạn $N!$.

9. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Quên hoàn tác trạng thái (Missing Unchoose Step): * Sau khi gọi đệ quy backtrack(i + 1), quên viết visited[val] = false; hoặc cur_sum -= val; $\implies$ Trạng thái của nhánh trước bị rò rỉ sang nhánh sau, làm mất toàn bộ các nghiệm tiếp theo.

2. Bẫy cắt tỉa break trong Subset Sum có số âm: * Lệnh if (current_sum + A[i] > S) break; chỉ an toàn khi mọi phần tử $A_i > 0$ và mảng đã sort tăng dần. Tuyệt đối không áp dụng nguyên trạng cho mảng có phần tử âm!

3. Đánh dấu sai mảng các họ đường chéo trong bài $N$-Queens: * Với chỉ số 1-based: * Họ đường chéo xuôi \: $row - col \in [-(N-1), N-1] \implies row - col + N \in [1, 2N-1]$. * Họ đường chéo ngược /: $row + col \in [2, 2N]$. * Khai báo diag1 và diag2 tối thiểu kích thước $2N + 1$.

4. Giả thiết về mệnh giá xu trong Coin Change: * Mọi mệnh giá xu $C_i \ge 1$ để đảm bảo độ sâu tối đa bị chặn trên bởi $\lfloor S / C_{\min} \rfloor$.

10. Mẫu cài đặt chuẩn thi đấu (competitive templates)

# include <bits/stdc++.h>
using namespace std;

using ll = long long;

// 1. Sinh Hoán Vị 1..N chuẩn State Restoration Invariant
int n = 3;
vector<int> cur;

vector<bool> visited;

void genPermutations(int step) {
    if (step > n) {

        for (int i = 0; i < n; ++i) cout << cur[i] << (i + 1 == n ? "" : " ");
        cout << "\n";
        return;
    }
    for (int val = 1; val <= n; ++val) {
        if (!visited[val]) {
            visited[val] = true;       // 1. CHOOSE
            cur.push_back(val);
            genPermutations(step + 1); // 2. EXPLORE
            cur.pop_back();            // 3. UNCHOOSE (Khôi phục)
            visited[val] = false;
        }
    }
}

// 2. Bài Toán N-Queens (Đếm số cách đặt N quân hậu)
int n_queens = 4;
ll queen_ways = 0;
vector<bool> col_used, diag1_used, diag2_used;

void solveNQueens(int row) {
    if (row > n_queens) {

        queen_ways++;
        return;
    }
    for (int col = 1; col <= n_queens; ++col) {
        if (!col_used[col] && !diag1_used[row - col + n_queens] && !diag2_used[row + col]) {
            col_used[col] = diag1_used[row - col + n_queens] = diag2_used[row + col] = true; // CHOOSE
            solveNQueens(row + 1); // EXPLORE
            col_used[col] = diag1_used[row - col + n_queens] = diag2_used[row + col] = false; // UNCHOOSE
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    visited.assign(n + 1, false);
    genPermutations(1);

    col_used.assign(n_queens + 1, false);
    diag1_used.assign(2 * n_queens + 1, false);
    diag2_used.assign(2 * n_queens + 1, false);
    solveNQueens(1);
    cout << "So cach dat " << n_queens << " quan hau: " << queen_ways << "\n";
    return 0;
}