Bài 12.4. Tối ưu thuật toán quay lui bằng nhánh cận

Chào mừng quay trở lại với series về Cấu trúc dữ liệu và Giải thuật của chúng ta! Trong các bài trước, chúng ta đã khám phá sức mạnh của thuật toán quay lui (backtracking) để giải quyết các bài toán tìm kiếm giải pháp, đặc biệt là các bài toán có không gian trạng thái lớn. Quay lui hoạt động bằng cách xây dựng giải pháp từng bước một, và khi một bước dẫn đến trạng thái không hợp lệ, nó "quay lui" để thử một hướng khác.

Tuy nhiên, thuật toán quay lui "thuần túy" đôi khi vẫn phải khám phá một lượng lớn các khả năng, đặc biệt là trong các bài toán tối ưu. Bài toán tối ưu không chỉ đơn giản là tìm một giải pháp hợp lệ, mà là tìm giải pháp tốt nhất (ví dụ: chi phí thấp nhất, giá trị lớn nhất). Với quay lui truyền thống, chúng ta có thể phải chờ nó khám phá tất cả các giải pháp hợp lệ để tìm ra giải pháp tốt nhất, hoặc ít nhất là khám phá rất nhiều nhánh trước khi tìm thấy giải pháp tối ưu. Điều này có thể tốn rất nhiều thời gian và tài nguyên.

Vậy, làm thế nào để chúng ta làm cho quay lui hiệu quả hơn cho các bài toán tối ưu? Câu trả lời nằm ở kỹ thuật Nhánh cận (Branch and Bound).

Nhánh cận (Branch and Bound): Thêm trí tuệ cho quay lui

Nhánh cận là một kỹ thuật tối ưu hóa được xây dựng dựa trên ý tưởng của quay lui. Nó vẫn đi theo các "nhánh" (branches) khác nhau của không gian trạng thái để xây dựng giải pháp. Tuy nhiên, điểm khác biệt cốt lõi là nó sử dụng một "cận" (bound) để ước lượng tiềm năng của mỗi nhánh đang được khám phá.

Nếu tại một điểm nào đó trong quá trình xây dựng giải pháp, chúng ta có thể ước lượng rằng giải pháp tốt nhất có thể đạt được từ nhánh hiện tại không thể tốt hơn giải pháp tốt nhất mà chúng ta đã tìm thấy cho đến nay, thì chúng ta có thể "cắt tỉa" (prune) toàn bộ nhánh đó. Chúng ta biết chắc rằng việc tiếp tục khám phá nhánh này sẽ không dẫn đến một giải pháp tối ưu hơn, nên không cần phí thời gian cho nó nữa.

Hãy hình dung không gian tìm kiếm như một cái cây khổng lồ. Quay lui khám phá cây đó, cắt bỏ những nhánh "chết" (không dẫn đến giải pháp hợp lệ). Nhánh cận còn thông minh hơn: nó còn cắt bỏ những nhánh "không tiềm năng" (không thể dẫn đến giải pháp tối ưu hơn giải pháp tốt nhất đã biết), ngay cả khi chúng có thể dẫn đến giải pháp hợp lệ.

Thành phần cốt lõi của Nhánh cận

Nhánh (Branching): Giống như quay lui, đây là quá trình phân chia bài toán thành các bài toán con nhỏ hơn, tương ứng với việc mở rộng giải pháp từng bước. Mỗi bước lựa chọn tạo ra một nhánh mới để khám phá.
Cận (Bounding): Đây là trái tim của kỹ thuật. Tại mỗi nút trong cây tìm kiếm (tức là một trạng thái trung gian của giải pháp), chúng ta tính một giá trị cận cho giải pháp tốt nhất có thể đạt được từ nút này trở đi.
- Đối với bài toán minimization (tìm giá trị nhỏ nhất), chúng ta tính cận dưới (lower bound): ước lượng chi phí tối thiểu có thể thêm vào để hoàn thành giải pháp.
- Đối với bài toán maximization (tìm giá trị lớn nhất), chúng ta tính cận trên (upper bound): ước lượng giá trị tối đa có thể đạt được từ đây.
Cắt tỉa (Pruning): Tại mỗi bước, sau khi tính cận, chúng ta so sánh nó với giải pháp tốt nhất đã tìm thấy cho đến thời điểm đó (gọi là best_solution hoặc optimal_cost).
- Nếu là bài toán minimization và current_cost + lower_bound >= optimal_cost, chúng ta cắt tỉa.
- Nếu là bài toán maximization và current_value + upper_bound <= optimal_value, chúng ta cắt tỉa.

