Analisis Kompleksitas Backtracking

Setiap algoritma backtracking mengeksplorasi sebuah state-space tree — pohon keputusan di mana setiap node mewakili keadaan parsial dan setiap anak mewakili sebuah pilihan. Ukuran pohon ini menentukan kompleksitas waktu. Dua parameter utamanya adalah branching factor b (banyaknya anak rata-rata per node) dan depth d (panjang jalur terpanjang dari root ke daun). State space kasar-kasar adalah b^d — yakni pertumbuhan eksponensial terhadap kedua parameter. Pada Chapter ini kita akan memetakan kompleksitas berbagai soal backtracking klasik, mengukur rasio node aktual vs batas teoretis, dan menjelaskan mengapa pruning mengecilkan konstanta tanpa mengubah kelas Big-O worst case.

Aturan: Branching Factor × Depth = State Space #

Untuk pohon keputusan dengan branching factor rata-rata b dan kedalaman d, banyaknya node total dalam pohon tak terpotong adalah:

text

1 + b + b^2 + ... + b^d = (b^(d+1) - 1) / (b - 1)

Untuk b besar, suku dominan adalah b^d, sehingga kompleksitas ditulis sebagai O(b^d). Inilah rumus dasar analisis backtracking.

Soal	Branching factor `b`	Depth `d`	Worst case (naif)
N-Queens	`n` (kolom kandidat per baris)	`n` (baris)	O(n^n)
Subset sum	`2` (include/exclude)	`n` (elemen)	O(2^n)
Subset generation	`2`	`n`	O(2^n)
Permutation generation	`n - i` pada level `i`	`n`	O(n!)
Combination C(n, k)	`2` (include/exclude) dengan cut	`n`	O(C(n, k))
Sudoku	`9` (digit kandidat)	`81` (sel)	O(9^81) ≈ 2 × 10^77

N-Queens: Dari O(n^n) ke O(n!) dengan Pruning #

Aturan #

N-Queens menempatkan n ratu pada papan n × n tanpa saling serang. Naif: setiap ratu bisa di n kolom, ada n ratu → pohon berukuran n^n. Dengan feasibility pruning (cek konflik kolom/diagonal sebelum rekursi), banyak kandidat yang tersisa per level menyusut: di baris ke-i, paling banyak ada n - i kolom yang valid (asumsi longgar), sehingga jumlah daun dibatasi oleh n!.

Kode: Mengukur Node Aktual vs n! #

cpp
#include <iostream>
#include <vector>

long long g_nodes = 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;                  // kolom sama
        int dr = row - r;
        int dc = c - col;
        if (dc < 0) dc = -dc;
        if (dr == dc) return false;                  // diagonal
    }
    return true;
}

void nqueens(std::vector<int>& pos, int row, int n) {
    ++g_nodes;
    if (row == n) return;                            // solusi tercapai
    for (int col = 0; col < n; ++col) {
        if (aman(pos, row, col)) {                   // feasibility pruning
            pos[row] = col;
            nqueens(pos, row + 1, n);
        }
    }
}

long long factorial(int n) {
    long long f = 1;
    for (int i = 2; i <= n; ++i) f *= i;
    return f;
}

