Khóa học CTDL và GT

Bài 12.3. Kỹ thuật nhánh cận cơ bản

Chào mừng các bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Hôm nay, chúng ta sẽ cùng khám phá một kỹ thuật mạnh mẽ và linh hoạt trong việc giải quyết các bài toán tối ưu tổ hợp: Kỹ thuật Nhánh cận (Branch and Bound - B&B).

Trong thế giới thực, chúng ta thường đối mặt với những vấn đề mà mục tiêu là tìm ra giải pháp tốt nhất (tối thiểu hoặc tối đa hóa một giá trị nào đó) từ một tập hợp lớn các khả năng. Ví dụ: tìm đường đi ngắn nhất, phân công công việc hiệu quả nhất, xếp lịch tối ưu, hay chọn vật phẩm vào ba lô để được giá trị cao nhất.

Với những bài toán này, việc thử tất cả các khả năng (thử vét cạn - exhaustive search) thường là không khả thi vì không gian tìm kiếm quá lớn. Kỹ thuật nhánh cận ra đời để giải quyết vấn đề này bằng cách kết hợp việc tìm kiếm có hệ thống (nhánh) với khả năng loại bỏ sớm những khả năng không hứa hẹn (cận).

Nhánh cận là gì? Sức mạnh từ sự kết hợp

Kỹ thuật nhánh cận là một phương pháp giải thuật tổng quát được sử dụng rộng rãi để tìm ra lời giải tối ưu cho các bài toán tối ưu tổ hợp và rời rạc (như quy hoạch nguyên - integer programming). Về cơ bản, nó là sự cải tiến của kỹ thuật quay lui (backtracking) hoặc tìm kiếm theo chiều sâu/chiều rộng bằng cách thêm vào một "bộ lọc" thông minh: cận.

Hai thành phần cốt lõi của Branch and Bound là:

1. Nhánh (Branching): Quá trình chia bài toán ban đầu thành các bài toán con nhỏ hơn. Tưởng tượng bạn đang đi trên một cái cây (cây không gian trạng thái), mỗi lần rẽ là bạn đang tạo ra một nhánh mới, dẫn đến một nhóm các lời giải tiềm năng. Quá trình này tạo ra một cây tìm kiếm mà các nút lá của nó đại diện cho các lời giải khả thi của bài toán gốc.
2. Cận (Bounding): Quá trình tính toán một giá trị "cận" (upper bound hoặc lower bound) cho giá trị mục tiêu của lời giải tối ưu trong phạm vi bài toán con hiện tại.
   • Đối với bài toán tối thiểu hóa (minimization), chúng ta thường tính cận dưới (lower bound). Cận dưới cho biết giá trị nhỏ nhất có thể đạt được trong nhánh hiện tại, ngay cả trong trường hợp tốt nhất. Lời giải tối ưu thực tế trong nhánh đó sẽ luôn lớn hơn hoặc bằng cận dưới này.
   • Đối với bài toán tối đa hóa (maximization), chúng ta thường tính cận trên (upper bound). Cận trên cho biết giá trị lớn nhất có thể đạt được trong nhánh hiện tại, ngay cả trong trường hợp tốt nhất. Lời giải tối ưu thực tế trong nhánh đó sẽ luôn nhỏ hơn hoặc bằng cận trên này.

Sức mạnh của nhánh cận nằm ở việc sử dụng cận để thực hiện cắt tỉa (pruning). Khi chúng ta đang khám phá một nhánh và tính toán cận của nó, nếu cận này cho thấy rằng không thể nào tìm được một lời giải tốt hơn lời giải tối ưu đã tìm thấy cho đến nay (gọi là lời giải đương nhiệm - incumbent), thì chúng ta có thể loại bỏ hoàn toàn nhánh đó mà không cần khám phá sâu hơn. Điều này giúp giảm đáng kể không gian tìm kiếm.

Cơ chế hoạt động cơ bản

Hãy hình dung quá trình tìm kiếm bằng Branch and Bound:

