Brute Force

Brute force sering dianggap solusi “pemalas”, tetapi sebenarnya ini adalah senjata paling penting dalam toolbox problem-solver. Brute force memberi baseline yang pasti benar, dapat dipakai untuk verifikasi solusi cepat, dan kadang memang cukup — soal dengan n ≤ 10 atau n ≤ 20 sering dapat diselesaikan dengan enumerasi penuh. Pada Chapter ini kita akan mempelajari dua pola brute force paling umum: enumerasi subset (semua himpunan bagian) dan enumerasi permutasi (semua urutan). Kita juga akan melihat kapan berhenti pada brute force dan kapan harus lanjut ke solusi optimal.

Kapan Brute Force Cukup #

Aturan: Lihat Constraint #

Brute force layak dipakai ketika n kecil. Berikut pedoman praktis:

Mekanisme: Mengapa Brute Force Sering Cukup #

Banyak soal “preliminary round” di kompetisi sengaja memuat subtask dengan n kecil agar brute force dapat skor parsial. Bahkan bila total soal butuh optimal, memulai dari brute force memberi kerangka kerja yang benar yang dapat kita optimasi secara bertahap.

Pola 1: Enumerasi Subset dengan Bitmask #

Aturan #

Diberikan n item, kita ingin mencoba semua 2^n himpunan bagian. Setiap himpunan bagian direpresentasikan sebagai bitmask integer 0..2^n - 1. Bit ke-i bernilai 1 berarti item ke-i termasuk subset.

Kode: Subset Sum via Bitmask #

#include <iostream>
#include <vector>

bool subset_sum_brute(const std::vector<int>& a, int target) {
    int n = static_cast<int>(a.size());
    for (int mask = 0; mask < (1 << n); ++mask) {
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) sum += a[i];
        }
        if (sum == target) return true;
    }
    return false;
}

