Pengertian, Properti, Pengorganisasian Solusi Backtracking Algorithm (Algoritma runut-balik)

Photo by Alex Knight on Unsplash - 

Pendahuluan

Runut-balik (Backtracking) adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara lebih mangkus.

Runut-balik, yang merupakan perbaikan dari algoritma Brute-Force, secara sistematis mencari solusi persoalan diantara semua kemungkinan solusi yang ada.

Dengan metode runut-balik, kita tidak perlu memeriksa semua kemungkinan solusi yang ada.

Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat.

Saat ini algoritma runut-balik banyak diterapkan untuk program games (seperti permainan tic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur, dll).

Dan masalah-masalah pada bidang kecerdasan buatan (Artificial Intelligence).

Properti Umum Metode Runut-balik

1. Solusi persoalan.

Solusi dinyatakan sebagai vektor dengan n-tuple :

• X = (X1, X2, …, Xn),  Xi ∈ Si . 

Mungkin saja S1 = S2 = … = Sn. 

Contoh: Si = {0, 1},  Xi = 0 atau 1

2. Fungsi pembangkit nilai xk

Dinyatakan sebagai : T(k) 

• T(k) membangkitkan nilai untuk XK, yang merupakan komponen vektor solusi.

3. Fungsi pembatas (pada beberapa persoalan fungsi ini dinamakan fungsi kriteria)

• Dinyatakan sebagai B (X1, X2, ..., XK)

• B bernilai True jika (X1, X2, ..., XK) mengarah ke solusi. Jika true, maka pembangkitan nilai untuk XK+1 dilanjutkan, tetapi jika false, maka (X1, X2, ..., XK) dibuang dan tidak dipertimbangkan lagi dalam pencarian solusi.

Pengorganisasian Solusi

• Semua kemungkinan solusi dari persoalan disebut ruang solusi (solution space).

• Jika Xi ∈ Si, maka  S1 × S2 × ... × Sn disebut ruang solusi. Jumlah anggota di dalam ruang solusi adalah | S1| ∙ | S2| ∙ ... ∙ | Sn |.

• Tinjau knapsack 0/1 untuk N = 3.

• Solusi persoalan dinyatakan sebagai vektor (X1, X2, X3) dengan Xi ∈ {0,1}.

• Ruang solusinya adalah {0,1} × {0,1} × {0,1} = {(0, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1)}

• Pada knapsack 0/1 dengan N = 3 terdapat 2n = 23 = 8 kemungkinan solusi, yaitu :

  (0, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1), dan (1, 1, 1). 

• Penyelesaian secara exhaustive search adalah dengan menguji setiap kemungkinan solusi.

• Ruang solusi diorganisasikan ke dalam struktur pohon.

• Tiap simpul pohon menyatakan status (state) persoalan, sedangkan sisi (cabang) dilabeli dengan nilai-nilai xi.

• Lintasan dari akar ke daun menyatakan solusi yang mungkin.

• Seluruh lintasan dari akar ke daun membentuk ruang solusi. Pengorganisasian pohon ruang solusi diacu sebagai pohon ruang status (state space tree).

Tinjau persoalan knapsack 1/0 untuk N = 3. Ruang solusinya : 

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Prinsip Pencarian Solusi dengan Metode Runut-balik

• Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan pembentukan yang dipakai adalah mengikuti aturan pencarian mendalam (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul-e (expand-node).

• Tiap kali simpul-e diperluas, lintasan yang dibangun olehnya bertambah panjang. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi, maka simpul-e tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Fungsi yang digunakan untuk membunuh simpul-e adalah dengan menerapkan fungsi pembatas (bounding function). Simpul yang sudah mati tidak akan pernah diperluas lagi.

• Jika pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian  diteruskan dengan membangkitkan simpul anak yang lainnya. Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan runut-balik ke simpul hidup terdekat (simpul orangtua). Selanjutnya simpul ini menjadi simpul-e yang baru.

• Pencarian dihentikan bila kita telah menemukan solusi atau tidak ada lagi simpul hidup untuk runut-balik.

• Tinjau persoalan knapsack 0/1 dengan instansiasi:

N = 3

(W1, W2, W3) = (35, 32, 25)

(P1, P2, P3) = (40, 25, 50)

M = 30

• Solusi dinyatakan sebagai X = (X1, X2, X3), Xi = {0, 1}. 

• Fungsi pembatas :

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

• Pohon dinamis yang dibentuk selama pencarian untuk persoalan knapsack 0/1 dengan N = 3, M = 30, W = (35, 32, 25) Dan P = (40, 25, 50)

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Penomoran ulang simpul-simpul sesuai urutan pembangkitannya.

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Solusi optimumnya adalah X = (0, 0, 1) dan F =  50.

Skema Umum Algoritma Runut-Balik (versi rekursif)

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Skema Umum Algoritma Runut-Balik (versi iteratif)

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Setiap simpul dalam pohon ruang status berasosiasi dengan sebuah pemanggilan rekursif. Jika jumlah simpul dalam pohon ruang status adalah 2n atau n!.

Maka untuk kasus terburuk, algoritma runut-balik membutuhkan waktu dalam o(p(n)2n) atau o(q(n)n!), dengan p(n) dan q(n) adalah polinom derajat n yang menyatakan waktu komputasi setiap simpul.

Mencari jalan keluar di dalam labirin (Maze Problem). 

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Penyelesaian dengan bactracking:

Bagi lintasan menjadi sederetan langkah. Sebuah langkah terdiri dari pergerakan satu unit sel pada arah tertentu. Arah yang mungkin: Ke atas (up), ke bawah (down), ke kiri (left), ke kanan (right).

Garis besar algoritma runut-baliknya:

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Bagaimana mengetahui langkah yang mana yang perlu dijejaki kembali ?

Ada 2 Solusi Untuk Masalah Ini :

• Pertama, simpan semua langkah yang pernah dilakukan, atau

• Kedua, gunakan rekursi (yang secara implisit menyimpan semua langkah). Rekursi adalah solusi yang lebih mudah.

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Contoh runut-balik pada sebuah labirin. Runut-balik diperlihatkan dengan garis putus-putus.

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

 Kesimpulan

(Maav, gambar ini telah terhapus. Silahkan anda cari di Google Image)

Baca Juga :

Artikel Terkait