1. Bắt đầu với bài toán gốc (gốc cây tìm kiếm).
2. Khởi tạo một giá trị cho lời giải tối ưu tốt nhất tìm được cho đến nay. Đối với tối thiểu hóa, khởi tạo bằng vô cùng; đối với tối đa hóa, khởi tạo bằng âm vô cùng.
3. Sử dụng kỹ thuật nhánh để tạo ra các bài toán con (các nút con của nút hiện tại).
4. Đối với mỗi bài toán con được tạo ra (mỗi nút con), tính toán giá trị cận của nó.
5. Sử dụng kỹ thuật cận để cắt tỉa:
   • Đối với tối thiểu hóa: Nếu cận dưới của bài toán con hiện tại lớn hơn hoặc bằng giá trị lời giải tốt nhất đã tìm được, thì loại bỏ bài toán con này (không cần khám phá nhánh này nữa).
   • Đối với tối đa hóa: Nếu cận trên của bài toán con hiện tại nhỏ hơn hoặc bằng giá trị lời giải tốt nhất đã tìm được, thì loại bỏ bài toán con này.
6. Chọn một bài toán con chưa bị loại bỏ để tiếp tục khám phá (sử dụng chiến lược tìm kiếm, ví dụ: theo chiều sâu - DFS, theo chiều rộng - BFS, hoặc best-first search dựa trên cận).
7. Nếu một bài toán con là một lời giải khả thi cho bài toán gốc (nút lá của cây tìm kiếm), kiểm tra xem giá trị của lời giải này có tốt hơn lời giải tốt nhất đã tìm được hay không. Nếu có, cập nhật lời giải tốt nhất.
8. Lặp lại quá trình 3-7 cho đến khi không còn bài toán con nào để khám phá.

Lời giải tốt nhất tìm được khi quá trình kết thúc chính là lời giải tối ưu toàn cục.

Mấu chốt: Kỹ thuật B&B hiệu quả khi và chỉ khi cận mà bạn tính toán đủ "chặt" (gần với giá trị tối ưu thực tế trong nhánh) để có thể cắt tỉa được nhiều nhánh. Việc lựa chọn hàm cận và chiến lược nhánh là rất quan trọng và phụ thuộc vào bài toán cụ thể.

Các thành phần quan trọng

Để triển khai B&B, chúng ta cần xác định rõ:

• Biểu diễn trạng thái bài toán: Làm thế nào để mô tả một bài toán con hoặc một lời giải tiềm năng?
• Chiến lược nhánh: Làm thế nào để chia một bài toán thành các bài toán con? (Ví dụ: chọn biến tiếp theo để quyết định giá trị, chọn vật phẩm tiếp theo để đưa vào/không đưa vào, chọn thành phố tiếp theo trong hành trình...)
• Hàm cận: Làm thế nào để tính toán cận (dưới cho min, trên cho max) cho một bài toán con? Đây là thành phần quan trọng nhất và thường là khó nhất để thiết kế hiệu quả. Cận phải là hợp lệ (không bao giờ loại bỏ lời giải tối ưu thực tế) và chặt (gần với giá trị tối ưu thực tế).
• Chiến lược lựa chọn nút: Chọn bài toán con nào để mở rộng tiếp theo? (DFS, BFS, Best-first dựa trên cận - thường chọn nút có cận hứa hẹn nhất: cận dưới nhỏ nhất cho min, cận trên lớn nhất cho max). Chiến lược này ảnh hưởng đến thứ tự khám phá và hiệu quả thực tế. Với bài toán cơ bản, tìm kiếm theo chiều sâu (DFS) thường được sử dụng vì đơn giản.
• Kiểm tra lời giải khả thi: Khi nào thì một trạng thái của bài toán con là một lời giải hợp lệ cho bài toán gốc? (Ví dụ: đã phân công hết công việc, đã chọn xong vật phẩm cho ba lô trong giới hạn sức chứa...)
• Hàm mục tiêu: Tính giá trị của một lời giải khả thi.

Ví dụ minh họa 1: Bài toán Phân công đơn giản (Simplified Assignment Problem)

Hãy xem xét một bài toán phân công đơn giản: Chúng ta có N công việc và N người. Ma trận cost[i][j] cho biết chi phí khi người i làm công việc j. Mỗi người chỉ làm một công việc, mỗi công việc chỉ được một người làm. Mục tiêu là tìm cách phân công sao cho tổng chi phí là nhỏ nhất.

Đây là một bài toán tối thiểu hóa. Chúng ta sẽ sử dụng Branch and Bound với tìm kiếm theo chiều sâu (DFS).

Biểu diễn trạng thái: Một trạng thái có thể được mô tả bằng số lượng công việc đã được phân công và cách phân công đó (một mảng hoặc vector lưu trữ assignment[i] = j nghĩa là người i làm công việc j).

Chiến lược nhánh: Ở mỗi bước, chúng ta chọn công việc tiếp theo chưa được phân công và thử gán nó cho mỗi người chưa bận.

