Giải thuật vét càn (brute force) là một trong những phương pháp cơ bản nhất trong thiết kế giải thuật — không dựa trên tối ưu hóa hay suy luận sâu, mà dựa vào việc kiểm tra từng khả năng có thể xảy ra cho đến khi tìm được nghiệm hoặc xác định không tồn tại nghiệm.

Khái niệm và đặc điểm

Giải thuật vét càn còn được gọi là phương pháp liệt kê hoặc duyệt toàn bộ. Nguyên lý cốt lõi là:

• Duyệt qua tất cả các cấu hình hợp lệ của bài toán;
• Với mỗi cấu hình, kiểm tra điều kiện nghiệm;
• Giữ lại nghiệm tốt nhất (hoặc nghiệm đầu tiên thỏa mãn).

Ưu điểm:

• Cài đặt đơn giản, dễ hiểu, ít lỗi logic;
• Đảm bảo tính đúng đắn nếu không gian nghiệm hữu hạn;
• Là chuẩn mực để đánh giá hiệu quả của các giải thuật tối ưu hơn.

Nhược điểm:

• Độ phức tạp thời gian thường cao (ví dụ: O(n!), O(2ⁿ), O(n²));
• Chỉ khả thi với kích thước đầu vào nhỏ (n ≤ 20 với hoán vị, n ≤ 30 với tổ hợp nhị phân);
• Không khai thác cấu trúc bài toán — thiếu tính "thông minh".

Ví dụ 1: Sắp xếp chèn — hiện thân của vét càn tuyến tính

Sắp xếp chèn hoạt động bằng cách xây dựng dãy đã sắp từ trái sang phải. Với mỗi phần tử ở vị trí i, thuật toán "đẩy lùi" các phần tử lớn hơn nó về bên phải để tạo chỗ trống, rồi chèn phần tử đó vào vị trí phù hợp.

Mỗi bước yêu cầu so sánh và dịch chuyển — một dạng vét càn cục bộ trên đoạn con đã xử lý.

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

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

int main() {
    std::vector<int> data = {6, 4, 7, 3};
    insertionSort(data);
    for (int x : data) std::cout << x << " ";
    // Output: 3 4 6 7
}

Ví dụ 2: Sinh hoán vị — vét càn trên không gian hoán vị

Bài toán: Liệt kê tất cả các hoán vị của tập {1, 2, ..., n}.

Thay vì viết vòng lặp lồng nhau (không mở rộng được với n thay đổi), ta dùng hàm chuẩn std::next_permutation, vốn thực hiện vét càn theo thứ tự từ điển trên mảng đã sắp tăng.

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

int main() {
    int n;
    std::cin >> n;
    std::vector<int> perm(n);
    for (int i = 0; i < n; ++i) perm[i] = i + 1;

    do {
        for (int x : perm) std::cout << x << " ";
        std::cout << "\n";
    } while (std::next_permutation(perm.begin(), perm.end()));
}

Lưu ý quan trọng: Hàm next_permutation chỉ sinh đúng toàn bộ hoán vị nếu mảng ban đầu ở trạng thái tăng dần. Nếu khởi tạo ngẫu nhiên (ví dụ {4,3,2,1}), nó chỉ sinh các hoán vị đứng sau trong thứ tự từ điển — dẫn đến kết quả thiếu.

Ví dụ 3: Bài toán ba lô 0-1 — nhiều cách tiếp cận vét càn

Cho n đồ vật, mỗi đồ vật i có khối lượng w[i] và giá trị v[i]. Cần chọn một tập con sao cho tổng khối lượng ≤ giới hạn W và tổng giá trị đạt cực đại.

Vì mỗi đồ vật chỉ chọn hoặc không chọn, không gian nghiệm gồm 2ⁿ tổ hợp nhị phân — phù hợp để áp dụng vét càn.

Cách 1: Duyệt nhị phân trực tiếp

Dùng số nguyên i từ 0 đến 2ⁿ − 1, mỗi bit trong biểu diễn nhị phân của i biểu thị trạng thái chọn của một đồ vật.

#include <iostream>
#include <vector>
#include <climits>

int main() {
    const int W = 10, n = 5;
    std::vector<int> w = {2, 2, 6, 5, 4};
    std::vector<int> v = {6, 3, 5, 4, 6};

    int bestValue = 0;
    int bestMask = 0;

    for (int mask = 0; mask < (1 << n); ++mask) {
        int weight = 0, value = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                weight += w[i];
                value += v[i];
            }
        }
        if (weight <= W && value > bestValue) {
            bestValue = value;
            bestMask = mask;
        }
    }

    std::cout << "Cách chọn: ";
    for (int i = 0; i < n; ++i) 
        std::cout << ((bestMask >> i) & 1) << " ";
    std::cout << "\nGia tri toi da: " << bestValue << "\n";
    // Output: Cách chọn: 1 1 0 0 1 → Gia tri toi da: 15
}

Cách 2: Quay lui (DFS)

Mỗi bước quyết định chọn hoặc bỏ qua đồ vật thứ i, duy trì tổng khối lượng và giá trị hiện tại. Khi duyệt hết n đồ vật, cập nhật nghiệm nếu hợp lệ.

#include <iostream>
#include <vector>

int W = 10;
std::vector<int> w = {2, 2, 6, 5, 4};
std::vector<int> v = {6, 3, 5, 4, 6};
int bestValue = 0;
std::vector<int> bestChoice(5, 0);

void dfs(int idx, int currentWeight, int currentValue, std::vector<int>& choice) {
    if (idx == w.size()) {
        if (currentWeight <= W && currentValue > bestValue) {
            bestValue = currentValue;
            bestChoice = choice;
        }
        return;
    }

    // Thử không chọn
    choice[idx] = 0;
    dfs(idx + 1, currentWeight, currentValue, choice);

    // Thử chọn (nếu còn đủ chỗ)
    if (currentWeight + w[idx] <= W) {
        choice[idx] = 1;
        dfs(idx + 1, currentWeight + w[idx], currentValue + v[idx], choice);
    }
}

int main() {
    std::vector<int> choice(5, 0);
    dfs(0, 0, 0, choice);
    
    std::cout << "Cach chon: ";
    for (int x : bestChoice) std::cout << x << " ";
    std::cout << "\nGia tri toi da: " << bestValue << "\n";
}

Cách 3: Sử dụng next_permutation với chuỗi nhị phân

Tạo chuỗi gồm n ký tự '0' và n ký tự '1', sau đó sinh toàn bộ hoán vị và xét n ký tự đầu làm mẫu chọn. Cách này kém hiệu quả hơn nhưng minh họa rõ tư duy vét càn trên cấu trúc rời rạc.

Kết luận

Vét càn không phải là "giải thuật yếu", mà là nền tảng để hiểu bản chất bài toán. Việc nhận diện khi nào một bài toán có thể giải bằng vét càn — và lựa chọn cách triển khai phù hợp (nhị phân, DFS, hoán vị, hoặc vòng lặp lồng) — là kỹ năng thiết yếu khi học phân tích độ phức tạp và thiết kế giải thuật.