Việc chọn một hàm cận tốt là rất quan trọng. Hàm cận tốt phải:

Dễ tính toán: Việc tính cận không nên tốn quá nhiều thời gian, nếu không lợi ích từ việc cắt tỉa sẽ bị mất đi.
Chặt chẽ (tight): Cận càng gần với giá trị thực tế càng tốt. Cận chặt chẽ giúp cắt tỉa được nhiều nhánh hơn.

Ví dụ minh họa: Bài toán Gán việc (Assignment Problem)

Hãy xét một bài toán kinh điển mà Nhánh cận có thể giải quyết hiệu quả: Bài toán Gán việc.

Giả sử chúng ta có N công việc và N công nhân. Chi phí để công nhân i thực hiện công việc j được cho trong một ma trận cost[i][j]. Mỗi công nhân chỉ làm một công việc và mỗi công việc chỉ do một công nhân làm. Mục tiêu là tìm cách gán N công việc cho N công nhân sao cho tổng chi phí là nhỏ nhất.

Đây là một bài toán tối ưu (minimization). Một cách giải bằng quay lui thuần túy là thử mọi hoán vị có thể có của việc gán công việc cho công nhân, tính tổng chi phí cho mỗi hoán vị, và giữ lại hoán vị có chi phí nhỏ nhất. Với N công việc, có N! cách gán khác nhau. Điều này trở nên không khả thi ngay cả với N tương đối nhỏ (ví dụ 10! = 3,628,800, 15! rất lớn).

Nhánh cận sẽ giúp chúng ta làm điều này hiệu quả hơn nhiều.

Áp dụng Nhánh cận cho Bài toán Gán việc

Chúng ta sẽ xây dựng giải pháp bằng cách gán từng công việc một.

Trạng thái: Tại mỗi bước đệ quy, trạng thái có thể được định nghĩa bởi:
- Công việc hiện tại đang xem xét (job_index).
- Chi phí hiện tại đã tích lũy (current_cost).
- Tập hợp các công nhân đã được gán (assigned_workers).
Nhánh: Tại bước job_index, chúng ta sẽ thử gán công việc này cho mỗi công nhân i chưa được gán. Mỗi lần thử một công nhân mới là một nhánh mới.
Cận (Lower Bound): Đối với bài toán minimization này, chúng ta cần tính cận dưới. Một cách đơn giản để tính cận dưới tại một trạng thái (khi đã gán job_index-1 công việc) là:
- Chi phí hiện tại đã tích lũy (current_cost)
- Cộng với ước lượng chi phí tối thiểu cho các công việc còn lại (job_index đến N-1).
- Ước lượng chi phí tối thiểu cho các công việc còn lại có thể là tổng của chi phí nhỏ nhất trong mỗi hàng của ma trận chi phí cho các công việc chưa được gán, từ các công nhân chưa được gán. Một cách đơn giản hơn (nhưng có thể không chặt chẽ bằng) là cộng tổng chi phí nhỏ nhất trong mỗi hàng tương ứng với các công việc còn lại, bất kể công nhân nào. Cách tính cận chặt chẽ hơn: Đối với mỗi công việc k từ job_index đến N-1, tìm chi phí nhỏ nhất để gán công việc k cho bất kỳ công nhân nào chưa được gán. Tổng các chi phí nhỏ nhất này là cận dưới cho phần còn lại.
Cắt tỉa: Nếu current_cost + lower_bound_of_remaining_jobs >= min_total_cost_found_so_far, thì chúng ta không cần khám phá nhánh này nữa.

