Pruning

Pruning adalah teknik memotong cabang pada state-space tree yang dipastikan tidak akan menghasilkan solusi atau solusi optimal. Bayangkan mencari jalan di maze: bila kita tahu lorong tertentu buntu lebih awal (misalnya tidak ada jalan keluar dari zona itu), tidak perlu menjelajahi seluruh lorong. Pada N-Queens, pruning sederhana “cek konflik kolom/diagonal sebelum rekursi” mengurangi node yang dieksplorasi dari ~n^n (naif) menjadi n! (dengan pruning). Pada Chapter ini kita akan membandingkan N-Queens dengan dan tanpa pruning, serta mempelajari jenis-jenis pruning umum.

Aturan: Potong Sebelum Eksplorasi #

Pruning dilakukan sebelum panggilan rekursif, bukan setelah. Algoritma:

1. Generate kandidat pilihan.
2. Filter: buang kandidat yang melanggar constraint atau tidak menjanjikan.
3. Untuk setiap kandidat tersisa, lakukan choose-explore-unchoose.

Tanpa pruning, semua kandidat dijelajahi → eksponensial penuh. Dengan pruning, banyak cabang dipotong sebelum sempat menjelajahi subtree.

Jenis Pruning #

Empat jenis pruning umum dalam backtracking:

N-Queens: Tanpa Pruning vs Dengan Pruning #

Tanpa Pruning (Naif) #

Coba semua kemungkinan: setiap ratu bisa di kolom mana saja (0 hingga n-1), bahkan bila konflik. Baru cek di akhir bila solusi valid.

Dengan Pruning #

Sebelum menempatkan ratu di (row, col), cek konflik kolom dan diagonal dengan ratu-ratu sebelumnya. Bila konflik, skip kolom ini.

Kode: Perbandingan Node Eksplorasi #

#include <iostream>
#include <vector>

long long g_nodes_no_prune = 0;
long long g_nodes_prune = 0;

bool aman(const std::vector<int>& pos, int row, int col) {
    for (int r = 0; r < row; ++r) {
        int c = pos[r];
        if (c == col) return false;
        int dr = row - r;
        int dc = c - col;
        if (dc < 0) dc = -dc;
        if (dr == dc) return false;
    }
    return true;
}

// Tanpa pruning: coba semua kolom, cek di akhir
void nqueens_no_prune(std::vector<int>& pos, int row, int n) {
    ++g_nodes_no_prune;
    if (row == n) return;  // semua ratu terpasang
    for (int col = 0; col < n; ++col) {
        pos[row] = col;
        nqueens_no_prune(pos, row + 1, n);
    }
}

// Dengan pruning: cek aman sebelum rekursi
void nqueens_prune(std::vector<int>& pos, int row, int n) {
    ++g_nodes_prune;
    if (row == n) return;
    for (int col = 0; col < n; ++col) {
        if (aman(pos, row, col)) {
            pos[row] = col;
            nqueens_prune(pos, row + 1, n);
        }
    }
}

int main() {
    for (int n : {4, 6, 8, 10}) {
        std::vector<int> pos(n, -1);
        g_nodes_no_prune = 0;
        nqueens_no_prune(pos, 0, n);
        g_nodes_prune = 0;
        nqueens_prune(pos, 0, n);
        std::cout << "n=" << n
                  << " | tanpa pruning: " << g_nodes_no_prune << " node"
                  << " | dengan pruning: " << g_nodes_prune << " node"
                  << " | ratio: " << static_cast<double>(g_nodes_no_prune) / g_nodes_prune
                  << "x\n";
    }
    return 0;
}

Output yang Dihasilkan:

n=4 | tanpa pruning: 341 node | dengan pruning: 17 node | ratio: 20.0588x
n=6 | tanpa pruning: 55987 node | dengan pruning: 153 node | ratio: 365.928x
n=8 | tanpa pruning: 19173961 node | dengan pruning: 2057 node | ratio: 9321.32x
n=10 | tanpa pruning: 11111111111 node | dengan pruning: 35539 node | ratio: 312646x

1. Tanpa pruning n^n nodes: untuk n=8, 8^8 ≈ 16.7 juta node. Fungsi ini mengunjungi tepat sum_{i=0}^{n} n^i = (n^{n+1} - 1)/(n - 1) node — total node di pohon tak terpotong (terlihat dari pola 11111... untuk n=10 → 11 digit 1 = 11111111111).
2. Dengan pruning jauh lebih sedikit: untuk n=8, hanya 2057 node. Ratio peningkatan ~9300x.
3. Pola pertumbuhan: tanpa pruning tumbuh n^n (eksponensial basis n), dengan pruning tumbuh kira-kira n! (factorial).
4. Pelajaran: pruning adalah perbedaan antara “mustahil selesai” dan “selesai dalam milidetik”.

Pruning untuk Optimality: Branch and Bound #

Pada soal optimasi (cari solusi terbaik), kita simpan best so far. Bila estimasi lower bound solusi parsial saat ini sudah lebih buruk dari best, skip subtree.

Contoh: Subset Sum dengan Pruning #

Diberikan array bilangan bulat positif dan target T. Cari subset dengan jumlah tepat T.

Kode: Subset Sum dengan Bound Pruning #

#include <iostream>
#include <vector>
#include <numeric>

int g_nodes = 0;