Hàm cận (Cận dưới): Đối với một trạng thái mà k công việc đã được phân công với tổng chi phí là current_cost, chúng ta cần tính cận dưới cho chi phí tổng cộng (bao gồm cả k công việc đã gán và N-k công việc còn lại). Một cận dưới đơn giản và hợp lệ là: Lower Bound = current_cost + Tổng chi phí tối thiểu cho các công việc còn lại Trong đó, "Tổng chi phí tối thiểu cho các công việc còn lại" được tính bằng cách cộng chi phí nhỏ nhất trong mỗi hàng (công việc) chưa được gán (loại bỏ những người đã bận).

Cắt tỉa: Nếu Lower Bound >= best_total_cost (chi phí tốt nhất tìm được cho đến nay), cắt tỉa nhánh này.

Ví dụ nhỏ: 3 công việc, 3 người. Ma trận chi phí:

cost = [
    [9, 2, 7],  # Chi phí người 0 làm việc 0, 1, 2
    [6, 4, 3],  # Chi phí người 1 làm việc 0, 1, 2
    [5, 8, 1]   # Chi phí người 2 làm việc 0, 1, 2
]

Mục tiêu: tìm assignment[0], assignment[1], assignment[2] (mỗi người 0, 1, 2 làm một công việc duy nhất từ {0, 1, 2}) để cost[0][assignment[0]] + cost[1][assignment[1]] + cost[2][assignment[2]] nhỏ nhất.

Cài đặt C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

const int INF = std::numeric_limits<int>::max();

// Ma trận chi phí
std::vector<std::vector<int>> cost_matrix = {
    {9, 2, 7},
    {6, 4, 3},
    {5, 8, 1}
};
int N = cost_matrix.size();

// Mảng lưu trữ công việc được phân công cho mỗi người.
// assignment[i] = j nghĩa là người i làm công việc j.
// Khởi tạo -1 nghĩa là chưa được phân công.
std::vector<int> assignment(N, -1);

// Mảng đánh dấu công việc đã có người làm hay chưa
std::vector<bool> job_assigned(N, false);

// Biến lưu trữ chi phí tốt nhất tìm được cho đến nay
int best_total_cost = INF;

// Hàm tính cận dưới cho trạng thái hiện tại
int calculate_lower_bound(int person_idx, int current_cost) {
    int lower_bound = current_cost;

    // Cộng thêm chi phí tối thiểu cho các công việc còn lại
    for (int i = person_idx; i < N; ++i) {
        int min_job_cost = INF;
        for (int j = 0; j < N; ++j) {
            // Chỉ xem xét các công việc chưa được gán
            if (!job_assigned[j]) {
                 min_job_cost = std::min(min_job_cost, cost_matrix[i][j]);
            }
        }
        // Nếu vẫn còn công việc chưa được gán cho người i và min_job_cost là INF,
        // nghĩa là không thể gán, bài toán con này không khả thi.
        // Tuy nhiên, trong bài toán phân công vuông N x N, luôn có cách gán
        // miễn là chúng ta tuân thủ quy tắc, nên min_job_cost sẽ không là INF
        // nếu việc gán hợp lệ.
        if (min_job_cost != INF) {
             lower_bound += min_job_cost;
        } else {
            // Nếu không tìm được công việc nào chưa được gán cho người i,
            // điều này có thể xảy ra nếu tất cả công việc đã bị gán bởi người khác
            // trong các nhánh trước đó (không phải cách triển khai tốt nhất cho bài toán này).
            // Một cận dưới đơn giản hơn (nhưng yếu hơn) là chỉ dựa vào chi phí hiện tại.
            // Tuy nhiên, cách tính dựa trên min_job_cost cho các *hàng* chưa được xử lý là phổ biến.
            // Để đơn giản, chúng ta giả định min_job_cost luôn tìm được nếu có người/việc còn lại.
            // Cận dưới tốt hơn cho bài toán phân công là tổng chi phí nhỏ nhất trong mỗi hàng/cột còn lại.
            // Cách triển khai này đơn giản hóa cận dưới.
        }
    }
    return lower_bound;
}


