Teknik Desain · Pelajaran 8 dari 10
Backtracking
10 menit baca · BelajarCode
Backtracking menelusuri ruang solusi secara rekursif: tambahkan satu pilihan, lanjutkan, dan jika ternyata buntu, batalkan pilihan itu (mundur) lalu coba pilihan lain. Kekuatannya ada pada pemangkasan: cabang yang pasti gagal tidak ditelusuri lebih jauh.
N-Queens
Tempatkan N ratu catur di papan N × N sehingga tidak ada dua ratu yang saling menyerang (tidak sebaris, sekolom, atau sediagonal).
1def n_ratu(n):2 solusi = []3 kolom = set()4 diag1 = set()5 diag2 = set()6 posisi = []78 def tempatkan(baris):9 if baris == n:10 solusi.append(posisi.copy())11 return12 for k in range(n):13 if k in kolom or baris - k in diag1 or baris + k in diag2:14 continue15 kolom.add(k)16 diag1.add(baris - k)17 diag2.add(baris + k)18 posisi.append(k)19 tempatkan(baris + 1)20 posisi.pop()21 kolom.remove(k)22 diag1.remove(baris - k)23 diag2.remove(baris + k)2425 tempatkan(0)26 return solusi2728for n in [4, 6, 8]:29 print(n, "ratu:", len(n_ratu(n)), "solusi")3031papan = n_ratu(6)[0]32for k in papan:33 print(" ".join("Q" if c == k else "." for c in range(6)))4 ratu: 2 solusi 6 ratu: 4 solusi 8 ratu: 92 solusi . Q . . . . . . . Q . . . . . . . Q Q . . . . . . . Q . . . . . . . Q .
Himpunan kolom, diag1 (selisih baris dan kolom), dan diag2 (jumlah baris dan kolom) memeriksa serangan dalam O(1). Tanpa pemangkasan, brute force harus mencoba 8⁸ (lebih dari 16 juta) susunan untuk N = 8.
Subset sum
Apakah ada himpunan bagian yang jumlahnya tepat sama dengan target?
1def subset_sum(angka, target):2 angka = sorted(angka, reverse=True)3 hasil = []45 def coba(i, sisa, dipilih):6 if sisa == 0:7 hasil.append(dipilih.copy())8 return9 if i == len(angka) or sisa < 0:10 return11 if sum(angka[i:]) < sisa:12 return13 dipilih.append(angka[i])14 coba(i + 1, sisa - angka[i], dipilih)15 dipilih.pop()16 coba(i + 1, sisa, dipilih)1718 coba(0, target, [])19 return hasil2021print(subset_sum([3, 34, 4, 12, 5, 2], 9))[[5, 4], [4, 3, 2]]
Baris if sum(angka[i:]) < sisa: return memangkas cabang yang mustahil mencapai target walaupun semua sisa angka diambil.
Cek pemahaman
Apa yang membuat backtracking lebih efisien dari brute force murni?
Latihan
Semua permutasi
Tulis fungsi backtracking yang menghasilkan semua permutasi dari sebuah string tanpa memakai itertools. Uji dengan "abc".
Pembahasan
1def permutasi(teks):2 hasil = []3 dipakai = [False] * len(teks)4 sekarang = []56 def bangun():7 if len(sekarang) == len(teks):8 hasil.append("".join(sekarang))9 return10 for i, karakter in enumerate(teks):11 if dipakai[i]:12 continue13 dipakai[i] = True14 sekarang.append(karakter)15 bangun()16 sekarang.pop()17 dipakai[i] = False1819 bangun()20 return hasil2122print(permutasi("abc"))['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Ada n! permutasi, jadi waktunya Θ(n · n!). Untuk masalah yang memang meminta semua permutasi, tidak ada cara yang lebih cepat.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.