Penjelasan backtracking: cara kerja, kode, dan contoh

Masalah yang diselesaikan backtracking

Sebagian masalah meminta setiap susunan yang memenuhi sekumpulan aturan, atau salah satu susunan semacam itu: tempatkan 8 ratu agar tidak ada yang saling menyerang, isi grid Sudoku, daftar semua subset yang jumlahnya sama dengan target, temukan semua cara memecah string menjadi kata-kata kamus. Tidak ada rumus cerdas; Anda harus mencari. Mencoba setiap kombinasi lengkap secara buta jauh terlalu lambat, tetapi sebagian besar kombinasi parsial sudah tidak valid setelah beberapa pilihan.

Backtracking memeriksa aturan setelah setiap pilihan. Ketika solusi parsial melanggar aturan, seluruh cabang pohon pencarian itu langsung ditinggalkan dan algoritma kembali mencoba opsi berikutnya.

Ide dasar dengan kata-kata sederhana

1. Jika solusi parsial saat ini sudah lengkap, catat.
2. Jika belum, untuk setiap pilihan berikutnya yang mungkin: jika pilihan itu diizinkan, ambil (choose).
3. Lakukan rekursi untuk memperluas solusi lebih jauh (explore).
4. Batalkan pilihan, agar opsi berikutnya dimulai dari state yang sama (unchoose).

Ruang pencariannya berupa pohon: akarnya solusi kosong, setiap level menambah satu pilihan, dan daunnya kandidat lengkap. Backtracking adalah depth-first search pada pohon ini, dan pruning berarti memotong subpohon yang tidak mungkin berisi solusi.

Contoh: 4-Queens

Tempatkan 4 ratu pada papan 4 × 4, satu per baris, sehingga tidak ada dua ratu yang berbagi kolom atau diagonal. Kolom bernomor 0 sampai 3.

Melanjutkan pencarian menemukan satu-satunya solusi lain, 2, 0, 3, 1, yang merupakan bayangan cermin dari solusi pertama.

Implementasi Python

Simpan set kolom dan diagonal yang terpakai agar setiap pemeriksaan keamanan O(1). Pada satu diagonal row - col konstan, dan pada diagonal lainnya row + col konstan.

def solve_n_queens(n):
    solutions, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(cols.copy())   # copy, not the live list
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue                    # prune: square is attacked
            cols.append(col)                # choose
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            place(row + 1)                  # explore
            cols.pop()                      # unchoose
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    place(0)
    return solutions

print(solve_n_queens(4))       # [[1, 3, 0, 2], [2, 0, 3, 1]]
print(len(solve_n_queens(8)))  # 92

Template yang sama menghasilkan semua subset dan semua permutasi:

def subsets(items):
    result, current = [], []

    def go(i):
        if i == len(items):
            result.append(current.copy())
            return
        current.append(items[i]); go(i + 1); current.pop()   # take items[i]
        go(i + 1)                                            # skip items[i]

    go(0)
    return result

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def go():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; current.append(x)
                go()
                used[i] = False; current.pop()

    go()
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Untuk subset dan permutasi biasa di kode sungguhan, itertools.combinations dan itertools.permutations lebih cepat. Tulis backtracking sendiri bila Anda perlu pruning dengan aturan khusus masalah.

Kompleksitas waktu dan ruang

Backtracking tidak bisa mengalahkan ukuran output: jika Anda harus mendaftar n! permutasi, Anda butuh setidaknya n! langkah. Pruning hanya membantu dengan melewati cabang yang tidak menghasilkan apa-apa.

Varian dan kesalahan umum

• Lupa membatalkan: jika state tidak dipulihkan setelah pemanggilan rekursif, cabang berikutnya melihat pilihan yang basi.
• Menambahkan list yang masih dipakai: result.append(current) menyimpan referensi yang berubah kemudian; tambahkan current.copy().
• Duplikat pada input: urutkan item dan lewati item yang sama dengan sebelumnya pada kedalaman yang sama untuk menghindari subset atau permutasi duplikat.
• Berhenti pada solusi pertama: kembalikan True dari rekursi dan hentikan loop bila satu solusi sudah cukup, seperti pada solver Sudoku.
• Urutan yang lebih baik: coba pilihan paling terbatas lebih dulu (untuk Sudoku, sel kosong dengan kandidat paling sedikit). Ini sering mengecilkan pohon secara drastis.

Kapan memakainya dan penggunaannya di dunia nyata

• Constraint satisfaction: Sudoku, teka-teki silang, pewarnaan peta, penyusunan jadwal, dan jadwal ujian.
• SAT solver dan mesin logika ala Prolog dibangun di atas pencarian backtracking dengan pruning yang kuat.
• Mesin regular expression di banyak bahasa, termasuk re di Python, memakai backtracking; pola yang ditulis buruk bisa melakukan backtracking secara eksponensial ("catastrophic backtracking").
• Soal wawancara: subsets, permutations, combination sum, N-Queens, word search pada grid, palindrome partitioning, generate parentheses, letter combinations of a phone number.