Cài đặt bằng C++

Chúng ta sẽ sử dụng một hàm đệ quy để thực hiện quá trình nhánh và cận.

#include <iostream>
#include <vector>
#include <limits> // For numeric_limits
#include <algorithm> // For min

using namespace std;

const int N = 4; // Ví dụ với N=4 công việc và 4 công nhân
int costMatrix[N][N] = {
    {9, 2, 7, 8},
    {6, 4, 3, 7},
    {5, 8, 1, 8},
    {7, 6, 9, 4}
};

// Biến lưu trữ chi phí tối thiểu tìm được cho đến nay
int minTotalCost = numeric_limits<int>::max();

// Hàm đệ quy thực hiện Branch and Bound
// job_index: chỉ số công việc hiện tại đang xét (từ 0 đến N-1)
// current_cost: chi phí đã tích lũy cho các công việc từ 0 đến job_index-1
// assigned_workers: mảng boolean đánh dấu công nhân nào đã được gán
void solveAssignment(int job_index, int current_cost, bool assigned_workers[]) {
    // ** Bước 1: Cập nhật chi phí tối thiểu nếu đã tìm thấy giải pháp đầy đủ **
    if (job_index == N) {
        // Đã gán hết N công việc, đây là một giải pháp đầy đủ
        minTotalCost = min(minTotalCost, current_cost);
        return; // Quay lui
    }

    // ** Bước 2: Tính cận dưới cho phần còn lại của bài toán **
    // Ước lượng chi phí tối thiểu để hoàn thành các công việc từ job_index đến N-1
    int lower_bound = 0;
    for (int i = job_index; i < N; ++i) { // Duyệt qua các công việc còn lại
        int min_cost_for_this_job = numeric_limits<int>::max();
        // Tìm chi phí nhỏ nhất để gán công việc 'i' cho một công nhân CHƯA được gán
        for (int j = 0; j < N; ++j) {
            if (!assigned_workers[j]) {
                min_cost_for_this_job = min(min_cost_for_this_job, costMatrix[i][j]);
            }
        }
        // Nếu không còn công nhân nào chưa được gán mà công việc này chưa được gán
        // (Điều này không xảy ra trong hàm đệ quy bình thường nếu logic đúng,
        // nhưng thêm kiểm tra để an toàn)
        if (min_cost_for_this_job == numeric_limits<int>::max() && i > job_index) {
             // Điều này có nghĩa là không có cách nào hoàn thành các công việc còn lại
             // Nhánh này không hợp lệ hoặc không thể hoàn thành
             lower_bound = numeric_limits<int>::max(); // Đặt cận rất cao để bị cắt tỉa
             break;
        }
        lower_bound += min_cost_for_this_job;
    }


    // ** Bước 3: Cắt tỉa (Pruning) **
    // Nếu chi phí hiện tại + cận dưới cho phần còn lại >= chi phí tối thiểu đã tìm được
    // thì nhánh này không thể dẫn đến giải pháp tốt hơn. Cắt bỏ nó.
    // Lưu ý: Chúng ta kiểm tra `current_cost + lower_bound >= minTotalCost`
    // nhưng cần cẩn thận với tràn số nếu lower_bound rất lớn.
    // An toàn hơn: kiểm tra `lower_bound >= minTotalCost - current_cost`
    // và cả khi lower_bound là max_int.
    if (lower_bound == numeric_limits<int>::max() || current_cost + lower_bound >= minTotalCost) {
         // cout << "Pruning at job " << job_index << " with cost " << current_cost << " and bound " << lower_bound << endl;
         return; // Cắt tỉa
    }


    // ** Bước 4: Nhánh (Branching) **
    // Thử gán công việc hiện tại (job_index) cho từng công nhân (worker_index) chưa được gán
    for (int worker_index = 0; worker_index < N; ++worker_index) {
        if (!assigned_workers[worker_index]) {
            // Đánh dấu công nhân này đã được gán
            assigned_workers[worker_index] = true;

            // Đệ quy cho công việc tiếp theo
            // Chi phí mới = chi phí hiện tại + chi phí gán công việc job_index cho worker_index
            solveAssignment(job_index + 1, current_cost + costMatrix[job_index][worker_index], assigned_workers);

            // ** Bước 5: Quay lui (Backtracking) **
            // Bỏ đánh dấu công nhân này để thử các cách gán khác cho công việc job_index
            assigned_workers[worker_index] = false;
        }
    }
}

