Metode Backtracking

Teknik Backtracking merupakan salah satu cara dalam penyelesaian suatu masalah secara
umum (General Problem Solving). Dasar dari teknik Backtracking ini adalah suatu teknik
pencarian (searching). Teknik pencarian ini digunakan dalam rangka mencari penyelesaian-
penyelesaian yang mungkin (feasible solution) dari suatu masalah sehingga terbentuk suatu
himpunan pcnyelesaiannya. Dari himpunan penyelesaian tersebut akan diperoleh penyelesaian
yang memuaskan atau solusi yang optimal.

Teknik Backtracking ini pertama kali dipcrkenalkan oleh D.H. Lehmer pada lahun 1950. Ide
terscbut baru dapat dirumuskan dalam suatu algoritma secara umum pada tahun 1960 oleh R
J. Walker Pada tahun yang sama, selelah penyaji algoritma dari teknik Backtracking
dikembangkanlah variasi aplikasinya oleh Golomb dan Baumert.

Adapun langkah pertama dari teknik Backtracking ini adalah dengan membentuk suatu
himpunan penyelesaian yang mungkin atau diharapkan. Himpunan tersebut berbentuk sebagai
n~tuple yakni (X1. x2,..., xn) dengan X1 dipilih dari himpunan hingga S1. Seringkali penyelesaian
masalah tesebut dikatakan scbagai usaha untuk mencari sebuah vektor yang optimal
(maksimum atau minimum) atau dengan kata lain sebuah vektor yang memuaskan bcrdasarkan
fungsi utama atau fungsi tujuannya P(x1, x2,..., xn). Sewaktu-waktu bisa saja terjadi bahwa
semua vektor dari himpunan penyelcsaian tersebut dapat merupakan sebagai solusi yang
optimal atau memuaskan fungsi tujuan P.

Backtracking itu seperti mencoba jalur yang berbeda, dan saat kita menemui jalan buntu, Kita
mundur ke pilihan terakhir dan mencoba rute yang berbeda. Dalam artikel ini, kita akan
membahas dasar-dasar Backtracking, cara kerjanya, dan bagaimana Backtracking dapat
membantu memecahkan berbagai macam masalah yang menantang. Backtracking itu seperti
metode untuk menemukan jalan yang benar melalui pilihan yang rumit.

Pengertian Backtracking

Backtracking adalah teknik algoritmik pemecahan masalah yang melibatkan pencarian solusi
secara bertahap dengan mencoba berbagai pilihan dan membatalkannya jika mengarah ke
jalan buntu. Teknik ini umumnya digunakan dalam situasi saat Kita perlu mengeksplorasi
berbagai kemungkinan untuk memecahkan masalah, seperti mencari jalan di labirin atau
memecahkan teka-teki seperti Sudoku. Saat jalan buntu tercapai, algoritme akan kembali ke
titik keputusan sebelumnya dan mengeksplorasi jalan yang berbeda hingga solusi ditemukan
atau semua kemungkinan telah habis.

Backtracking dapat didefinisikan sebagai teknik algoritmik umum yang mempertimbangkan

pencarian setiap kemungkinan kombinasi untuk memecahkan masalah komputasi.
Istilah Dasar

 Kandidat: Kandidat adalah pilihan atau elemen potensial yang dapat ditambahkan ke
solusi saat ini.
 Solusi: Solusinya adalah konfigurasi yang valid dan lengkap yang memenuhi semua
kendala masalah.
 Solusi Parsial: Solusi parsial adalah konfigurasi antara atau tidak lengkap yang
dibangun selama proses penelusuran kembali.
 Ruang Keputusan: Ruang keputusan adalah himpunan semua kandidat atau pilihan
yang mungkin pada setiap titik keputusan.
 Titik Keputusan: Titik keputusan adalah langkah spesifik dalam algoritma di mana
kandidat dipilih dan ditambahkan ke solusi parsial.
 Solusi yang Layak: Solusi yang layak adalah solusi parsial atau tuntas yang mematuhi
semua kendala.
 Jalan Buntu: Jalan buntu terjadi ketika solusi parsial tidak dapat diperluas tanpa
