Kamis, 17 Januari 2013

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

2 komentar:

  1. kita juga punya nih jurnal mengenai Algoritma Backtracking silahkan dikunjungi dan dibaca , berikut linknya
    http://repository.gunadarma.ac.id/bitstream/123456789/2747/1/21-PENYELESAIAN%20MASALAH%20N-QUEEN%20DENGAN%20TEKNIK%20BACKTRACKING.pdf

    BalasHapus