Buat persentasi

Download Buat persentasi

Post on 15-Aug-2015

37 views

Category:

Education

2 download

Embed Size (px)

TRANSCRIPT

<ol><li> 1. AAllggoorriittmmaa RRuunnuutt--bbaalliikk((BBaacckkttrraacckkiinngg))BBaaggiiaann 11 </li><li> 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. </li><li> 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). </li><li> 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 </li><li> 5. 2. Fungsi pembangkit nilai xkDinyatakan sebagai:T(k)T(k) membangkitkan nilai untuk xk, yangmerupakan komponen vektor solusi. </li><li> 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. </li><li> 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 |. </li><li> 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)}. </li><li> 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. </li><li> 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). </li><li> 11. TTiinnjjaauu ppeerrssooaallaann KKnnaappssaacckk 11//00 uunnttuukk nn == 33..RRuuaanngg ssoolluussiinnyyaa:: </li><li> 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). </li><li> 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. </li><li> 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. </li><li> 15. Pencarian dihentikan bila kita telahmenemukan solusi atau tidak ada lagisimpul hidup untuk runut-balik. </li><li> 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: </li><li> 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 </li><li> 18. PPeennoommoorraann uullaanngg ssiimmppuull--ssiimmppuull sseessuuaaii uurruuttaannppeemmbbaannggkkiittaannnnyyaaSolusi optimumnya adalah X = (0, 0, 1) dan F = 50. </li><li> 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 </li><li> 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 &gt; 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 } </li><li> 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. </li><li> 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? </li><li> 23. CCoonnttoohh 22 bbuuaahh ssoolluussii 88--qquueeeenn pprroobblleemm:: </li><li> 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. </li><li> 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 </li><li> 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. </li><li> 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. </li><li> 28. Contoh: Pohon rruuaanngg--ssttaattuuss ppeerrssooaallaann 44--RRaattuu </li><li> 29. CCoonnttoohh ssoolluussii rruunnuutt--bbaalliikk ppeerrssooaallaann 44--RRaattuu:: </li><li> 30. Pohon ruang ssttaattuuss ddiinnaammiiss ppeerrssooaallaann 44--RRaattuu yyaanngg ddiibbeennttuukk sseellaammaa ppeennccaarriiaann:: </li><li> 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 </li><li> 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 &gt; 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] &gt; 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 } </li><li> 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</li></ol>