melanggar batasan.
 Mundur: Mundur melibatkan pembatalan keputusan sebelumnya dan kembali ke titik
keputusan sebelumnya.
 Ruang Pencarian: Ruang pencarian mencakup semua kemungkinan kombinasi
kandidat dan pilihan.
 Solusi Optimal: Dalam masalah optimasi, solusi optimal adalah solusi terbaik yang
mungkin.

Komponen Kunci dari Backtracking

Backtracking adalah teknik algoritmik yang kuat yang digunakan untuk secara sistematis
mencari solusi untuk masalah dengan beberapa kemungkinan pilihan dan kendala. Komponen
utamanya adalah:

 Ruang Keputusan: Ruang masalah direpresentasikan sebagai struktur seperti pohon di

mana setiap node sesuai dengan titik keputusan. Node ini memiliki cabang yang
mewakili pilihan atau opsi yang mungkin. Algoritma mengeksplorasi ruang keputusan
ini, secara bertahap membuat keputusan.
 Pilihan: Di setiap titik keputusan, algoritma membuat pilihan dari satu set pilihan
yang tersedia. Pilihan ini sangat penting untuk menemukan solusi yang valid atau
menentukan bahwa tidak ada.
  Kendala: Kendala adalah aturan atau kondisi yang harus dipatuhi oleh solusi. Selama
eksplorasi, algoritma memeriksa apakah pilihan saat ini memenuhi kendala ini. Jika
tidak, itu mundur.
 Rekursensi: Backtracking melibatkan rekurasi, karena algoritma mengeksplorasi
pilihan lebih lanjut dengan menyelami pohon pengambilan keputusan. Proses rekursif
ini memungkinkan untuk eksplorasi sistematis dari semua jalur yang mungkin.
 Memeriksa dan Validasi: Setelah membuat pilihan, algoritma memeriksa apakah itu
mengarah pada solusi yang valid dengan memverifikasi apakah keadaan saat ini
memenuhi persyaratan masalah. Jika pilihan itu valid, itu berlanjut ke titik keputusan
berikutnya. Jika tidak, itu mundur.
 Mekanisme Backtracking: Ketika jalur yang dipilih mengarah ke jalan buntu atau
melanggar batasan, algoritma mundur. Ini berarti membalikkan pilihan terakhir yang
dibuat, kembali ke titik keputusan sebelumnya, dan mengeksplorasi pilihan alternatif.
 Ketentuan Penghentian: Algoritma mengulangi proses membuat pilihan, memeriksa,
dan mundur sampai menemukan solusi yang valid yang memenuhi semua kendala
atau melelahkan semua pilihan yang mungkin tanpa hasil. Kondisi penghentian
menentukan kapan algoritma harus berhenti.
 Pemangkasan: Untuk meningkatkan efisiensi, teknik pemangkasan sering diterapkan.
Pemangkasan melibatkan deteksi dini jalur yang tidak valid dan menghindari
eksplorasi lebih lanjut di jalur tersebut, mengurangi upaya komputasi yang tidak
perlu.
 Optimalisasi: Tergantung pada masalah, teknik optimasi dapat diintegrasikan ke
dalam algoritma backtracking untuk menemukan solusi terbaik atau mengoptimalkan
fungsi objektif tertentu.
 Struktur Data: Algoritma backtracking dapat menggunakan struktur data untuk
melacak keadaan dan pilihan saat ini, memfasilitasi pemeriksaan yang efisien dan
operasi mundur. Struktur data umum termasuk tumpukan, array, atau panggilan fungsi
rekursif.
 Akumulasi Solusi: Dalam beberapa kasus, algoritma terakumulasi dan mencatat
pilihan yang dibuat untuk membangun solusi akhir. Hal ini sangat penting dalam
masalah di mana menemukan satu solusi yang valid tidak cukup.

Jenis-jenis Masalah Backtracking

Masalah yang terkait dengan backtracking dapat dikategorikan menjadi 3 kategori:

 Masalah Keputusan: Di sini, kita mencari solusi yang layak.
 Masalah Optimasi: Untuk jenis ini, kami mencari solusi terbaik.
 Masalah Enumerasi: menemukan semua kemungkinan solusi yang layak untuk