// Hàm đệ quy giải bài toán bằng Branch and Bound
// person_idx: đang xét phân công cho người thứ person_idx
// current_cost: tổng chi phí hiện tại của các công việc đã phân công cho người 0...person_idx-1
void solve(int person_idx, int current_cost) {
    // Trường hợp cơ bản: đã phân công xong cho tất cả mọi người
    if (person_idx == N) {
        // Đã tìm được một lời giải khả thi (một cách phân công đầy đủ)
        best_total_cost = std::min(best_total_cost, current_cost);
        return;
    }

    // Tính cận dưới cho trạng thái hiện tại (trước khi phân công cho người person_idx)
    // Cận này dựa trên current_cost (đã gán cho person_idx-1 người)
    // và ước lượng chi phí thấp nhất cho person_idx đến N-1 người còn lại.
    // Cận dưới chính xác hơn nên tính *sau* khi gán cho người person_idx
    // để phản ánh chi phí của assignment[person_idx].
    // Tuy nhiên, để minh họa cận dưới cơ bản, chúng ta có thể tính
    // cận cho trạng thái *trước* khi gán cho person_idx, nhưng nó sẽ yếu hơn.
    // Một cách tính cận mạnh hơn là tính sau khi gán cho person_idx và ước lượng
    // chi phí còn lại cho person_idx+1 đến N-1.
    // Hãy điều chỉnh cận dưới để tính sau khi đã gán cho person_idx.

    // Vòng lặp nhánh: thử gán công việc j cho người person_idx
    for (int job_idx = 0; job_idx < N; ++job_idx) {
        // Kiểm tra xem công việc job_idx đã được gán cho ai chưa
        if (!job_assigned[job_idx]) {
            // Bước 1: Nhánh - Gán công việc job_idx cho người person_idx
            assignment[person_idx] = job_idx;
            job_assigned[job_idx] = true;
            int new_cost = current_cost + cost_matrix[person_idx][job_idx];

            // Bước 2: Tính cận dưới cho bài toán con mới
            // Bài toán con: phân công cho người person_idx + 1 trở đi
            // Cận dưới = chi phí hiện tại + chi phí tối thiểu cho các công việc còn lại
            // Tính chi phí tối thiểu cho các công việc còn lại (từ person_idx + 1 đến N-1)
            int remaining_min_cost = 0;
            for (int i = person_idx + 1; i < N; ++i) { // Cho những người còn lại
                int min_job_cost_for_person_i = INF;
                for (int j = 0; j < N; ++j) { // Tìm công việc chưa gán với chi phí nhỏ nhất cho người i
                    if (!job_assigned[j]) {
                         min_job_cost_for_person_i = std::min(min_job_cost_for_person_i, cost_matrix[i][j]);
                    }
                }
                // Nếu min_job_cost_for_person_i vẫn là INF, có lỗi logic trong cách gán
                // hoặc bài toán không có lời giải. Trong bài N x N đầy đủ, điều này không xảy ra
                // nếu việc gán tuân thủ quy tắc.
                 if (min_job_cost_for_person_i != INF) {
                    remaining_min_cost += min_job_cost_for_person_i;
                 }
            }
            int lower_bound = new_cost + remaining_min_cost;


            // Bước 3: Cắt tỉa - So sánh cận dưới với lời giải tốt nhất đã biết
            if (lower_bound < best_total_cost) {
                // Nếu nhánh này có tiềm năng tốt hơn, tiếp tục đệ quy
                solve(person_idx + 1, new_cost);
            }

            // Quay lui: Hủy gán công việc job_idx khỏi người person_idx
            assignment[person_idx] = -1;
            job_assigned[job_idx] = false;
        }
    }
}

int main() {
    std::cout << "Bat dau tim kiem loi giai toi uu cho bai toan phan cong..." << std::endl;

    // Bat dau tu nguoi dau tien (person 0) voi chi phi ban dau la 0
    solve(0, 0);

    if (best_total_cost == INF) {
        std::cout << "Khong tim thay loi giai hop le." << std::endl;
    } else {
        std::cout << "Chi phi phan cong toi thieu la: " << best_total_cost << std::endl;
        // Luu y: De in duoc phan cong cu the, can luu lai assignment khi best_total_cost duoc cap nhat.
        // Phan code tren chi tim chi phi.
    }

    return 0;
}

Giải thích code:

