♟️
Desain dan Analisis Algoritma

Paradigma Backtracking

DFS · State Space Tree · Pruning

Contoh
N-Queens
Penempatan ratu tanpa saling serang
Masalah
Subset Sum
Pilih subset dengan jumlah target
Paradigma
DFS + Undo
Bangun solusi, mundur jika buntu
Definisi & Intuisi

Apa itu Backtracking?

Backtracking adalah teknik pemecahan masalah yang membangun solusi secara bertahap, mencoba berbagai pilihan, dan mundur (backtrack) ketika pilihan tersebut terbukti tidak mengarah ke solusi yang valid. [1]

Biasanya diimplementasikan sebagai Depth-First Search pada state-space tree: setiap node mewakili solusi parsial, setiap edge mewakili keputusan baru. [1][2]

Teknik ini setara dengan brute force yang lebih pintar: masih eksplorasi ruang solusi, tetapi dengan pemangkasan (pruning) untuk menghindari cabang yang pasti gagal. [1][2]

Skema Umum

// Skema Backtracking Generik procedure Backtrack(solusi_parsial): if solusi_parsial sudah lengkap: if solusi_parsial valid: lapor / simpan solusi return // coba semua pilihan for each pilihan yang mungkin do terapkan pilihan → update solusi_parsial if solusi_parsial masih mungkin valid: Backtrack(solusi_parsial) batalkan pilihan (undo)
State-Space Tree

Ruang Keadaan & DFS

State-Space Tree

  • • Setiap node merepresentasikan solusi parsial.
  • • Root = keadaan awal (belum ada keputusan).
  • • Level k = sudah membuat k keputusan (misalnya menempatkan k ratu). [1][2]
  • • Daun (leaf) = solusi lengkap (bisa valid atau tidak valid).

Backtracking menjelajahi pohon ini dengan Depth-First Search, lalu “naik lagi” ketika sebuah cabang tidak bisa diperluas menjadi solusi yang valid. [1][2]

Contoh Singkat

Misal kita ingin mengisi 3 posisi dengan angka {1,2}. State-space tree akan mempunyai root kosong, lalu bercabang dua di setiap level:

              []
         /                 [1]          [2]
      /   \        /      [1,1] [1,2]  [2,1] [2,2]

Backtracking = DFS pada pohon ini + cek/pemangkasan ketika constraint dilanggar.

Contoh 1 — N-Queens

Masalah N-Queens

Masalah: letakkan N ratu pada papan catur N×N sehingga tidak ada dua ratu yang saling menyerang (tidak sebaris, sekolom, atau se-diagonal). [3]

Strategi Backtracking

  • • Tempatkan ratu baris demi baris (satu ratu per baris).
  • • Pada baris k, coba semua kolom 0..N−1 yang tidak diserang ratu sebelumnya.
  • • Jika pada suatu baris tidak ada kolom valid → backtrack ke baris sebelumnya dan geser ratu ke kolom lain.

Ini menghasilkan DFS pada state-space tree dengan kedalaman N, di mana setiap level mewakili baris ke-k. [3][4]

// Sketsa Backtracking N-Queens procedure NQueens(row): if row = N: cetak / simpan konfigurasi papan return for col ← 0 to N-1 do if posisi (row, col) aman: tempatkan ratu di (row, col) NQueens(row + 1) hapus ratu dari (row, col) // undo
Contoh 2 — Subset Sum

Masalah Subset Sum

Diberikan himpunan bilangan X dan target T, apakah ada subset dari X yang jumlahnya persis T? [1]

Strategi Backtracking

  • • Pada setiap langkah, pilih sebuah elemen x ∈ X.
  • • Cabang 1: masukkan x ke subset (T ← T−x).
  • • Cabang 2: abaikan x (T tetap).
  • • Jika T = 0 → ditemukan solusi. Jika T < 0 atau X habis → buntu, backtrack. [1]
// Backtracking Subset Sum (versi konseptual) function SubsetSum(X, T): if T = 0: return True elif T < 0 or X kosong: return False pilih suatu elemen x dari X X' ← X \ {x} // cabang: ambil x if SubsetSum(X', T - x): return True // cabang: tidak ambil x return SubsetSum(X', T)
Pruning

Pruning: Memotong Cabang Tidak Perlu