masalah jenis ini.

Cara kerja Backtracking

Seperti yang kita ketahui algoritma backtracking menelusuri setiap kemungkinan jalur untuk
menemukan solusi yang valid, penelusuran jalur ini dapat dengan mudah dipahami melalui
gambar yang diberikan:
Seperti yang ditunjukkan pada gambar,

 “ IS” mewakili Keadaan Awal di mana panggilan rekursi mulai menemukan solusi
yang valid.
 C: mewakili berbagai Titik Pemeriksaan untuk panggilan rekursif
 TN : melambangkan Node Terminal tempat pemanggilan rekursif tidak dapat
dilakukan lagi, node ini bertindak sebagai kasus dasar rekursi dan kita menentukan
apakah solusi saat ini valid atau tidak pada kondisi ini.

Di setiap Checkpoint, program membuat beberapa keputusan dan berpindah ke checkpoint lain
hingga mencapai Node terminal. Setelah menentukan apakah solusinya valid atau tidak,
program mulai kembali ke checkpoint dan mencoba menjelajahi jalur lain. Misalnya, pada
gambar di atas, TN1…TN5 adalah node terminal tempat solusinya tidak dapat diterima,
sementara TN6 adalah status tempat menemukan solusi yang valid.

Panah kembali pada gambar menunjukkan penelusuran kembali dalam tindakan, di mana kita
mengembalikan perubahan yang dibuat oleh beberapa titik pemeriksaan.

Proses backtracking dapat dipecah menjadi beberapa langkah utama:

1. Inisialisasi: Algoritma dimulai dengan keadaan awal atau solusi parsial, sering
direpresentasikan sebagai wadah kosong atau kanvas kosong, tergantung pada masalah.
Ini juga membentuk struktur data yang diperlukan untuk melacak pilihan dan kendala.
2. Eksplorasi: Pada setiap titik keputusan, algoritma membuat pilihan dari seperangkat
opsi yang tersedia. Pilihan ini dapat melibatkan memilih elemen dari daftar,
menempatkan objek di papan, atau keputusan apa pun yang relevan dengan masalah
tertentu.
3. Memeriksa: Setelah membuat pilihan, algoritma memeriksa apakah itu memenuhi
kendala dan kriteria masalah. Jika pilihan saat ini berlaku sejauh ini, algoritma berlanjut
ke langkah berikutnya. Jika tidak, itu mundur ke titik keputusan sebelumnya.
4. Rekurasi: Jika pilihan berlaku, algoritma rekursif mengeksplorasi pilihan lebih lanjut
dengan kembali ke langkah eksplorasi. Ini berarti bahwa ia menyelam lebih dalam ke
pohon keputusan untuk mengeksplorasi kemungkinan-kemungkinan baru.
 5. Backtracking: Jika, pada titik tertentu, algoritma menghadapi situasi di mana tidak ada
pilihan yang valid yang tersisa untuk mengeksplorasi atau menyadari bahwa jalan saat
ini tidak dapat mengarah pada solusi, itu mundur ke titik keputusan sebelumnya. Ini
melibatkan membatalkan pilihan terakhir yang dibuat dan menjelajahi jalur alternatif.
6. Penghentian: Algoritma mengulangi langkah 2 hingga 5 sampai menemukan solusi
yang valid yang memenuhi semua kendala atau menghabiskan semua pilihan yang
mungkin tanpa menemukan solusi. Dalam kasus terakhir, disimpulkan bahwa tidak ada
solusi untuk contoh masalah yang diberikan.

Secara teknis, untuk masalah backtracking:

o Algoritma ini membangun solusi dengan menjelajahi semua kemungkinan jalur yang
dibuat oleh pilihan dalam masalah, solusi ini dimulai dengan himpunan kosong S={}
o Tiap pilihan menciptakan sub-pohon baru ' s' yang kita tambahkan ke dalam set.
o Sekarang ada dua kasus:
 S+s adalah himpunan yang valid
 S+s bukan set yang valid