int main() {
    std::cout << "Perbandingan node dikunjungi vs n! (worst case):\n";
    for (int n : {4, 6, 8, 10, 12}) {
        std::vector<int> pos(n, -1);
        g_nodes = 0;
        nqueens(pos, 0, n);
        long long nf = factorial(n);
        double ratio = static_cast<double>(g_nodes) / nf;
        std::cout << "n=" << n
                  << " | node=" << g_nodes
                  << " | n!=" << nf
                  << " | ratio=" << ratio << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
Perbandingan node dikunjungi vs n! (worst case):
n=4 | node=17 | n!=24 | ratio=0.708333
n=6 | node=153 | n!=720 | ratio=0.2125
n=8 | node=2057 | n!=40320 | ratio=0.0510169
n=10 | node=35539 | n!=3628800 | ratio=0.0097936
n=12 | node=856189 | n!=479001600 | ratio=0.00178744

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

Variabel global g_nodes: penghitung node yang dikunjungi. Di-increment di awal setiap panggilan rekursif agar setiap node (termasuk daun dan internal) terhitung tepat satu kali.
Fungsi aman: feasibility check. Mengembalikan false bila ratu di (row, col) konflik dengan ratu mana pun di baris 0..row-1. Bila false, loop for skip kolom ini — cabang dipotong sebelum rekursi.
Baris if (aman(pos, row, col)): titik krusial pruning. Tanpa baris ini, algoritma akan mencoba semua n kolom tiap baris dan menghasilkan n^n node.
Output n=12: 856 ribu node aktual vs 479 juta (12!). Rasio 0.0018 berarti pruning memangkas 99.82% dari n! dan jauh lebih banyak dari n^n = 8.92 × 10^12 (rasio 9.6 × 10^-8).
Tren rasio menurun: dari 0.71 (n=4) ke 0.0018 (n=12). Ini menunjukkan pruning makin efektif untuk n besar — solusi valid makin jarang sehingga makin banyak cabang yang dipotong lebih awal.

Kompleksitas formal N-Queens dengan feasibility pruning adalah O(n!) worst case. Untuk konfigurasi tertentu (papan dengan solusi jarang), pruning bisa mengecilkan konstanta hingga orde ribuan.

Subset Sum: O(2^n) yang Ketat #

Aturan #

Subset sum: diberikan array a berisi n bilangan dan target T. Tentukan apakah ada subset dengan jumlah tepat T. Setiap elemen memiliki dua pilihan (include atau exclude), sehingga pohon keputsan adalah binary tree dengan 2^n daun dan 2^(n+1) - 1 node total. Worst case terjadi bila tidak ada subset yang mencapai target — algoritma harus mengunjungi seluruh pohon.

Kode: Mengukur Node Aktual vs 2^n #

cpp
#include <iostream>
#include <vector>

long long g_nodes = 0;

bool subset_sum(const std::vector<int>& a, size_t i, int cur, int target) {
    ++g_nodes;
    if (cur == target) return true;                  // solusi ditemukan
    if (i == a.size()) return false;                 // habis, tidak ketemu
    if (subset_sum(a, i + 1, cur + a[i], target))    // include a[i]
        return true;
    if (subset_sum(a, i + 1, cur, target))           // exclude a[i]
        return true;
    return false;
}

int main() {
    std::cout << "Subset sum node count vs 2^n (worst case, target tidak ada):\n";
    for (int n : {5, 10, 15, 20}) {
        std::vector<int> a;
        for (int i = 0; i < n; ++i) a.push_back(i + 1);
        g_nodes = 0;
        subset_sum(a, 0, 0, -1);                     // target=-1, mustahil
        long long pow2 = 1LL << n;
        std::cout << "n=" << n
                  << " | node=" << g_nodes
                  << " | 2^n=" << pow2
                  << " | ratio=" << static_cast<double>(g_nodes) / pow2 << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
Subset sum node count vs 2^n (worst case, target tidak ada):
n=5 | node=63 | 2^n=32 | ratio=1.96875
n=10 | node=2047 | 2^n=1024 | ratio=1.99902
n=15 | node=65535 | 2^n=32768 | ratio=1.99997
n=20 | node=2097151 | 2^n=1048576 | ratio=2

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

Target -1: karena cur selalu ≥ 0 (semua elemen positif), kondisi cur == target tak pernah terpenuhi. Algoritma harus menjelajahi seluruh pohon. Inilah skenario worst case.
Total node = 2^(n+1) - 1: pohon biner lengkap dengan n level. Untuk n=20, total = 2,097,151 node = 2^21 - 1.
Rasio mendekati 2: rasio node / 2^n = (2^(n+1) - 1) / 2^n = 2 - 1/2^n, yang menuju 2 untuk n besar. Inilah bukti bahwa kompleksitas Θ(2^n) — konstanta faktor 2 tidak mempengaruhi kelas Big-O.
Tanpa bound pruning: untuk target yang realistis (misalnya T = n*(n+1)/4), subset dengan jumlah T sering ditemukan lebih awal dan algoritma berhenti. Tetapi worst case tetap O(2^n).
Implikasi praktis: untuk n = 30, batas teoretis ~2 miliar node. Algoritma naive berhenti pada ~30-60 detik; dengan memoization (subset sum DP) bisa diturunkan ke O(n × T).

Sudoku: Sulit Dibatasi Secara Presisi #

Sudoku 9×9 memiliki 81 sel, masing-masing dapat berisi 1-9. Worst case naif: 9^81 ≈ 2 × 10^77 node — angka astronomi yang mustahil dihitung. Kenyataannya, Sudoku solver praktis berjalan dalam milidetik. Bagaimana mungkin?

Alasannya: branching factor aktual jauh di bawah 9 karena constraint propagation. Setelah sel-sel tertentu terisi, banyak kandidat di sel berikutnya otomatis tereliminasi oleh aturan baris/kolom/kotak 3×3. Kompleksitas tergantung pada:

Banyak sel kosong awal: petunjuk yang diberikan membatasi depth.
Distribusi petunjuk: puzzle dengan petunjuk tersebar merata biasanya lebih mudah.
Urutan sel yang dipilih: MRV (minimum remaining values) heuristik memilih sel dengan kandidat paling sedikit dulu, memangkas pohon lebih awal.
Constraint propagation: deduksi sel tunggal (sel yang hanya punya 1 kandidat) menurunkan depth tanpa branching.

Karena faktor-faktor ini, tidak ada batas Big-O yang ketat untuk Sudoku backtracking solver yang bergantung pada instance. Analisis formal terbaik tetap O(9^81) worst case, tetapi praktiknya jauh lebih cepat.

State-Space Tree dengan Pruning #

Visualisasi pohon keputusan menunjukkan bagaimana pruning memotong cabang sebelum sempat dieksplorasi penuh:

flowchart TD Root["state awal"] --> A1["pilih opsi 1"] Root --> A2["pilih opsi 2"] Root --> A3["pilih opsi 3"] A1 --> B1["lanjut eksplorasi"] A1 -.->|pruning: constraint violation| BCut["✂ dipotong"] A2 --> B2["lanjut eksplorasi"] B2 --> C1["solusi ditemukan"] A3 -.->|pruning: bound tidak menjanjikan| ACut["✂ dipotong"] B1 --> C2["dead end"] C2 -.->|backtrack| A1

Garis putus-putus dengan tanda ✂ menyimbolkan cabang yang tidak dijelajahi berkat pruning. Garis solid menyimbolkan jalur yang benar-benar dieksplorasi. Tanpa pruning, semua cabang (termasuk yang dipotong) akan dikunjungi.

Pruning Mengecilkan Konstanta, Bukan Kelas #

Mengapa kelas tidak berubah? Karena analisis worst case mengasumsikan input yang paling tidak menyenangkan — yakni input di mana pruning tidak efektif. Untuk N-Queens, tidak ada instance yang membuat pruning gagal total (selalu ada konflik yang bisa dideteksi lebih awal), sehingga worst case lebih rendah dari n^n menjadi n!. Tetapi untuk subset sum, ada instance (target mustahil dengan elemen tidak terurut) yang memaksa eksplorasi penuh 2^n.

Tiga pelajaran praktis:

Average case sering jauh lebih cepat dari worst case — algoritma N-Queens dengan pruning menyelesaikan n=12 dalam milidetik meski worst case-nya 12!.
Pruning efektif bila constraint ketat. Subset sum dengan elemen kecil-kecil (sum maksimum rendah) dapat ditambah DP untuk menjadi pseudo-polinomial O(n × T).
Untuk soal dengan kelas eksponensial, solusi praktis adalah ganti pendekatan: gunakan DP (subset sum), approximation algorithm (TSP), atau specialized algorithm (Sudoku dengan SAT solver) ketika n terlalu besar.

Perbandingan Kompleksitas Soal Backtracking #

Soal	`b`	`d`	Naif	Dengan pruning	Catatan
N-Queens	`n`	`n`	O(n^n)	O(n!)	Feasibility pruning kolom/diagonal
Subset sum	2	`n`	O(2^n)	O(2^n)	Bound pruning membantu rata-rata, bukan worst
Subset generation	2	`n`	O(2^n)	O(2^n)	Output saja sudah 2^n
Permutation	`n - i`	`n`	O(n!)	O(n!)	Tidak ada yang bisa dipotong
Combination C(n, k)	2	`n`	O(2^n)	O(C(n, k))	Cut saat `cur.size() > k` atau `sisa < k - cur.size()`
Sudoku 9×9	9	81	O(9^81)	praktis cepat	Constraint propagation menurunkan `b` aktual
Maze solving	4 (arah)	panjang jalur	O(4^L)	O(L²) dengan BFS	Backtracking suboptimal vs BFS

Ringkasan #

Kompleksitas backtracking naif adalah O(b^d) dengan b branching factor dan d depth.
N-Queens: naif O(n^n), dengan feasibility pruning O(n!). Untuk n=12, pruning memangkas 99.82% node.
Subset sum: O(2^n) ketat, dengan rasio node/2^n ≈ 2 pada worst case (target mustahil).
Sudoku: O(9^81) worst case teoretis, tetapi constraint propagation membuat solver praktis berjalan dalam milidetik. Tidak ada batas Big-O ketat untuk instance umum.
Pruning mengecilkan konstanta, bukan kelas. Average case bisa jauh lebih cepat; worst case tetap O(b^d).
Untuk n besar, alihkan ke pendekatan lain: DP untuk subset sum, approximation untuk TSP, atau specialized solver untuk Sudoku.