Teknik Backtrakcing
Teknik Backtracking merupakan salah satu teknik dalam penyelesaian
masalah secara umum (General Problem Solving). Adapun dasar dari teknik ini
adalah suatu teknik pencarian (Teknik Searching). Teknik pencarian ini
digunakan dalam rangka mendapatkan himpunan penyelesaian yang mungkin. Dari
himpunan penyelesaian yang mungkin ini akan diperoleh solusi optimal atau
memuaskan.
Teknik Backtracking ini diperkenalkan pertama kali oleh : D.H.
Lehmer (1950), Penulisan algoritmanya oleh: R.J. Walker (1960), dan Variasi
aplikasinya dikembangkan oleh : Golomb & Baumert (1960).
Berikut ini disajikan algoritma backtracking secara umum, yang
menggunakan teknik iteratif :
PROCEDURE BACKTRACK(n)
INTEGER k,n; LOCAL x(1:n)
k ← 1
WHILE k > 0 DO
IF ada x(k) yang belum dicoba sedemikian
sehingga
x(k) ∈ T(x(1), … , x(k-1)) AND Bk(x(1), … ,
x(k)) = TRUE
THEN
IF (x(1), … , x(k)) adalah sebuah jalur (path) yang merupakan
solusi
THEN PRINT (x(1), … , x(k)) ENDIF
k ← k + 1
ELSE k ← k – 1
ENDIF
REPEAT
END BACKTRACK
Sedangkan bentuk rekursifnya adalah sebagai berikut :
PROCEDURE RBACKTRACK(k)
GLOBAL n,
x(1:n)
FOR setiap
x(k) sedemikian sehingga
x(k) ∈ T(x(1), … , x(k-1)) AND Bk(x(1), … ,
x(k)) = TRUE
IF (x(1), … , x(k)) adalah sebuah jalur
(path) yang merupakan solusi
THEN PRINT (x(1), … , x(k)) ENDIF
CALL RBACKTRACK(k + 1)
END RBACKTRACK
Contoh Pemakaian Teknik Backtracking :
The 8 - Queens Problem
The 4 - Queens Problem
Sum of Subsets
Graph Coloring
Hamilton Cycles
Knapsack Problem
Tic - Tac - Toe Game
The Travelling Salesman Problem
SUM OF SUBSETS
Masalah utama dari Sum of Subsets adalah
jika terdapat n bilangan real dan ingin dihitung semua kombinasi yang mungkin
dari himpunan bilangan tersebut. Kombinasi yang diinginkan yaitu kombinasi yang
jumlah seluruh elemennya sama dengan M (tertentu).
Sebelum kita selesaikan masalah tersebut dengan menggunakan teknik
backtracking, perhatikan terlebih dahulu penyajian permasalahan dan
penyelesaiannya dalam bentuk pohon.
Misalkan
banyaknya bilangan real tersebut adalah 4 (n=4). Terdapat 2 jenis pohon
pencarian, yakni Breadth First Search (BFS) yang menggunakan queue dan Depth
First Search (DFS) yang menggunakan stack. Berikut penggambaran kedua jenis
pohon tersebut.
Kedua bentuk penyajian pohon dari
persoalan sum of subsets, merupakan tahapan pertama dalam proses mendapatkan
solusi sesungguhnya (solusi optimal). Untuk mendapatkan solusi yang optimal
dari ruang penyelesaian digunakan suatu algoritma lain. Algoritma tersebut
menggunakan teknik backtracking, yang selanjutnya disebut dengan algoritma
SUMOFSUB.
PROCEDURE SUMOFSUB(s,k,r)
GLOBAL INTEGER M,n
GLOBAL REAL W(1:n)
GLOBAL BOOLEAN X(1:n)
REAL r,s; INTEGER k,j
X(k) = 1
IF s + W(k) = M THEN PRINT (X(j), j ← 1 TO k)
ELSE
IF s + W(k) + W(k+1) ≤ M THEN
CALL SUMOFSUB(s+W(k), k+1, r-W(k))
ENDIF
ENDIF
IF s + r - W(k) ≥ M AND s + W(k) ≤ M THEN
X(k) 0
CALL SUMOFSUB(s, k+1, r-W(k))
ENDIF
END SUMOFSUB
Contoh :
Suatu
himpunan terdiri dari 6 bilangan, yakni {5, 10, 12, 13, 15, 18} yang disusun
secara tidak turun. Akan ditentukan himpunan-himpunan bagiannya, yang jumlah
seluruh elemennya adalah 30.
Perhatikan
simpul A, B dan C yang merupakan outputnya dalam bentuk tuple (1,1,0,0,1),
(1,0,1,1) dan (0,0,1,0,0,1).
.jpg)