o Bila himpunan tersebut valid, maka kita membuat pilihan lebih lanjut dan mengulang
proses hingga solusi ditemukan, jika tidak, kita menarik kembali keputusan kita untuk
memasukkan ' s' dan mengeksplorasi jalur lain hingga solusi ditemukan atau semua jalur
yang mungkin telah habis.

Pseudocode untuk Backtracking

Cara terbaik untuk mengimplementasikan backtracking adalah melalui rekursi, dan semua
kode backtracking dapat diringkas sesuai dengan Pseudocode yang diberikan:

void FIND_SOLUTIONS(parameters):
if (valid solution):
store the solution
Return
for (all choice):
if (valid choice):
APPLY (choice)
FIND_SOLUTIONS (parameters)
BACKTRACK (remove choice)
Return

Analisis Kompleksitas Backtracking

Karena algoritma backtracking murni brute force, maka dalam hal kompleksitas waktu,
kinerjanya sangat buruk. Secara umum, backtracking dapat dilihat memiliki kompleksitas
waktu yang disebutkan di bawah ini:

 Eksponensial (O(K^N))
 Faktorial (O(N!))
Kompleksitas ini disebabkan oleh fakta bahwa di setiap keadaan kita mempunyai banyak
pilihan yang menyebabkan jumlah jalur meningkat dan sub-pohon berkembang pesat.

Perbedakan Backtracking dengan Rekursi

Rekursi dan Backtracking adalah konsep yang terkait dalam ilmu komputer dan
pemrograman, tetapi keduanya bukanlah hal yang sama. Mari kita bahas perbedaan utama di
antara keduanya:

Rekursi Melacak kembali

Backtracking selalu menggunakan rekursi
Rekursi tidak selalu memerlukan backtracking
untuk menyelesaikan masalah
Memecahkan masalah dengan berbagai
Memecahkan masalah dengan memecahnya
pilihan dan mengeksplorasi pilihan secara
menjadi submasalah yang lebih kecil dan
sistematis, menelusuri kembali bila
serupa, lalu menyelesaikannya secara rekursif.
diperlukan.
Dikendalikan oleh panggilan fungsi dan Dikelola secara eksplisit dengan loop dan
tumpukan panggilan. status.
Aplikasi Rekursi: Penelusuran Pohon dan Penerapan Backtracking: Masalah N
Grafik, Menara Hanoi, Algoritma Bagi dan Queen, Masalah Tikus dalam Labirin,
Taklukkan, Pengurutan Gabungan, Pengurutan Masalah Tur Ksatria, Pemecah Sudoku,
Cepat, dan Pencarian Biner. dan Masalah Pewarnaan Grafik.

Aplikasi Backtracking

 Membuat bot pintar untuk memainkan Permainan Papan seperti Catur.

 Memecahkan labirin dan teka-teki seperti masalah N-Queen.
 Perutean Jaringan dan Kontrol Kemacetan.
 Dekripsi
 Pembenaran Teks

Contoh kasus 1:
Permutasi dari String yang diberikan

Diberikan string S , tugasnya adalah menulis program untuk mencetak semua permutasi dari
string yang diberikan.

Permutasi yang juga disebut "angka susunan" atau "urutan," adalah penataan ulang elemen-
elemen dari daftar berurut S menjadi korespondensi satu-satu dengan S itu sendiri. Suatu string
dengan panjang N memiliki N! permutasi.

Contoh:

Masukan: S = “ABC”
Keluaran: “ABC”, “ACB”, “BAC”, “BCA”, “CBA”, “CAB”
Masukan: S = “XY”
Keluaran: “XY”, “YX”

Cetak permutasi dari string yang diberikan menggunakan backtracking :

Pohon Rekursi untuk permutasi string “ABC”

Ikuti langkah-langkah yang diberikan untuk menyelesaikan masalah:

 Buat fungsi permute() dengan parameter sebagai string input dan indeks awal string
 Panggil fungsi ini dengan nilai input string dan indeks awal, idx sebagai 0
o Dalam fungsi ini, jika idx menjadi ukuran string maka cetak string yang sama
 Atau jalankan for loop dari idx ke ukuran – 1 dan tukar elemen saat ini di for