bool subset_sum(const std::vector<int>& a, size_t i, int cur, int target,
                int sisa_sum)
{
    ++g_nodes;
    if (cur == target) return true;
    if (i == a.size()) return false;

    // Pruning: bila cur + sisa_sum < target, mustahil mencapai target
    if (cur + sisa_sum < target) return false;
    // Pruning: bila cur saja sudah > target, jangan tambah lagi
    // (asumsi a berisi bilangan bulat positif)

    // Pilih a[i]
    if (cur + a[i] <= target) {
        if (subset_sum(a, i + 1, cur + a[i], target, sisa_sum - a[i]))
            return true;
    }
    // Tidak pilih a[i]
    return subset_sum(a, i + 1, cur, target, sisa_sum - a[i]);
}

int main() {
    std::vector<int> a = {3, 7, 2, 8, 5, 1, 4, 6};
    int target = 15;
    int total = std::accumulate(a.begin(), a.end(), 0);

    g_nodes = 0;
    bool found = subset_sum(a, 0, 0, target, total);
    std::cout << "target " << target << (found ? " ketemu" : " tidak ketemu") << '\n';
    std::cout << "node dieksplorasi: " << g_nodes << '\n';

    // Bandingkan tanpa pruning
    g_nodes = 0;
    int impossible = -999;
    bool found2 = subset_sum(a, 0, 0, 100, total);
    std::cout << "target 100 (mustahil) " << (found2 ? "ketemu" : "tidak ketemu") << '\n';
    std::cout << "node dieksplorasi: " << g_nodes << '\n';
    return 0;
}

Output yang Dihasilkan:

target 15 ketemu
node dieksplorasi: 15
target 100 (mustahil) tidak ketemu
node dieksplorasi: 1

1. Parameter sisa_sum: jumlah elemen dari indeks i hingga akhir. Dihitung sekali di awal dan di-decrement per level.
2. Baris if (cur + sisa_sum < target) return false;: pruning — bila jumlah maksimum yang bisa dicapai dari sini kurang dari target, mustahil. Skip seluruh subtree.
3. Hasil target=15: ketemu dalam 15 node (vs ~256 node tanpa pruning = 2^8).
4. Hasil target=100 (mustahil karena total 36): terdeteksi dalam 1 node — langsung di root. Tanpa pruning, akan menjelajahi semua 2^8 = 256 node.

Symmetry Pruning pada N-Queens #

Papan catur simetris: solusi pada kolom 0-baris-pertama adalah mirror dari solusi pada kolom n-1-baris-pertama. Kita bisa memotong separuh ruang pencarian.

Kode: N-Queens dengan Symmetry Pruning #

#include <iostream>
#include <vector>

int g_solutions = 0;

bool aman(const std::vector<int>& pos, int row, int col) {
    for (int r = 0; r < row; ++r) {
        int c = pos[r];
        if (c == col) return false;
        int dr = row - r;
        int dc = c - col;
        if (dc < 0) dc = -dc;
        if (dr == dc) return false;
    }
    return true;
}

void solve(std::vector<int>& pos, int row, int n) {
    if (row == n) { ++g_solutions; return; }
    for (int col = 0; col < n; ++col) {
        if (aman(pos, row, col)) {
            pos[row] = col;
            solve(pos, row + 1, n);
        }
    }
}

int main() {
    int n = 8;
    std::vector<int> pos(n, -1);
    g_solutions = 0;
    solve(pos, 0, n);
    std::cout << "n=" << n << ", solusi tanpa symmetry pruning: "
              << g_solutions << '\n';
    return 0;
}

Output yang Dihasilkan:

n=8, solusi tanpa symmetry pruning: 92

1. Total 92 solusi untuk n = 8 (kelasik). Tanpa symmetry pruning, semua dihitung.
2. Dengan symmetry pruning: hanya coba kolom 0 sampai n/2 - 1 di baris pertama. Setiap solusi yang ditemukan merepresentasikan 8 solusi simetri (rotasi + flip) — kecuali beberapa yang simetris sempurna.
3. Kompleksitas: dari 92 node solusi → 12 unik (rasio ~7.7x). Untuk n besar, penghematan 4-8x.

Pengukuran Dampak Pruning #

Pruning mengurangi kompleksitas secara dramatis tetapi tidak mengubah kelas kompleksitas worst case. N-Queens dengan pruning tetap O(n!) worst case (untuk konfigurasi tanpa solusi valid, semua simpul harus diperiksa).

Kapan Pruning Tidak Membantu #

Pruning efektif bila:

1. Constraint ketat: banyak pilihan yang bisa difilter awal. N-Queens (4 constraint per ratu) cocok.
2. Solusi jarang: bila solusi sangat sedikit, pruning memotong hampir semua cabang.
3. Bound informatif: lower/upper bound yang ketat memungkinkan optimality pruning.

Pruning kurang efektif bila:

1. Constraint longgar: banyak pilihan lolos filter. Subset sum tanpa target (cari semua subset) tidak ada yang bisa dipotong.
2. Solusi padat: bila sebagian besar cabang mengandung solusi, tidak banyak yang bisa dipotong.
3. Bound lemah: bila estimasi lower bound jauh dari aktual, pruning tidak terpicu.

Ringkasan #

• Pruning memotong cabang state-space tree sebelum eksplorasi penuh.
• Empat jenis utama: feasibility, optimality, symmetry, bound.
• N-Queens dengan feasibility pruning: dari n^n menjadi ~n! node. Rasio 10x-30000x untuk n=4..12.
• Subset sum dengan bound pruning: deteksi “mustahil” dalam O(1) langsung di root.
• Symmetry pruning: manfaatkan simetri papan untuk memotong setengah atau lebih ruang pencarian.
• Pruning tidak mengubah kelas Big-O worst case, tetapi konstanta berkurang dramatis.