Materi Algoritma Backtracking ( Runut Balik ) by Rinaldi Munir

Materi Algoritma Backtracking ( Runut Balik ) by Rinaldi Munir



Hallo Sobat coding, pada kesempatan kali ini, brainedukasi akan memberikan informasi pembelajaran mengenai algoritma runut balik atau backtracking,  dari sumber nya Rinaldi Munir

Algoritma Runut Balik ( Backtracking )

Merupakan algoritma yang berbasis pada DFS digunakan untuk memecahkan masalah secara lebih mungkus, dari pada menggunakan brute force,.. Algoritma runut balik pertama kali diperkenalkan oleh D.H Lehmer pada tahun 1950,  algoritma ini biasanya digunakan juga dalam kecerdasan buatan dan game. seperti catur dan sodoku.

Algoritma Runut Balik bersifat DFS (Depth First Search) sehingga aturan pencariannya akan mengikut kepada aturan pencarian DFS yaitu dengan mencari solusi dari akar ke daun. ( dalam pohon ruang fungsi ) dengan pencarian mendalam, 

Properti Umum metode Backtracking ( Runut Balik ) 
Properti umum dijelaskan sebagai berikut (Munir, 2006)

1.  Solusi persoalan
     Solusi dinyatakan sebagai vektor dengan n-tuple

     X = (x1,x2,........xn), xi E Si ( xi anggota himpunan berhingga Si)
     Mungkin saja S1 = S2 = ....Sn
     Sebagai contoh Si = { 2,5 },xi=2, atau 5

2.  Fungsi pembangkit nilai Xk
     dinyatakan sebagai T(k), T(k) membangkitkan nilai untuk Xk yang merupakan vektor solusi.

3.  Fungsi Pembatas (Fungsi Kriteria)
     dinyatakan sebagai  B(x1,x2....... xk)
     Fungsi pembatas (B) bernilai true jika (x1,x2,.........x3) mengarah ke solusi .
     Jika true , maka pembangkitan nilai untuk xk+1 dilanjutkan , tetapi jika false maka (x1,x2,........xk)
     dibuang dan tidak dipertimbangkan lagi.

Prinsip pencarian solusi dengan metode Backtracking (runut balik)
langkah - langkah pencarian solusi sebagai berikut (Munit, 2006)


  1. Pengorganisasian solusi diimplementasikan kedalam sebuah vektor struktur pohon, Solusi dicari  dengen membentuk lintasan dari akar ke daun dengan menggunakan DFS
  2.  Simpul -  simpul yang sudah dibuat dinamakan simpul hidup (live node)
  3.  Simpul yang sedang diperluas dinamakan simpul-E (Expand simpul)
  4. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi maka simpul-E tersebut "dibunuh"   sehingga menjadi simpul mati (dead node)
  5. Fungsi yang digunakan untuk membunuh simpul-E adalah dengan menerapkan fungsi pembatas ( Bounding Function )
  6.   Simpul yang sudah mati tidak akan diperluas lagi
  7. Bila tidak ada lagi simpul anak yang dapat dibangkitkan maka pencarian solusi dilanjutkan dengan melakukan runut balik (backtrack) ke simpul terdekat
  8. Pencarian dihentikan bila kita telah menemukan solusi atau tidak ada lagi simpul hidup untuk runut balik

Skema Umum Algoritma Runut Balik ( Rekursif )

Skema Umum Algoritma Runut Balik ( Iteraktif )


LihatTutupKomentar