loop dengan s[idx]
 Kemudian panggil lagi fungsi yang sama dengan menambah nilai idx sebesar
1
  Setelah itu tukar lagi nilai yang sudah ditukar sebelumnya untuk memulai
backtracking

Berikut ini adalah implementasi pendekatan di atas:

# Function to swap characters in a string

def swap(s, i, j):
s = list(s)
s[i], s[j] = s[j], s[i]
return ''.join(s)

# Function to print permutations of the string

def permuteRec(s, idx):
# Base case
if idx == len(s) - 1:
print(s)
return

for i in range(idx, len(s)):

# Swapping
s = swap(s, idx, i)

# First idx+1 characters fixed

permuteRec(s, idx + 1)

# Backtrack
s = swap(s, idx, i)

# Wrapper function
def permute(s):
permuteRec(s, 0)

# Driver code
s = "ABC"
permute(s)

Output
ABC
ACB
BAC
BCA
CBA
CAB

Analisis Kompleksitas

Kompleksitas Waktu: O(N * N!) Perhatikan bahwa ada N! permutasi dan dibutuhkan waktu
O(N) untuk mencetak permutasi.
Kompleksitas ruang : O(N)

Contoh kasus 2:
Masalah Jumlah Subset menggunakan Backtracking

Diberikan satu set[] bilangan bulat non-negatif dan suatu nilai sum , tugasnya adalah
mencetak bagian dari set yang diberikan yang jumlahnya sama dengan sum yang diberikan .

Contoh:
Input: set[] = {1,2,1}, sum = 3
Output: [1,2],[2,1]
Penjelasan: Ada subset [1,2],[2,1] dengan jumlah 3.

Input: set[] = {3, 34, 4, 12, 5, 18}, sum = 30

Output: [12,18] [18,12]
Penjelasan: ada subset [12,18] [18,12] yang jumlahnya mencapai 30.

Masalah Jumlah Subset menggunakan Backtracking

Jumlah subset juga dapat dianggap sebagai kasus khusus dari masalah Knapsack 0–1 . Untuk
setiap item, ada dua kemungkinan:
 Sertakan elemen saat ini dalam subset dan ulangi untuk elemen yang tersisa dengan Sum yang
tersisa .
 Kecualikan elemen saat ini dari subset dan lakukan pengulangan untuk elemen yang tersisa.
Terakhir, jika Sum menjadi 0 , cetak elemen dari subset saat ini. Kasus dasar rekursif
adalah ketika tidak ada item yang tersisa , atau jumlahnya menjadi negatif , lalu cukup
kembalikan.
Implementasi dalam Bahasa Python

# Print all subsets if there is at least one subset of set[]

# with a sum equal to the given sum
flag = False

def print_subset_sum(i, n, _set, target_sum, subset):

global flag
if target_sum == 0:
# Prints valid subset
flag = True
print("[", end=" ")
for element in subset:
print(element, end=" ")
print("]", end=" ")
return

if i == n:
return

print_subset_sum(i + 1, n, _set, target_sum, subset)

if _set[i] <= target_sum:

[Link](_set[i])
print_subset_sum(i + 1, n, _set, target_sum - _set[i], subset)
[Link]()

# Driver code
if __name__ == "__main__":
# Test case 1
set_1 = [1, 2, 1]
sum_1 = 3
n_1 = len(set_1)
subset_1 = []
print("Output 1:")
print_subset_sum(0, n_1, set_1, sum_1, subset_1)
print()
 flag = False

# Test case 2
set_2 = [3, 34, 4, 12, 5, 2]
sum_2 = 30
n_2 = len(set_2)
subset_2 = []
print("Output 2:")
print_subset_sum(0, n_2, set_2, sum_2, subset_2)
if not flag:
print("There is no such subset")

Output 1:
[21][12]
Output 2:
There is no such subset

Analisis kompleksitas:
 Kompleksitas Waktu: O(2 n ) Solusi di atas dapat mencoba semua subset dari
himpunan yang diberikan dalam kasus terburuk. Oleh karena itu kompleksitas waktu
dari solusi di atas bersifat eksponensial .
 Kompleksitas Ruang: O(n) di mana n adalah ruang tumpukan rekursi

