buat persentasi

Download Buat persentasi

Post on 15-Aug-2015

41 views

Category:

Education

2 download

Embed Size (px)

TRANSCRIPT

  1. 1. AAllggoorriittmmaa RRuunnuutt--bbaalliikk((BBaacckkttrraacckkiinngg))BBaaggiiaann 11
  2. 2. PPeennddaahhuulluuaann Runut-balik (backtracking) adalahalgoritma yang berbasis pada DFS untukmencari solusi persoalan secara lebihmangkus. Runut-balik, yang merupakan perbaikandari algoritma brute-force, secarasistematis mencari solusi persoalan diantara semua kemungkinan solusi yangada.
  3. 3. Dengan metode runut-balik, kita tidak perlumemeriksa semua kemungkinan solusi yangada. Hanya pencarian yang mengarah ke solusisaja yang selalu dipertimbangkan. Akibatnya,waktu pencarian dapat dihemat. Saat ini algoritma runut-balik banyak diterapkanuntuk program games (seperti permainan tic-tac-toe, menemukan jalan keluar dalam sebuahlabirin, catur, dll) dan masalah-masalah padabidang kecerdasan buatan (artificialintelligence).
  4. 4. PPrrooppeerrttii UUmmuumm MMeettooddeeRRuunnuutt--bbaalliikk1. Solusi persoalan. Solusi dinyatakan sebagai vektor dengann-tuple:X = (x1, x2, , xn), xi Si . Mungkin saja S1 = S2 = = Sn. Contoh: Si = {0, 1}, xi = 0 atau 1
  5. 5. 2. Fungsi pembangkit nilai xkDinyatakan sebagai:T(k)T(k) membangkitkan nilai untuk xk, yangmerupakan komponen vektor solusi.
  6. 6. 3. Fungsi pembatas (pada beberapa persoalanfungsi ini dinamakan fungsi kriteria) Dinyatakan sebagaiB(x1, x2, , xk) B bernilai true jika (x1, x2, , xk) mengarah kesolusi. Jika true, maka pembangkitan nilaiuntuk xk+1 dilanjutkan, tetapi jika false, maka (x1,x2, , xk) dibuang dan tidak dipertimbangkanlagi dalam pencarian solusi.
  7. 7. PPeennggoorrggaanniissaassiiaann SSoolluussii Semua kemungkinan solusi dari persoalandisebut ruang solusi (solution space). Jika xi Si, maka S1 S2 Sn disebutruang solusi. Jumlah anggota di dalam ruang solusiadalah | S1| | S2| | Sn |.
  8. 8. Tinjau Knapsack 0/1 untuk n = 3. Solusi persoalan dinyatakan sebagaivektor (x1, x2, x3) dengan xi {0,1}.Ruang solusinya adalah{0,1} {0,1} {0,1} = {(0, 0, 0), (0, 1, 0),(0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1),(0, 1, 1), (1, 1, 1)}.
  9. 9. Pada Knapsack 0/1 dengan n = 3 terdapat2n = 23 = 8 kemungkinan solusi, yaitu:(0, 0, 0), (0, 1, 0), (0, 0, 1),(1, 0, 0), (1, 1, 0), (1, 0, 1),(0, 1, 1), dan (1, 1, 1). Penyelesaian secara exhaustive searchadalah dengan menguji setiapkemungkinan solusi.
  10. 10. Ruang solusi diorganisasikan ke dalam strukturpohon. Tiap simpul pohon menyatakan status (state)persoalan, sedangkan sisi (cabang) dilabelidengan nilai-nilai xi. Lintasan dari akar ke daun menyatakan solusiyang mungkin. Seluruh lintasan dari akar ke daun membentukruang solusi. Pengorganisasian pohon ruangsolusi diacu sebagai pohon ruang status (statespace tree).
  11. 11. TTiinnjjaauu ppeerrssooaallaann KKnnaappssaacckk 11//00 uunnttuukk nn == 33..RRuuaanngg ssoolluussiinnyyaa::
  12. 12. Prinsip PPeennccaarriiaann SSoolluussii ddeennggaannMMeettooddee RRuunnuutt--bbaalliikk Solusi dicari dengan membentuk lintasandari akar ke daun. Aturan pembentukanyang dipakai adalah mengikuti aturanpencarian mendalam (DFS). Simpul-simpulyang sudah dilahirkan dinamakansimpul hidup (live node). Simpul hidupyang sedang diperluas dinamakansimpul-E (Expand-node).
  13. 13. Tiap kali simpul-E diperluas, lintasanyang dibangun olehnya bertambahpanjang. Jika lintasan yang sedangdibentuk tidak mengarah ke solusi, makasimpul-E tersebut dibunuh sehinggamenjadi simpul mati (dead node).Fungsi yang digunakan untukmembunuh simpul-E adalah denganmenerapkan fungsi pembatas(bounding function). Simpul yang sudahmati tidak akan pernah diperluas lagi.
  14. 14. Jika pembentukan lintasan berakhirdengan simpul mati, maka prosespencarian diteruskan denganmembangkitkan simpul anak yanglainnya. Bila tidak ada lagi simpul anakyang dapat dibangkitkan, makapencarian solusi dilanjutkan denganmelakukan runut-balik ke simpul hidupterdekat (simpul orangtua). Selanjutnyasimpul ini menjadi simpul-E yang baru.
  15. 15. Pencarian dihentikan bila kita telahmenemukan solusi atau tidak ada lagisimpul hidup untuk runut-balik.
  16. 16. Tinjau persoalan Knapsack 0/1 denganinstansiasi:n = 3(w1, w2, w3) = (35, 32, 25)(p1, p2, p3) = (40, 25, 50)M = 30 Solusi dinyatakan sebagai X = (x1, x2, x3), xi {0,1}. Fungsi pembatas:
  17. 17. PPoohhoonn ddiinnaammiiss yyaanngg ddiibbeennttuukk sseellaammaa ppeennccaarriiaannuunnttuukk ppeerrssooaallaann KKnnaappssaacckk 00//11 ddeennggaann nn == 33,,MM == 3300,, ww == ((3355,, 3322,, 2255)) ddaann pp == ((4400,, 2255,, 5500))12 91 0 1 31 4 1 5x 1 = 1 x 1 = 0x 2 = 1 x 2 = 0x 3 = 1 x 3 = 0BB
  18. 18. PPeennoommoorraann uullaanngg ssiimmppuull--ssiimmppuull sseessuuaaii uurruuttaannppeemmbbaannggkkiittaannnnyyaaSolusi optimumnya adalah X = (0, 0, 1) dan F = 50.
  19. 19. SSkkeemmaa UUmmuumm AAllggoorriittmmaa RRuunnuutt--BBaalliikk((vveerrssii rreekkuurrssiiff))procedure RunutBalikR(input k:integer){Mencari semua solusi persoalan dengan metode runut-balik; skemarekursifMasukan: k, yaitu indeks komponen vektor solusi, x[k]Keluaran: solusi x = (x[1], x[2], , x[n])}Algoritma:for tiap x[k] yang belum dicoba sedemikian sehingga( x[k]T(k)) and B(x[1], x[2], ... ,x[k])= true doif (x[1], x[2], ... ,x[k]) adalah lintasan dari akar ke daunthenCetakSolusi(x)endifRunutBalikR(k+1) { tentukan nilai untuk x[k+1]}endfor
  20. 20. SSkkeemmaa UUmmuumm AAllggoorriittmmaa RRuunnuutt--BBaalliikk((vveerrssii iitteerraattiiff))procedure RunutBalikI(input n:integer){Mencari semua solusi persoalan dengan metode runut-balik; skemaiteratif.Masukan: n, yaitu panjang vektor solusiKeluaran: solusi x = (x[1], x[2], , x[n])}Delarasi:k : integerAlgoritma:k1while k > 0 doif (x[k] belum dicoba sedemikian sehingga x[k]T(k)) and(B(x[1], x[2], ... ,x[k])= true)thenif (x[1],x[2],...,x[k]) adalah lintasan dari akar ke daunthenCetakSolusi(x)endifkk+1 {indeks anggota tupple berikutnya}else {x[1], x[2], , x[k] tidak mengarah ke simpul solusi }kk-1 {runut-balik ke anggota tupple sebelumnya}endifendwhile{ k = 0 }
  21. 21. Setiap simpul dalam pohon ruang statusberasosiasi dengan sebuah pemanggilanrekursif. Jika jumlah simpul dalam pohon ruang statusadalah 2n atau n!, maka untuk kasus terburuk,algoritma runut-balik membutuhkan waktu dalamO(p(n)2n) atau O(q(n)n!), dengan p(n) dan q(n)adalah polinom derajat n yang menyatakanwaktu komputasi setiap simpul.
  22. 22. PPeerrssooaallaann NN--RRaattuu((TThhee NN--QQuueeeennss PPrroobblleemm)) Diberikan sebuah papan catur yangberukuran N N dan delapan buah ratu.Bagaimanakah menempatkan N buah ratu(Q) itu pada petak-petak papan catursedemikian sehingga tidak ada dua ratuatau lebih yang terletak pada satu barisyang sama, atau pada satu kolom yangsama, atau pada satu diagonal yangsama?
  23. 23. CCoonnttoohh 22 bbuuaahh ssoolluussii 88--qquueeeenn pprroobblleemm::
  24. 24. Penyelesaian ddeennggaann AAllggoorriittmmaa BBrruuttee--FFoorrccee::a) Brute Force 1 Mencoba semua kemungkinan solusipenempatan delapan buah ratu padapetak-petak papan catur. Ada C(64, 8) = 4.426.165.368kemungkinan solusi.
  25. 25. b) Brute Force 2 Meletakkan masing-masing ratu hanyapada baris-baris yang berbeda. Untuksetiap baris, kita coba tempatkan ratumulai dari kolom 1, 2, , 8. Jumlah kemungkinan solusi yangdiperiksa berkurang menjadi88 = 16.777.216
  26. 26. c) Brute Force 3 (exhaustive search) Misalkan solusinya dinyatakan dalamvektor 8-tupple:X = (x1 , x2 , ... , x8) Vektor solusi merupakan permutasi daribilangan 1 sampai 8. Jumlah permutasi bilangan 1 sampai 8adalah P(1, 8)= 8! = 40.320 buah.
  27. 27. Penyelesaian dengan AAllggoorriittmmaa RRuunnuutt--bbaalliikk:: Algoritma runut-balik memperbaiki algoritmabrute force 3 (exhaustive search). Ruang solusinya adalah semua permutasi dariangka-angka 1, 2, 3, 4, 5, 6, 7, 8. Setiap permutasi dari 1, 2, 3, 4, 5, 6, 7, 8dinyatakan dengan lintasan dari akar daun. Sisi-sisipada pohon diberi label nilai xi.
  28. 28. Contoh: Pohon rruuaanngg--ssttaattuuss ppeerrssooaallaann 44--RRaattuu
  29. 29. CCoonnttoohh ssoolluussii rruunnuutt--bbaalliikk ppeerrssooaallaann 44--RRaattuu::
  30. 30. Pohon ruang ssttaattuuss ddiinnaammiiss ppeerrssooaallaann 44--RRaattuu yyaanngg ddiibbeennttuukk sseellaammaa ppeennccaarriiaann::
  31. 31. Algoritma Runut-bbaalliikk uunnttuukk PPeerrssooaallaann 88--RRaattuu(a) Versi iteratif Dua buah ratu terletak pada baris yang sama, berartii = k Dua buah ratu terletak pada kolom yang sama, berartij=l Dua buah ratu terletak pada diagonal yang sama,berarti i-j=k-l atau i+j=k+l i-k=j-l atau k-i=j-l j-l= i-k1 2 3 4 5 6 7 812345678
  32. 32. procedure N_RATU_I(input N:integer){ Mencetak semua solusi penempatan N buah ratu padapetak papan catur N x N tanpa melanggar kendala; versi iteratifMasukan: N = jumlah ratuKeluaran: semua solusi x = (x[1], x[2], , x[N]) dicetak kelayar.}Deklarasik : integerAlgoritma:k1 {mulai pada baris catur ke-1}x[1]0 {inisialisasi kolom dengan 0}while k > 0 dox[k]x[k]+1 {pindahkan ratu ke kolom berikutnya}while (x[k] N) and (not TEMPAT(k)) do{periksa apakah ratu dapat ditempatkan pada kolom x[k]}x[k]:=x[k] + 1endwhile{x[k] > n or TEMPAT(k) }if x[k] n then { kolom penempatan ratu ditemukan }if k=N then { apakah solusi sudah lengkap?}CetakSolusi(x,N) { cetak solosi}elsekk+1 {pergi ke baris berikutnya}x[k]0 {inisialisasi kolom dengan 0}endifelsekk-1 { runut-balik ke baris sebelumnya}endifendwhile{ k = 0 }
  33. 33. function TEMPAT(input k:integer)boolean{true jika ratu dapat ditempatkan pada kolom x[k], false jika tidak}Deklarasii : integerstop : booleanAlgoritma:kedudukantrue { asumsikan ratu dapat ditempatkan pada kolomx[k] }{ periksa apakah memang ratu dapat ditempatkan pada kolom x[k] }i1 { mulai dari baris pertama}stopfalsewhile (i