1. cost_matrix: Lưu chi phí cost[i][j] khi người i làm việc j.
2. assignment: Mảng assignment[i] = j để theo dõi người i được gán công việc j. Dùng -1 cho chưa gán.
3. job_assigned: Mảng boolean để theo dõi công việc nào đã có người làm.
4. best_total_cost: Biến toàn cục (hoặc truyền qua tham chiếu) để lưu chi phí nhỏ nhất tìm được cho đến nay. Khởi tạo bằng giá trị rất lớn (INF).
5. solve(person_idx, current_cost): Hàm đệ quy chính.
   • person_idx: Chỉ số người chúng ta đang cố gắng phân công công việc ở bước hiện tại.
   • current_cost: Tổng chi phí của các công việc đã phân công cho những người từ 0 đến person_idx - 1.
   • Base Case: Nếu person_idx == N, nghĩa là đã phân công xong cho tất cả N người. Đây là một lời giải khả thi. Cập nhật best_total_cost nếu current_cost hiện tại nhỏ hơn.
   • Branching: Duyệt qua tất cả các công việc (job_idx từ 0 đến N-1). Nếu công việc job_idx chưa được gán (!job_assigned[job_idx]), thử gán nó cho người person_idx.
   • Cập nhật assignment[person_idx], đánh dấu job_assigned[job_idx] = true, và tính new_cost.
   • Bounding: Tính lower_bound. Cận dưới ở đây được tính bằng new_cost (chi phí đã gán đến người person_idx) cộng với ước lượng chi phí nhỏ nhất có thể cho những người còn lại (person_idx + 1 đến N-1). Việc ước lượng này được thực hiện bằng cách cộng chi phí nhỏ nhất từ mỗi hàng (người) còn lại, chỉ xem xét các công việc chưa bị gán.
   • Pruning: So sánh lower_bound với best_total_cost. Nếu lower_bound < best_total_cost, nhánh này có thể chứa lời giải tốt hơn, nên tiếp tục đệ quy bằng cách gọi solve(person_idx + 1, new_cost) để phân công cho người tiếp theo. Ngược lại (lower_bound >= best_total_cost), nhánh này chắc chắn không thể cho ra chi phí tốt hơn best_total_cost, nên chúng ta cắt tỉa (không gọi đệ quy).
   • Backtracking: Sau khi đệ quy hoặc cắt tỉa, chúng ta phải hoàn tác việc gán (assignment[person_idx] = -1, job_assigned[job_idx] = false) để thử gán công việc khác cho người person_idx hoặc để các nhánh khác có thể sử dụng công việc job_idx.

Code này minh họa cách Branch and Bound sử dụng cận dưới để cắt tỉa trong một bài toán tối thiểu hóa. Hàm cận dưới ở đây là một ví dụ đơn giản; trong thực tế, việc thiết kế hàm cận hiệu quả và chặt chẽ là rất quan trọng để thuật toán hoạt động tốt.

Ví dụ minh họa 2: Bài toán Cái ba lô 0/1 (0/1 Knapsack Problem) - Tối đa hóa giá trị

Bài toán Cái ba lô 0/1: Cho một tập hợp các vật phẩm, mỗi vật có trọng lượng và giá trị. Ba lô có sức chứa tối đa. Chọn một tập hợp con các vật phẩm để đưa vào ba lô sao cho tổng trọng lượng không vượt quá sức chứa, và tổng giá trị là lớn nhất. Mỗi vật phẩm chỉ có thể chọn hoặc không chọn (0 hoặc 1).

Đây là bài toán tối đa hóa. Chúng ta sẽ sử dụng Branch and Bound, thường kết hợp với tìm kiếm theo chiều sâu.

Biểu diễn trạng thái: Một trạng thái có thể mô tả bằng số lượng vật phẩm đã xem xét, tổng trọng lượng hiện tại của các vật phẩm đã chọn, và tổng giá trị hiện tại.

Chiến lược nhánh: Ở mỗi bước, xem xét vật phẩm tiếp theo. Có hai nhánh: chọn vật phẩm đó (nếu còn chỗ trong ba lô) hoặc không chọn vật phẩm đó.

Hàm cận (Cận trên): Đối với một trạng thái mà chúng ta đã xem xét i vật phẩm, có trọng lượng current_weight và giá trị current_value, chúng ta cần tính cận trên cho tổng giá trị tối đa có thể đạt được nếu tiếp tục xem xét các vật phẩm còn lại (i+1 đến N). Một cận trên phổ biến và hiệu quả cho bài toán knapsack là sử dụng giải pháp của Bài toán Cái ba lô phân số (Fractional Knapsack Problem) cho các vật phẩm còn lại.