Contoh kasus ke 3: Cetak semua subset dari Set atau Array yang diberikan

Diberikan array Arr [] dengan ukuran N, cetak semua subset dari array.

Subset: Bagian dari array adalah tuple yang dapat diperoleh dari array dengan menghapus
beberapa (mungkin semua) elemen tersebut

Contoh:
Masukan: N = 3, Arr = [1, 2, 3]
Keluaran: {}
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{2}
{2, 3}
{3}
Penjelasan: Ini semua adalah subset yang dapat dibentuk dari array yang diberikan, dapat
dibuktikan bahwa tidak ada subset lain selain output yang diberikan.

Masukan: N = 2, Arr = [2, 4]

Keluaran: {}
{2}
{2, 4}
{4}
Penjelasan: Ini semua adalah subset yang dapat dibentuk dari array yang diberikan, dapat
dibuktikan bahwa tidak ada subset lain selain output yang diberikan.

Berapa banyak Subset yang mungkin untuk berbagai ukuran 'N'?

Sebelum melompat ke dalam solusi, dapatkah kita mengamati semacam hubungan antara
ukuran array N dan jumlah subset yang dibentuk oleh array itu? Jawabannya adalah YA, ada
hubungan yang diberikan oleh rumus berikut:

Jumlah Subset dari array ukuran N = 2N2 N

Bukti: Untuk setiap elemen array kita memiliki 2 pilihan:

 Pilihan 1: Sertakan ke dalam subset.

 Pilihan 2: Keluarkan dari subset.

Karena, setiap elemen memiliki 2 pilihan untuk berkontribusi ke dalam subset dan kami
memiliki total elemen N, oleh karena itu total subset = 2N2 N

Mari kita lihat bagaimana kita bisa membangun solusi kita dari pengamatan ini.

Mencetak semua subset menggunakan Backtracking

Seperti disebutkan di atas, untuk setiap elemen ada dua pilihan, termasuk ke dalam subset
atau mengecualikan itu. Algoritma backtracking dapat memungkinkan kita untuk
mengeksplorasi semua pilihan yang mungkin satu per satu secara rekursif.

State Space Tree untuk mencetak semua subset menggunakan Backtracking:

Misalkan array ukuran 3 memiliki elemen {1, 2, 3}, pohon ruang negara dapat dibangun
seperti di bawah ini:
Ikuti langkah-langkah di bawah ini untuk menerapkan ide di atas:
 Ini dimulai dengan subset kosong dan menambahkannya ke daftar hasil.
 Ini iterasi melalui unsur-unsur vektor input:
o Termasuk elemen saat ini dalam subsetsubset.
o Secara rekursif memanggil dirinya sendiri dengan subset yang diperbarui dan
indeks berikutnya..
o Mengecualikan elemen saat ini dari subset (backtracks).

Di bawah ini adalah implementasi dari pendekatan di atas:

def calcSubset(A, res, subset, index):

# Add the current subset to the result list
[Link](subset[:])

# Generate subsets by recursively including and excluding elements

for i in range(index, len(A)):
# Include the current element in the subset
[Link](A[i])

# Recursively generate subsets with the current element included

calcSubset(A, res, subset, i + 1)

# Exclude the current element from the subset (backtracking)

[Link]()

def subsets(A):
subset = []
res = []
index = 0
calcSubset(A, res, subset, index)
return res

# Driver code
if __name__ == "__main__":
array = [1, 2, 3]
res = subsets(array)
 # Print the generated subsets
for subset in res:
print(*subset)

Output
1
1 2
1 2 3
1 3
2
2 3
3

Analisis Kompleksitas:

 Kompleksitas Waktu: O(N*2^N), di mana n adalah ukuran array yang diberikan.

 Kompleksitas Ruang : O(N * 2^N)
o O(N): jika kita hanya mencetak subset kita, akan ada di max N recursion stack
o O(2^N) : jika kita akan menyimpan semua subset kita akan membutuhkan 2^N
blok memori untuk menyimpan setiap subset