Divide and Conquer [PDF]

Citation preview

Kartika Dwi Hapsari 1 Desain dan Analisa Algoritma – Divide and Conquer



Divide and Conquer A. Pengertian Merupakan teknik umum desai algoritma yang paling terkenal. Varian dari beberapa strategi pemrograman topdown, tetapi keistimewaannya adalah membuat sub-sub problem dari problem yang besar, oleh karena itu strategi ini ditunjukkan secara berulang-ulang (recursively), di dalam menerapkan algoritma yang sama dalam sub-sub problem seperti yang diterapkan pada masalah aslinya (original problem). Divide : Membagi masalah menjadi beberapa submasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya tiap submasalah berukuran hampir sama). Conquer : Memecahkan (menyelesaikan) masing-masing submasalah (secara rekursif). Combine: mengabungkan solusi masing-masing submasalah sehingga membentuk solusi masalah semula.



masalah



berukuran n



submasalah 1 ; berukuran n/2



submasalah 2 ; berukuran n/2



solusi submasalah 1



solusi submasalah 2



1



solusi masalah sebenarnya Kartika Dwi Hapsari | 105060809111003



Kartika Dwi Hapsari 2 Desain dan Analisa Algoritma – Divide and Conquer



Langkah kerja Divide and Conquer : 1. Sebuah permasalahan dibagi menjadi beberapa bagian yang lebih sederhana dari permasalahan yang sama, idealnya dengan ukuran yang sama. 2. Bagian yang lebih sederhana diselesaikan (biasanya secara rekursif) 3. Jika diperlukan solusi yang didapat dari bagian yang lebih sederhana digabungkan untuk mendapatkan penyelesaian untuk masalah yang sebenarnya. Objek masalah yang dibagi adalah masukan (input) atau instances yang berukuran n : tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap submasalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif (perulangan biasa), karena pada prinsipnya iteratif hampir sama dengan rekursif. Selain dibutuhkan sebuah “kondisi”, juga diperlukan “fase divide” untuk membagi/memecah problem menjadi sub-sub problem yang lebih kecil, dan “fase combine“ untuk menggabungkan kembali solusi dari sub-sub problem ke dalam solusi dari problem awalnya. Psodecode : function d and c (p) if basecase (p) then return solve (p) else (p1, : : :, pn) = divide (p) return combine (d and c (p1), : : :, d and c (pn)) endif 2



Kartika Dwi Hapsari | 105060809111003



Kartika Dwi Hapsari 3 Desain dan Analisa Algoritma – Divide and Conquer



Hal-hal yang penting pada Divide and Conquer : 1. Branching Factor Branching factor dalam algoritma divide and conquer adalah jumlah dari subproblem yang akan dibagi dari sebuah problem awal. Ini adalah langkah nyata dari algoritma divide and conquer, didalam proses pembagian yang sebenarnya, jumlah dari branching factor harus 2 atau lebih, karena jika tidak problem tidak bisa dibagi. Banyak jenis algoritma ini termasuk pula algoritma komputasi geometric yang memiliki branching factor berjumlah 2. 2. Balance Sebuah algoritma divide and conquer dikatakan balance jika problem awal dibagi menjadi sub-sub problem dengan ukuran yang sama. Yang artinya jumlah dari keseluruhan ukuran subproblem sama dengan ukuran problem awal (initial problem). Algoritma Mergesort dan binary tree, dan sama halnya dengan algoritma reduksi & prefix sum adalah beberapa contoh algoritma divide and conquer yang seimbang (balance). 3. Data Dependence of Divide Function Algoritma divide and conquer memiliki sebuah fungsi pembagian terhadap data yang memiliki ketergantungan, artinya jika ukuran relatif dari sebuah subproblem tergantung pada proses input datanya. Ini adalah salah satu ciri dari algoritma yang tidak seimbang, salah satu contohnya adalah algoritma quicksort yang akan membagi subproblem dengan fungsi data-dependent divide. 4. Control Parallelism or Sequentiality Algoritma divide and conquer dikatakan berurutan (sequential) jika subproblem dieksekusi sesuai dengan perintah program. Paralelisasi dari algoritma divide and conquer yang terurut pertama kali didefinisikan oleh Mou’s Divacon[Mou90], yang terjadi ketika hasil dari salah satu subeksekusi diperlukan oleh subeksekusi yang lain. Dalam kasus ini hasil 3