• Bài toán Cái ba lô phân số: Giống 0/1 Knapsack nhưng có thể lấy một phần của vật phẩm. Nó có thể giải dễ dàng bằng chiến lược tham lam: sắp xếp các vật phẩm còn lại theo tỷ lệ giá trị/trọng lượng giảm dần, và lấy các vật phẩm theo thứ tự này cho đến khi đầy ba lô (hoặc hết vật phẩm), lấy vật phẩm cuối cùng chỉ một phần nếu cần.
• Cận trên: Cận trên của một trạng thái sẽ là current_value cộng với giá trị tối đa có thể thu được từ các vật phẩm còn lại bằng cách giải bài toán Knapsack phân số với sức chứa còn lại (capacity - current_weight). Cận này là hợp lệ vì việc chỉ được lấy toàn bộ vật phẩm (0/1) không bao giờ cho giá trị tốt hơn việc được lấy phân số.

Cắt tỉa: Nếu Upper Bound <= best_total_value (giá trị tốt nhất tìm được cho đến nay), cắt tỉa nhánh này.

Cài đặt C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

struct Item {
    int weight;
    int value;
    double ratio; // value/weight ratio
};

// Sắp xếp vật phẩm theo tỷ lệ value/weight giảm dần
bool compareItems(const Item& a, const Item& b) {
    return a.ratio > b.ratio;
}

// Dữ liệu vật phẩm
std::vector<Item> items = {
    {10, 60, 0}, // Item 0
    {20, 100, 0},// Item 1
    {30, 120, 0} // Item 2
};
int N = items.size();
int capacity = 50; // Sức chứa ba lô

// Biến lưu trữ giá trị tốt nhất tìm được cho đến nay
int max_total_value = 0;

// Hàm tính cận trên sử dụng Fractional Knapsack cho các vật phẩm còn lại
// item_idx: chỉ số vật phẩm đầu tiên còn lại để xem xét
// current_weight: trọng lượng hiện tại trong ba lô
// current_value: giá trị hiện tại trong ba lô
double calculate_upper_bound(int item_idx, int current_weight, int current_value) {
    double upper_bound = current_value;
    int remaining_capacity = capacity - current_weight;

    // Sử dụng chiến lược tham lam cho Fractional Knapsack trên các vật phẩm còn lại
    for (int i = item_idx; i < N; ++i) {
        if (remaining_capacity <= 0) {
            break; // Ba lô đầy
        }

        // Nếu vật phẩm i có thể được lấy toàn bộ
        if (items[i].weight <= remaining_capacity) {
            upper_bound += items[i].value;
            remaining_capacity -= items[i].weight;
        } else {
            // Chỉ lấy một phần của vật phẩm i để lấp đầy chỗ trống còn lại
            upper_bound += (double)items[i].value / items[i].weight * remaining_capacity;
            remaining_capacity = 0;
            break;
        }
    }
    return upper_bound;
}


// Hàm đệ quy giải bài toán Knapsack 0/1 bằng Branch and Bound
// item_idx: đang xét vật phẩm thứ item_idx
// current_weight: trọng lượng hiện tại trong ba lô
// current_value: giá trị hiện tại trong ba lô
void solve(int item_idx, int current_weight, int current_value) {
    // Trường hợp cơ bản: đã xem xét hết vật phẩm
    if (item_idx == N) {
        // Đã xem xét tất cả vật phẩm, current_value là một lời giải khả thi (nếu current_weight <= capacity)
        // Nhưng cấu trúc hàm nhánh này đảm bảo current_weight luôn <= capacity khi chọn vật phẩm
        max_total_value = std::max(max_total_value, current_value);
        return;
    }

    // Tính cận trên cho nhánh hiện tại
    double upper_bound = calculate_upper_bound(item_idx, current_weight, current_value);

    // Cắt tỉa: Nếu cận trên <= giá trị tốt nhất đã biết, không cần khám phá nhánh này
    if (upper_bound <= max_total_value) {
        return;
    }

    // Bước 1: Nhánh - Xét trường hợp CHỌN vật phẩm item_idx
    // Chỉ chọn nếu còn chỗ trong ba lô
    if (current_weight + items[item_idx].weight <= capacity) {
        solve(item_idx + 1, current_weight + items[item_idx].weight, current_value + items[item_idx].value);
    }

    // Bước 2: Nhánh - Xét trường hợp KHÔNG CHỌN vật phẩm item_idx
    // Luôn có thể không chọn
    solve(item_idx + 1, current_weight, current_value);
}