int main() {
    std::vector<int> a = {3, 7, 11, 14, 19};
    for (int t : {10, 21, 25, 30, 100}) {
        std::cout << "subset_sum target=" << t << ": "
                  << (subset_sum_brute(a, t) ? "ADA" : "TIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

subset_sum target=10: ADA
subset_sum target=21: ADA
subset_sum target=25: ADA
subset_sum target=30: ADA
subset_sum target=100: TIDAK

1. Baris for (int mask = 0; mask < (1 << n); ++mask): iterasi semua 2^n kemungkinan bitmask. 1 << n adalah 2 pangkat n.
2. Baris if (mask & (1 << i)): cek apakah bit ke-i menyala di mask. Bila ya, item ke-i masuk subset.
3. Baris if (sum == target) return true;: berhenti lebih awal saat ditemukan. Optimasi praktis tanpa mengubah kompleksitas terburuk.
4. Hasil 10 → ADA: subset {3, 7} = 10. Sesuai.
5. Hasil 25 → ADA: subset {11, 14} = 25. Sesuai.
6. Hasil 30 → ADA: subset {11, 19} = 30. Sesuai.

Pola 2: Enumerasi Permutasi #

Aturan #

Untuk masalah yang sensitif terhadap urutan (misalnya TSP, job scheduling), kita harus mencoba semua n! urutan. C++ menyediakan std::next_permutation yang menghasilkan permutasi berikutnya dalam urutan leksikografis.

Kode: TSP Mini dengan Permutasi #

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

int tsp_brute(const std::vector<std::vector<int>>& dist) {
    int n = static_cast<int>(dist.size());
    std::vector<int> order(n);
    for (int i = 0; i < n; ++i) order[i] = i;
    int best = INT_MAX;
    do {
        int total = 0;
        for (int i = 0; i + 1 < n; ++i) total += dist[order[i]][order[i+1]];
        best = std::min(best, total);
    } while (std::next_permutation(order.begin(), order.end()));
    return best;
}

int main() {
    std::vector<std::vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    std::cout << "TSP minimum = " << tsp_brute(dist) << '\n';
    return 0;
}

Output yang Dihasilkan:

TSP minimum = 50

1. Baris for (int i = 0; i < n; ++i) order[i] = i;: inisialisasi urutan pertama. std::next_permutation butuh array sorted sebagai titik mulai.
2. Baris do { ... } while (std::next_permutation(...)): gunakan do-while agar permutasi awal juga diproses. std::next_permutation mengembalikan false saat kembali ke urutan awal.
3. Baris for (int i = 0; i + 1 < n; ++i) total += dist[order[i]][order[i+1]];: jumlahkan jarak antar kota berurutan dalam permutasi saat ini.
4. Baris best = std::min(best, total);: simpan biaya minimum lintas semua permutasi.
5. Hasil 50: rute 2 → 0 → 1 → 3 = dist[2][0] + dist[0][1] + dist[1][3] = 15 + 10 + 25 = 50. Brute force tidak mengasumsikan titik mulai tertentu, sehingga menemukan rute mulai dari kota mana pun.

Pola 3: Brute Force dengan Pruning (Cepat) #

Aturan #

Kita dapat menambahkan pruning sederhana untuk memotong cabang pencarian yang pasti tidak menghasilkan jawaban lebih baik. Ini adalah jembatan menuju backtracking yang lebih sistematis.

Kode: Subset Sum dengan Pruning Awal #

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

bool subset_with_prune(const std::vector<int>& a, int target) {
    std::vector<int> sorted_a = a;
    std::sort(sorted_a.rbegin(), sorted_a.rend());  // descending
    long long total = 0;
    for (int x : sorted_a) total += x;
    if (total < target) return false;       // pruning global

    // DFS dengan pruning
    std::function<bool(int, long long)> dfs = [&](int i, long long cur) -> bool {
        if (cur == target) return true;
        if (cur > target) return false;     // pruning: sudah lewat
        if (i == (int)sorted_a.size()) return false;
        // Coba ambil atau skip
        if (dfs(i + 1, cur + sorted_a[i])) return true;
        if (dfs(i + 1, cur)) return true;
        return false;
    };
    return dfs(0, 0);
}

int main() {
    std::vector<int> a = {3, 7, 11, 14, 19};
    for (int t : {10, 21, 25, 30, 100}) {
        std::cout << "prune target=" << t << ": "
                  << (subset_with_prune(a, t) ? "ADA" : "TIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

prune target=10: ADA
prune target=21: ADA
prune target=25: ADA
prune target=30: ADA
prune target=100: TIDAK

1. Baris std::sort(sorted_a.rbegin(), sorted_a.rend());: urutkan menurun. Tujuannya: nilai besar dicoba duluan, sehingga pruning cur > target lebih sering memotong.
2. Baris if (total < target) return false;: pruning global — bila jumlah semua elemen kurang dari target, tidak mungkin ada subset yang cocok.
3. Baris if (cur > target) return false;: pruning lokal — bila jumlah sementara sudah melebihi target (semua nilai non-negatif), cabang ini pasti gagal.
4. Baris if (dfs(i + 1, cur + sorted_a[i])) return true;: rekursi untuk “ambil item ke-i”.
5. Baris if (dfs(i + 1, cur)) return true;: rekursi untuk “skip item ke-i”.
6. Hasil identik dengan bitmask: verifikasi bahwa pruning tidak mengubah jawaban, hanya mempercepat.

Ringkasan #

• Brute force layak dipakai saat n kecil: n ≤ 10 untuk O(n!), n ≤ 20 untuk O(2^n).
• Enumerasi subset paling alami menggunakan bitmask 0..2^n-1. Cek bit ke-i dengan mask & (1 << i).
• Enumerasi permutasi paling mudah memakai std::next_permutation dengan do-while.
• Tambahkan pruning sederhana (sort menurun + cek batas) untuk memotong cabang gagal lebih awal.
• Brute force bukan kegagalan — ini baseline yang pasti benar dan alat verifikasi untuk solusi cepat.