dari subtree pertama diberikan (passing) kepada proses komputasi subtree kedua, supaya hasil akhir tersebut bisa digunakan sebagai nilai awalnya,



Kartika Dwi Hapsari | 105060809111003



Kartika Dwi Hapsari 4 Desain dan Analisa Algoritma – Divide and Conquer



tetapi sekarang ini contoh diatas tidak dapat dijadikan ilustrasi lagi karena teknologi komputer paralel yang semakin canggih dan kompleks. Rekursi Divide and Conquer Machiavelli menggunakan sintaks : Split (result1 = func (arg1), result2 = func (arg2) [, resultn = func (argn)]) Untuk membentuk fungsi call dalam algoritma divide and conquer. Varn adalah hasil akhir yang kembali ke fungsi func dalam argument argn. Machiavelli membuat versi fungsi yang salah satunya mengaplikasikan reduksi menjadi sebuah “pengulangan sederhana” . Contoh : void fetch_vec_int_serial (vec_int src, vec_int indices, vec_int dst) { int i, nelt = dst.nelt_here; for (i = 0; i < nelt; i++) { dst[i] = src[indices[i]] } }



B. Contoh Algoritma Skema umum : procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C. Masukan: masukan yang berukuran n Keluaran: solusi dari masalah semula } Deklarasi r, k : integer Algoritma



4



if n  n0 then



{ukuran masalah sudah cukup kecil }



SOLVE upa-masalah yang berukuran n ini else



Kartika Dwi Hapsari | 105060809111003



Kartika Dwi Hapsari 5 Desain dan Analisa Algoritma – Divide and Conquer Bagi menjadi r upa-masalah, masing-masing berukuran n/k for masing-masing dari r upa-masalah do DIVIDE_and_CONQUER(n/k) endfor COMBINE solusi dari r upa-masalah menjadi solusi masalah semula } endif



Jika pembagian selalu menghasilkan dua submasalah yang berukuran sama : procedure DIVIDE_and_CONQUER(input n : integer) { Menyelesaikan masalah dengan algoritma D-and-C. Masukan: masukan yang berukuran n Keluaran: solusi dari masalah semula } Deklarasi r, k : integer Algoritma if n  n0 then {ukuran masalah sudah cukup kecil } SOLVE upa-masalah yang berukuran n ini else Bagi menjadi 2 upa-masalah, masing-masing berukuran n/2 DIVIDE_and_CONQUER(upa-masalah



pertama



yang



berukuran



n/2) DIVIDE_and_CONQUER(upa-masalah kedua yang berukuran n/2) COMBINE solusi dari 2 upa-masalah endif



Kompleksitas Waktu :



5



g ( n) , n  n0  T ( n)   2T (n / 2)  f (n) , n  n0



Kartika Dwi Hapsari | 105060809111003



Kartika Dwi Hapsari 6 Desain dan Analisa Algoritma – Divide and Conquer



Contoh masalah : 1. Mencari nilai minimum dan maksimum 4



12



23



9



21



1



35



2



24



Ide dasar algoritma secara Divide and Conquer:



4



12



23



9



21



1



35



2



24



1



35



2



24



1 35 min = 1 maks = 35



2



24



1



2



24



DIVIDE 4



12



23



9



21



SOLVE: tentukan min & maks pada tiap bagian 4



12 23 min = 4 maks = 23



9



21



COMBINE 4



12 23 min = 1 maks = 35



9



21



35



Algoritma: 1. Untuk kasus n = 1 atau n = 2, SOLVE: Jika n = 1, maka min = maks = A[n] Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks. 2. Untuk kasus n > 2, 6



(a) DIVIDE: Bagi dua tabel A menjadi dua bagian yang sama, A1 dan A2



Kartika Dwi Hapsari | 105060809111003



Kartika Dwi Hapsari 7 Desain dan Analisa Algoritma – Divide and Conquer



(b) CONQUER: MinMaks(A1, n/2, min1, maks1) MInMaks(A2, n/2, min2, maks2) (c) COMBINE: if min1