int main() {
    bool assigned_workers[N] = {false}; // Ban đầu chưa có công nhân nào được gán

    // Bắt đầu tìm kiếm từ công việc đầu tiên (index 0) với chi phí ban đầu là 0
    solveAssignment(0, 0, assigned_workers);

    cout << "Chi phi toi thieu cho bai toan gan viec la: " << minTotalCost << endl;

    return 0;
}

Giải thích Code C++

costMatrix và N: Định nghĩa bài toán với ma trận chi phí và kích thước N.
minTotalCost: Biến toàn cục (hoặc có thể truyền bằng tham chiếu) dùng để lưu giữ chi phí tối thiểu tìm được cho đến thời điểm hiện tại. Nó được khởi tạo với giá trị rất lớn (numeric_limits<int>::max()) vì đây là bài toán minimization.
assigned_workers: Mảng boolean để theo dõi công nhân nào đã được sử dụng. assigned_workers[i] = true nghĩa là công nhân i đã được gán cho một công việc nào đó từ 0 đến job_index-1.
Hàm đệ quy solveAssignment(job_index, current_cost, assigned_workers):
- Base Case: Nếu job_index == N, nghĩa là chúng ta đã thành công gán hết N công việc. current_cost lúc này là tổng chi phí của một giải pháp đầy đủ. Chúng ta cập nhật minTotalCost nếu current_cost nhỏ hơn giá trị tốt nhất đã biết.
- Tính Cận Dưới (lower_bound): Đây là phần cốt lõi của Branch and Bound. Chúng ta duyệt qua các công việc còn lại (từ job_index đến N-1). Đối với mỗi công việc còn lại, chúng ta tìm chi phí nhỏ nhất trong hàng tương ứng trong ma trận chi phí chỉ từ những công nhân chưa được gán. Tổng của các chi phí nhỏ nhất này là cận dưới cho chi phí thêm vào để hoàn thành giải pháp từ trạng thái hiện tại.
- Cắt tỉa (Pruning): Chúng ta kiểm tra điều kiện current_cost + lower_bound >= minTotalCost. Nếu đúng, nhánh hiện tại không thể dẫn đến một giải pháp tốt hơn minTotalCost đã tìm được, nên chúng ta return ngay lập tức, cắt bỏ toàn bộ nhánh này.
- Nhánh (Branching): Duyệt qua tất cả các công nhân worker_index chưa được gán. Với mỗi công nhân như vậy:
  - Đánh dấu công nhân đó là đã được gán (assigned_workers[worker_index] = true).
  - Gọi đệ quy cho công việc tiếp theo (job_index + 1), cộng thêm chi phí gán công việc hiện tại cho công nhân này (costMatrix[job_index][worker_index]) vào current_cost.
- Quay lui (Backtracking): Sau khi gọi đệ quy, chúng ta phải hoàn tác việc gán công nhân hiện tại (assigned_workers[worker_index] = false). Điều này cho phép chúng ta thử gán công việc job_index cho các công nhân khác trong vòng lặp for, hoặc quay lại bước trước đó (job_index - 1) để thử các cách gán công việc đó khác.
Hàm main: Khởi tạo mảng assigned_workers và gọi hàm đệ quy bắt đầu từ công việc 0 với chi phí 0. Cuối cùng, in ra minTotalCost.

Tại sao nó hiệu quả hơn?

