Teknik Backtracking dan SUMOFSUB

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).