int main() {
    std::cout << "Bat dau tim kiem gia tri toi da cho bai toan cai ba lo 0/1..." << std::endl;

    // Tính tỷ lệ value/weight và sắp xếp vật phẩm
    for (int i = 0; i < N; ++i) {
        items[i].ratio = (double)items[i].value / items[i].weight;
    }
    std::sort(items.begin(), items.end(), compareItems); // Sắp xếp để cận trên chặt hơn

    // Bat dau tu vat pham dau tien (item 0) voi trong luong va gia tri ban dau la 0
    solve(0, 0, 0);

    std::cout << "Gia tri toi da co the dat duoc trong ba lo: " << max_total_value << std::endl;

    return 0;
}

Giải thích code:

1. Item struct: Lưu trữ thông tin về vật phẩm, bao gồm tỷ lệ value/weight cần cho việc tính cận.
2. compareItems: Hàm so sánh để sắp xếp vật phẩm theo tỷ lệ value/weight giảm dần. Việc sắp xếp này giúp hàm cận sử dụng Fractional Knapsack cho ra cận trên chặt hơn.
3. items: Vector lưu trữ các vật phẩm.
4. capacity: Sức chứa tối đa của ba lô.
5. max_total_value: Biến toàn cục lưu trữ giá trị lớn nhất tìm được cho đến nay. Khởi tạo bằng 0 (hoặc giá trị rất nhỏ).
6. calculate_upper_bound: Hàm tính cận trên. Nó nhận vào trạng thái hiện tại (item_idx, current_weight, current_value) và tính giá trị tối đa có thể đạt được bằng cách thêm các vật phẩm còn lại (item_idx đến N-1) theo cách của Fractional Knapsack vào sức chứa còn lại (capacity - current_weight).
7. solve(item_idx, current_weight, current_value): Hàm đệ quy chính.
   • item_idx: Chỉ số vật phẩm đang được xem xét.
   • current_weight: Trọng lượng hiện tại trong ba lô.
   • current_value: Giá trị hiện tại trong ba lô.
   • Base Case: Nếu item_idx == N, nghĩa là đã xem xét tất cả vật phẩm. current_value hiện tại là giá trị của một tập hợp vật phẩm hợp lệ (vì nhánh "chọn" đã kiểm tra sức chứa). Cập nhật max_total_value nếu current_value lớn hơn.
   • Bounding & Pruning: Trước khi nhánh, tính upper_bound cho trạng thái hiện tại. Nếu upper_bound <= max_total_value, nhánh này không thể chứa lời giải tốt hơn, nên cắt tỉa (dừng đệ quy tại đây).
   • Branching: Có hai nhánh con:
     • Chọn vật phẩm item_idx: Nếu trọng lượng hiện tại cộng với trọng lượng vật phẩm item_idx không vượt quá sức chứa (current_weight + items[item_idx].weight <= capacity), gọi đệ quy với item_idx + 1, trọng lượng tăng thêm, và giá trị tăng thêm.
     • Không chọn vật phẩm item_idx: Luôn có thể không chọn một vật phẩm. Gọi đệ quy với item_idx + 1, giữ nguyên trọng lượng và giá trị hiện tại.
   • Lưu ý: Trong triển khai DFS này, nhánh "chọn" được xét trước nhánh "không chọn". Trình tự này có thể ảnh hưởng một chút đến khi nào lời giải tốt nhất được tìm thấy, nhưng không ảnh hưởng đến tính đúng đắn của thuật toán.

Code này cho thấy cách B&B sử dụng cận trên để cắt tỉa trong bài toán tối đa hóa. Việc sử dụng Fractional Knapsack làm cận trên là một kỹ thuật chuẩn và khá hiệu quả cho bài toán 0/1 Knapsack.

So sánh với Backtracking/Tìm kiếm vét cạn

Sự khác biệt mấu chốt giữa Branch and Bound và các kỹ thuật tìm kiếm đơn giản như Backtracking hay thử vét cạn là ở khả năng cắt tỉa dựa trên cận.