So với quay lui thuần túy (duyệt N! cách gán), kỹ thuật Nhánh cận giúp chúng ta loại bỏ sớm rất nhiều nhánh không tiềm năng. Khi minTotalCost được cập nhật với một giá trị nhỏ hơn, điều kiện cắt tỉa trở nên "chặt chẽ" hơn, giúp cắt bỏ được nhiều nhánh hơn nữa ở các bước đệ quy sâu hơn.

Mức độ hiệu quả của Nhánh cận phụ thuộc rất nhiều vào chất lượng của hàm tính cận. Cận càng chặt (gần với chi phí thực tế hơn), khả năng cắt tỉa càng cao, thuật toán càng nhanh. Tuy nhiên, việc tính cận cũng không được quá phức tạp, nếu không thời gian tính cận sẽ làm chậm thuật toán. Hàm cận chúng ta sử dụng ở trên là một cận dưới đơn giản và hiệu quả cho bài toán Gán việc.

Lựa chọn Chiến lược Tìm kiếm

Trong ví dụ trên, chúng ta đã sử dụng chiến lược tìm kiếm theo chiều sâu (Depth-First Search - DFS), giống như quay lui thông thường. Tuy nhiên, Branch and Bound cũng có thể được kết hợp với các chiến lược tìm kiếm khác:

Tìm kiếm theo chiều rộng (BFS): Khám phá tất cả các nút ở một mức trước khi xuống mức tiếp theo.
Tìm kiếm Tốt nhất Đầu tiên (Best-First Search): Sử dụng một hàng đợi ưu tiên (priority queue) để luôn khám phá nút có cận (ước lượng) tốt nhất trước. Đối với minimization, nút có cận dưới nhỏ nhất sẽ được ưu tiên. Chiến lược này thường hứa hẹn tìm thấy giải pháp tối ưu sớm hơn, cho phép optimal_cost được cập nhật nhanh chóng và giúp việc cắt tỉa hiệu quả hơn. Tuy nhiên, nó có thể đòi hỏi nhiều bộ nhớ hơn BFS.

Việc lựa chọn chiến lược nào phụ thuộc vào đặc thù của bài toán và không gian tìm kiếm. Với DFS (như trong ví dụ), cấu trúc đệ quy tự nhiên của quay lui được giữ lại, làm cho việc triển khai đơn giản.

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

Nhánh cận là một ứng cử viên sáng giá khi bạn đối mặt với các bài toán tối ưu hóa trên không gian trạng thái lớn mà:

Có thể mô hình hóa bằng cây tìm kiếm (như trong quay lui).
Có thể dễ dàng tính toán một cận hợp lý cho giải pháp tối ưu từ một trạng thái trung gian bất kỳ.
Bài toán có kích thước quá lớn đối với tìm kiếm vét cạn (brute force) hoặc quay lui thuần túy.

Các ứng dụng phổ biến của Nhánh cận bao gồm:

Bài toán Người du lịch (Traveling Salesperson Problem - TSP)
Bài toán Cái túi (Knapsack Problem - đặc biệt là 0/1 Knapsack)
Lập lịch trình (Job Scheduling)
Quy hoạch nguyên (Integer Programming)
... và nhiều bài toán tối ưu tổ hợp khác.

Bài tập ví dụ:

[DSA-QuayLui-NhanhCan].Phân tích số.

Cho mảng A[] gồm N số nguyên dương phân biệt và số X. Nhiệm vụ của bạn là tìm phép tổ hợp các số trong mảng A[] có tổng bằng X. Các số trong mảng A[] có thể được sử dụng nhiều lần. Mỗi tổ hợp các số của mảng A[] được in ra theo thứ tự không giảm các số. Ví dụ với A[] = , X = 8 ta có các tổ hợp các số như sau: [2, 2, 2, 2], [2, 2, 4], [2, 6], [4, 4], [8].

Input Format

Dòng đầu tiên đưa vào số lượng bộ test T. Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm hai phần: phần thứ hất là hai số N và X; dòng tiếp theo đưa vào N số của mmảng A[]; các số được viết cách nhau một vài khoảng trống. T, N, X, A[i] thỏa mãn ràng buộc: 1≤T ≤10; 1≤X, A[i]≤100. N ≤ 20.

