Program Backtracking

LOGIKA PROGRAM BACKTRACKING

1. Secara iteratif

 

 

Logika program :

·         PROCEDURE BACKTRACK(n)

Digunakan untuk mendeklarasikan prosedur dengan nama Backtrack sebanyak (n). Dimana n itu merupakan panjang vektor solusi. Prosedur ini dibuat untuk hal-hal yang sering dilakukan berulang-ulang, Cukup dituliskan sekali saja dalam prosedur dan dapat dipanggil atau dipergunakan sewaktu-waktu bila diperlukan.

·         INTEGER k,n; LOCAL x(1:n)

Digunakan untuk mendeklarasikan variable k dan n dengan tipe data integer. Lalu mendefinisikan matrix x(1:n) dimana n itu merupakan panjang vector yang kita inputkan.

·         k ← 1

Variable K yang bernilai 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))  THEN

PRINT (x(1), … , x(k)) ENDIF

Disini perulangan akan dimulai ketika k > 0 maka ia akan berulang ke program selanjutnya. Dimana jika x(k) maka apabila T(x) dan B(x) bagian dari variable k = TRUE.

T(k) merupakan fungsi pembangkit nilai x(k) yang merupakan komponen vector solusi. Dan Bk(x(1)) merupakan fungsi pembatas yang menentukan apakah (x(1),x(2),….x(k) mengarah ke solusi. Lalu akan dipertanyakan kembali, apakah IF x(1)….. x(k) kondisi ini digunakan untuk mencari penyelesaian dari solusi nilai variable k dan perulangan yang ini  akan tercetak sebagai lintasan dari akar ke daunnya. Solusi dinyatakan sebagai vector n – tuple. Kemudian jika kondisi terpenuhi maka akan tercetak x(1),x(2), hingga ke - x(n).

·         k ← k + 1

ELSE

k ← k – 1

ENDIF

REPEAT

END BACKTRACK

Setelah diseleksi apakah Bk(x(1),x(2),….x(k)) mengarah kesolusi atau tidak. Jika ya, maka pembangkit nilai untuk k+1 akan dilanjutkan. Jika tidak maka (x(1),x(2),…x(k)) akan dibuang dan tidak dipertimbangkan lagi. Kemudian program akan melanjutkan langkah – langkah diatas hingga nilai n yang kita inputkan terpenuhi.

2. Secara rekursif

Logika program :

·         PROCEDURE RBACKTRACK(k)

GLOBAL n, x(1:n)

Digunakan untuk mendeklarasikan prosedur dengan nama RBACKTRACK sebanyak (k) dengan tujuan mencari semua solusi persoalan dengan metode runut-balik; skema rekursif. Dan variable k, yaitu indeks komponen vektor solusi, x[k]

·         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)) THEN

PRINT (x(1), … , x(k))

ENDIF

T(k) merupakan fungsi pembangkit nilai x(k) yang merupakan komponen vector solusi. Dan Bk(x(1)) merupakan fungsi pembatas yang menentukan apakah (x(1),x(2),….x(k) mengarah ke solusi. Lalu akan dipertanyakan kembali, apakah IF x(1)….. x(k) kondisi ini digunakan untuk mencari penyelesaian dari solusi nilai variable k dan perulangan yang ini  akan tercetak sebagai lintasan dari akar ke daunnya. Solusi dinyatakan sebagai vector n – tuple. Apabila setiap x bernilai k yang kita input, maka perulangan akan berlangsung jika perbandingan antara 2 kondisi tersebut bernilai benar (True). Lalu akan tercetak solusi yang terpenuhi dan akhiri penyeleksian dengan EndIf.

·         CALL RBACKTRACK(k + 1)

END RBACKTRACK

Lalu program akan memanggil fungsi rbacktracknya dengan kondisi (k+1) dimana program akan melanjutkan karena dianggap kondisi telah mengarah ke solusi. Lalu jika nilai terpenuhi, program akan menghentikan fungsi rbacktracknya.

3. Secara Sumofsub

 

 

Logika program :

·         PROCEDURE SUMOFSUB(s,k,r)

Digunakan untuk mendefinisikan procedure dengan nama SUMOFSUB yang digunakan untuk menyelesaikan permasalahan secara sumofsub dengan metode backtrack.

·         GLOBAL INTEGER M,n

Digunakan untuk mendeklarasikan variable M dan n dengan tipe data integer.

·         GLOBAL REAL W(1:n)

Digunakan untuk mendefinisikan index W(1:n) yang bertipe data real.

·         GLOBAL BOOLEAN X(1:n)

Digunakan untuk mendefinisikan index X(1:n) dengan tipe data Boolean.

·         REAL r,s; INTEGER k,j

Untuk mendeklarasikan variable r dan s dengan tipe data real serta variable k dan j dengan tipe data integer.

·         X(k) = 1

Merupakan index X sebanyak k yang bernilai 1.

·         IF s + W(k) = M THEN PRINT (X(j), j ← 1 TO k) ELSE

Jika nilai variable s dijumlahkan dengan index w(k) berinilai sama dengan M maka termasuk dalam himpunan bagian j (subsets) .

·         IF s + W(k) + W(k+1) ≤ M THENCALL SUMOFSUB(s+W(k), k+1, r-W(k))

ENDIF

ENDIF

Jika tidak maka, program akan menghitung penjumlahan antara variable s+w(k)+w(k+1) jika hasilnya lebih kecil dari nilai m maka program akan memanggil fungsi Sumofsub dengan penjumlahan (s+W(k), k+1, r-W(k)). Kemudian Endif digunakan untuk menghentikan penyeleksian.

·         IF s + r - W(k) ≥ M AND s + W(k) ≤ M THEN X(k) 0

Lalu akan ada kondisi dimana apabila penjumlahan s+r-w(k) lebih besar dari m dan s+w(k) lebih kecil dari m, maka kondisi tersebut akan mengarah ke arah solusi. Dan index X(k) akan tercetak.

·         CALL SUMOFSUB(s, k+1, r-W(k))

Digunakan untuk membuat fungsi sumofsub, yang akan digunakan apabila diperlukan sewaktu – waktu tanpa harus menuliskan program secara keseluruhan, hanya perlu memanggil nama fungsinya saja.

·         ENDIF

END SUMOFSUB

Digunakan untuk mengakhiri penyeleksian. Sedangkan end sumofsub digunakan untuk mengakhiri program.