• Vét cạn: Thử mọi khả năng, tính giá trị và ghi nhận lời giải tốt nhất. Không có cơ chế loại bỏ sớm các nhánh vô vọng.
• Backtracking: Tìm kiếm theo chiều sâu, xây dựng lời giải từng bước. Nếu một phần lời giải vi phạm ràng buộc nào đó, quay lui. Một số dạng backtracking có thể ghi nhận lời giải tốt nhất tìm được và sử dụng nó để cắt tỉa nếu một phần lời giải hiện tại đã tệ hơn lời giải tốt nhất (ví dụ: trong TSP, nếu độ dài đường đi hiện tại đã vượt quá độ dài đường đi tốt nhất tìm được). Tuy nhiên, cơ chế cắt tỉa này thường dựa trên giá trị thực tế của phần lời giải đã xây dựng, chứ không phải dựa trên tiềm năng tối ưu ước lượng của toàn bộ nhánh con như B&B.
• Branch and Bound: Kết hợp tìm kiếm có cấu trúc (nhánh) với việc tính toán cận (dưới cho min, trên cho max) cho tổng giá trị của cả nhánh. Sử dụng cận này để loại bỏ sớm các nhánh mà cận cho thấy không thể chứa lời giải tốt hơn lời giải đương nhiệm. Sức mạnh của B&B nằm ở việc hàm cận có thể ước lượng tiềm năng của một nhánh trước khi xây dựng xong một lời giải khả thi trong nhánh đó.

Khi nào sử dụng Nhánh cận?

Nhánh cận là lựa chọn tốt cho các bài toán tối ưu tổ hợp khi:

• Không gian tìm kiếm quá lớn để vét cạn.
• Có thể xây dựng một cấu trúc cây tìm kiếm (nhánh) cho bài toán.
• Quan trọng nhất, có thể tìm được một hàm cận hợp lệ và đủ "chặt" (hiệu quả trong việc cắt tỉa) cho các bài toán con.

Bài tập ví dụ:

[DSA-ThuatToanSinh].Sinh tổ hợp.

Cho hai số nguyên dương N và K. Nhiệm vụ của bạn là hãy liệt kê tất cả các tập con K phần tử của 1, 2, .., N. Ví dụ với N=5, K=3 ta có 10 tập con của 1, 2, 3, 4, 5 như sau: , ,,,,,,{2, 3, 5},,.

Input Format

Dòng đầu tiên đưa vào số lượng test T. Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một cặp số tự nhiên N, K được viết trên một dòng. T, n thỏa mãn ràng buộc: 1≤T≤100; 1≤k ≤ n≤15.

Constraints

.

Output Format

Đưa ra kết quả mỗi test theo từng dòng.

Ví dụ:

Dữ liệu vào

2
4 3
5 3

Dữ liệu ra

123 124 134 234
123 124 125 134 135 145 234 235 245 345

Okay, đây là hướng dẫn giải bài toán sinh tổ hợp bằng C++ theo phương pháp "sinh kế tiếp":

1. Cấu trúc dữ liệu: Sử dụng một mảng (hoặc vector) có kích thước K để lưu trữ một tổ hợp hiện tại, ví dụ int a[K].

2. Tổ hợp đầu tiên: Khởi tạo mảng a với tổ hợp đầu tiên theo thứ tự từ điển: 1, 2, ..., K.

3. Vòng lặp sinh: Sử dụng một vòng lặp (ví dụ do-while hoặc while) để lặp cho đến khi không thể sinh được tổ hợp kế tiếp nữa.

4. In tổ hợp hiện tại: Bên trong vòng lặp, in ra các phần tử của mảng a nối liền nhau (không cách), sau đó in một dấu cách để phân tách các tổ hợp.

5. Tìm phần tử có thể tăng: Để sinh tổ hợp kế tiếp, tìm chỉ số i lớn nhất (duyệt từ K-1 về 0) sao cho phần tử a[i] chưa đạt giá trị lớn nhất có thể tại vị trí i. Giá trị lớn nhất có thể của a[i] là N - (K - 1 - i). Tức là tìm i lớn nhất sao cho a[i] < N - (K - 1 - i).

6. Điều kiện dừng: Nếu không tìm thấy chỉ số i nào như vậy (tức là i < 0), điều này có nghĩa là tổ hợp hiện tại là tổ hợp cuối cùng (N-K+1, ..., N), và vòng lặp dừng lại.

7. Sinh tổ hợp kế tiếp: Nếu tìm thấy i:

   • Tăng giá trị a[i] lên 1: a[i]++.
   • Thiết lập các phần tử sau a[i] (từ a[i+1] đến a[K-1]) về giá trị nhỏ nhất có thể theo thứ tự tăng dần: a[j] = a[i] + (j - i) cho j từ i+1 đến K-1.

8. Xử lý nhiều test case: Bao bọc toàn bộ logic sinh tổ hợp trong một vòng lặp chạy T lần. In một dòng trắng (hoặc xuống dòng) sau mỗi test case nếu cần (ở đây output format chỉ yêu cầu xuống dòng sau mỗi test case).

Làm thêm nhiều bài tập miễn phí tại đây