Constraints

Output Format

Đưa ra kết quả mỗi test theo từng dòng. Mỗi đường tổ hợp được bao bởi cặp ký tự [, ]. Đưa ra -1 nếu không có tổ hợp nào thỏa mãn yêu cầu bài toán.

Ví dụ:

Dữ liệu vào

1
4 8
2 4 6 8

Dữ liệu ra

[2 2 2 2][2 2 4][2 6][4 4][8]

Chào bạn, đây là hướng dẫn giải bài "Phân tích số" sử dụng kỹ thuật đệ quy quay lui (backtracking) kết hợp với nhánh cận.

Sắp xếp mảng A: Đầu tiên, hãy sắp xếp mảng A theo thứ tự tăng dần. Điều này giúp đảm bảo các tổ hợp được tạo ra theo thứ tự không giảm và tránh lặp lại các tổ hợp giống nhau (ví dụ: [2, 4] và [4, 2] sẽ chỉ được tạo ra dưới dạng [2, 4] nếu ta tuân thủ thứ tự các phần tử trong mảng A).
Hàm đệ quy: Xây dựng một hàm đệ quy có nhiệm vụ tìm các tổ hợp. Hàm này cần các tham số sau:
- index: Chỉ số bắt đầu xét trong mảng A đã sắp xếp.
- current_sum: Tổng hiện tại của các số đã chọn trong tổ hợp đang xây dựng.
- current_combination: Một vector hoặc danh sách lưu trữ các số đã chọn cho tổ hợp hiện tại.
Điều kiện dừng (Base Cases):
- Nếu current_sum == X: Tìm được một tổ hợp hợp lệ. Lưu trữ current_combination vào danh sách kết quả chung. Dừng nhánh đệ quy này.
- Nếu current_sum > X: Tổng đã vượt quá X, nhánh này không thể tạo ra lời giải. Dừng nhánh đệ quy này.
Bước đệ quy:
- Duyệt qua các phần tử của mảng A bắt đầu từ chỉ số index. Gọi chỉ số hiện tại là i.
- Với mỗi phần tử A[i]:
  - Kiểm tra nếu current_sum + A[i] <= X. Đây là điều kiện nhánh cận đơn giản nhất để tránh đi vào những nhánh chắc chắn vượt quá X.
  - Nếu điều kiện trên đúng:
    - Thêm A[i] vào cuối current_combination.
    - Gọi đệ quy tiếp theo: solve(i, current_sum + A[i], current_combination). Quan trọng: truyền lại chỉ số i (chứ không phải i+1) vào lời gọi đệ quy tiếp theo. Điều này cho phép sử dụng lại chính phần tử A[i] nhiều lần.
    - Quay lui (Backtrack): Sau khi lời gọi đệ quy solve(i, ...) hoàn thành (tức là đã tìm hết các tổ hợp có thể tạo ra khi thêm A[i]), loại bỏ phần tử A[i] khỏi cuối current_combination để thử các khả năng khác.
Khởi tạo và chạy:
- Tạo một danh sách (ví dụ: vector<vector<int>>) để lưu trữ tất cả các tổ hợp hợp lệ tìm được.
- Gọi hàm đệ quy lần đầu với các giá trị ban đầu: solve(0, 0, empty_vector).
Xử lý kết quả:
- Sau khi hàm đệ quy chính kết thúc, kiểm tra danh sách kết quả.
- Nếu danh sách rỗng, in ra -1.
- Nếu danh sách không rỗng, duyệt qua từng tổ hợp trong danh sách, in chúng ra theo định dạng [phần_tử_1 phần_tử_2 ...] như yêu cầu.

Lưu ý: Do kích thước N và X nhỏ, phương pháp đệ quy quay lui này là phù hợp. Việc sắp xếp mảng A ban đầu và việc truyền chỉ số i trong lời gọi đệ quy là chìa khóa để tạo ra các tổ hợp duy nhất và có thứ tự.

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

Comments

There are no comments at the moment.