Tanpa pruning, backtracking bisa menjelajahi seluruh ruang solusi yang sering kali berukuran eksponensial (misal O(2ⁿ) atau O(n!)). [2][5]

Pruning = menghentikan eksplorasi suatu cabang lebih awal jika:

  • • solusi parsial sudah melanggar constraint (invalid), atau
  • • bahkan jika diperluas sekalipun tidak mungkin menghasilkan solusi lebih baik (untuk problem optimisasi). [2][5]

Dengan pruning yang efektif, waktu bisa berkurang jauh dibanding brute force murni. [5]

Contoh Pruning di Subset Sum

  • • Jika T < 0 → tidak perlu melanjutkan ke cabang lebih dalam.
  • • Jika jumlah maksimum semua elemen tersisa < T → sudah pasti tidak bisa mencapai T.

Contoh Pruning di N-Queens

  • • Begitu ratu di baris tertentu menyerang ratu sebelumnya secara diagonal, langsung berhenti di cabang itu.
  • • Tidak perlu menempatkan lebih dari 1 ratu di kolom yang sama di level-level berikut.
Analisis Kompleksitas

Seberapa Mahal Backtracking?

Secara umum, backtracking memiliki worst-case kompleksitas eksponensial, karena ruang solusi yang dieksplorasi sering kali eksponensial terhadap ukuran input. [2][5]

Contoh:

  • • N-Queens: maksimal O(Nⁿ) konfigurasi papan (walau dengan pruning jauh lebih sedikit). [3]
  • • Subset Sum: 2ⁿ subset yang mungkin. [1]

Keuntungan

  • • Sangat fleksibel, bisa menangani banyak jenis constraint. [2][6]
  • • Dengan pruning, sering kali jauh lebih cepat daripada enumerasi buta. [5][6]
  • • Mudah diparalelkan karena setiap cabang DFS relatif independen. [6]

Keterbatasan

  • • Tetap bisa sangat lambat untuk input besar atau constraint lemah. [2][6]
  • • Konsumsi memori untuk menyimpan state dan stack rekursi. [2][6]
  • • Tidak cocok untuk kebutuhan real-time yang ketat. [2][6]
Backtracking vs Brute Force

Bedanya Apa?

Aspek Brute Force Backtracking
Strategi eksplorasi Mencoba semua kemungkinan tanpa berhenti lebih awal. Mencoba kemungkinan, tetapi berhenti lebih awal pada cabang yang pasti gagal (pruning). [2][5]
Struktur Biasanya tidak memodelkan state-space tree secara eksplisit. State-space tree eksplisit, dengan DFS rekursif. [1][2]
Kinerja Selalu mengeksplorasi ruang penuh. Dalam praktik bisa jauh lebih cepat karena banyak cabang tidak dieksplorasi. [5]
Implementasi Sering lebih sederhana, tapi tidak efisien. Sedikit lebih kompleks (perlu undo) tapi lebih efisien.
Contoh Masalah Backtracking

Beberapa Problem Klasik

♟️

N-Queens

Tempatkan N ratu di papan N×N tanpa saling serang. [3][4][7]

🧩

Subset Sum / Knapsack

Cari subset dengan jumlah tertentu, atau kombinasi item dengan kapasitas terbatas. [1][7]

🎨

Graph Coloring

Warnai simpul graf sehingga tetangga tidak memiliki warna yang sama. [4][7]

🔢

Sudoku / Latin Square

Isi grid dengan angka tanpa melanggar aturan baris/kolom/blok. [2]

🧭

Hamiltonian Path / Knight’s Tour

Jalur yang mengunjungi semua simpul sekali, atau semua petak papan catur. [2][7]

🔐

Constraint Satisfaction

Masalah penugasan dengan constraint (map coloring, penjadwalan, dll.). [2][6]

Kesimpulan

Inti Paradigma Backtracking

Backtracking adalah DFS + undo + pruning. Paradigma ini sangat berguna untuk masalah kombinatorial dengan constraint rumit, di mana enumerasi brute force terlalu mahal, tetapi kita masih bisa memotong banyak cabang yang tidak menjanjikan.

🧠
Cara Pikir
Bangun solusi langkah demi langkah, selalu siap untuk mundur.
✂️
Pruning
Definisikan constraint dan fungsi bounding yang baik.
📊
Analisis
Worst-case sering eksponensial, tapi praktik bisa jauh lebih baik.
1 / 10