ALGORITMA
DIVIDE AND CONQUER
A.
DEFINISI
Divide and
conquer adalah paradigma desain algoritma yang didasarkan pada rekursi
multi-cabang. Algoritma divide-dan conquer bekerja dengan memecah masalah secara
rekursif menjadi dua atau leih sub-masalah dari jenis yang sama atau terkait,
hingga masalah ini menjadi cukup sederhana untuk diselesaikan secara langsung.
Solusi untuk sub-masalah kemudian digabungkan untuk memberikan solusi untuk
masalah aslinya.
Teknik
divide and conquer ini adalah dasar dari algoritma yang efisien untuk semua
jenis masalah, seperti pengurutan (misalnya, quicksort, jenis penggabungan),
mengalikan angka-angka besar (misalnya algoritma Karatsuba), menemukan pasangan
titik terdekat, analisis sintaksis (misalnya, parser top-down ), dan menghitung
transformasi Fourier diskrit.
Memahami
dan mendesain algoritma divide and conquer adalah keterampilan kompleks yang
membutuhkan pemahaman yang baik tentang sifat dasar masalah yang akan
dipecahkan. Seperti ketika membuktikan teorema dengan induksi, seringkali
masalah asli harus diganti dengan masalah yang lebih umum atau rumit untuk
menginisialisasi rekursi, dan tidak ada metode sistematis untuk menemukan
generalisasi yang tepat. Komplikasi bagi-dan-taklukkan ini terlihat saat
mengoptimalkan penghitungan angka Fibonacci dengan rekursi ganda yang efisien.
Kebenaran
dari algoritma bagi-dan-taklukkan biasanya dibuktikan dengan induksi matematis,
dan biaya komputasinya sering ditentukan dengan menyelesaikan hubungan
pengulangan.
B.
SEJARAH
Algoritma divide
and conquer di mana sub-masalah berukuran kira-kira setengah dari ukuran
aslinya, memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang
algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John
Mauchly, gagasan untuk menggunakan daftar item yang disortir untuk
memfasilitasi pencarian berasal dari setidaknya sejauh Babylonia pada 200 SM.
Algoritma divide and conquer kuno lainnya adalah algoritma Euclidean untuk
menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi
bilangan tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih
kecil, yang berasal dari beberapa abad SM.
Contoh awal
dari algoritma bagi dan aklukkan dengan beberapa subproblem adalah deskripsi
Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley-Tukey fast
Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya
secara kuantitatif, dan FFT tidak tersebar luas sampai ditemukan kembali lebih
dari satu abad kemudian.
Algoritma
D&C dua subproblem awal yang secara khusus dikembangkan untuk komputer dan
dianalisis dengan tepat adalah algoritma pengurutan gabungan, yang ditemukan
oleh John von Neumann pada tahun 1945.
Contoh
penting lainnya adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada
tahun 1960 yang dapat mengalikan dua angka n- digit dalam O operasi (dalam notasi Big O). Algoritma ini
membantah dugaan tahun 1956 Andrey Kolmogorov operasi akan diperlukan untuk tugas itu.
Sebagai
contoh lain dari algoritma bagi-dan-taklukkan yang awalnya tidak melibatkan
komputer, Donald Knuth memberikan metode yang biasanya digunakan kantor pos
untuk merutekan surat: surat diurutkan ke dalam kantong terpisah untuk wilayah
geografis yang berbeda, masing-masing kantong ini diurutkan sendiri ke dalam
batch untuk sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. Ini
terkait dengan jenis radix, dijelaskan untuk mesin sortir kartu berlubang sejak
tahun 1929.
C.
CARA KERJA
Objek
masalah yang di bagi adalah masukan (input) atau instances yang berukuran n:
tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap masalah
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. Salah satu penggunaan
algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe
array (elemen larik). Mengapa ? Karena pengolahan array pada umumnya selalu
menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah
untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array.
Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar
pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort,
dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma
O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan
menggunakan algoritma brute force.
Skema umum algoritma Divide And Conquer :
D.
PENERAPAN
ALGORITMA
1. Pemecahan
Masalah Convex Hull dengan Algoritma Divide and Conquer
Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer, hal ini dapat dipandang sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:
- Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).
- Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).
- Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.
- Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).
- Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung da mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.
Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi. Divide and Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.
Algoritma
Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah
convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup
kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan
algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk
permasalahan convex hull yang berdimensi lebih dari 3.
2. Persoalan
Minimum dan Maksimum (MinMaks)
Persoalan : Misalnya diketahui table A yang berukuran
n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan
nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi
elemen-elemen sebagai berikut :
Ide dasar algoritma secara Divide and Conquer :
Ukuran table hasil pembagian dapat dibuat cukup kecil
sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih
mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.
Algoritma MinMaks :
a. Untuk kasus
n = 1 atau n = 2,
SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2,
maka bandingkan kedua elemen untuk menentukan min dan maks.
b. Untuk kasus
n > 2,
DIVIDE : Bagi dua table A secara rekursif menjadi dua
bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.
CONQUER : Terapkan algoritma Divide and Conquer untuk
masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri
dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian
kanan dinyatakan dalam peubah min2 dan maks2.
COMBINE : Bandingkan min1 dan min2 untuk menentukan
min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.
3. Optimasi
Konversi Bilangan Desimal Ke Biner
Salah satu cara optimasi yang bias kita lakukan adalah
membagi bilangan decimal yang hendak diubah dengan angka 8 ( bukan 2 ). Di
sinilah prinsip algoritma Divide and Conquer kita gunakan untuk melakukan
optimasi. Kita pecah-pecah angka decimal yang akan kita gunakan dengan cara
membaginya dengan angka 8 secara berulang. Angka-angka sisa pembagian yang kita
peroleh kemudian kita ubah ke dalam bilangan biner sebelum kita gabungkan
menjadi hasil jawaban.
Karena angka pembagi yang kita pakai adalah 8 (23),
maka kita dapat mengurangijumlah pembagian yang kita lakukan menjadi ± 1/3 dari
jumlah semula. Hal ini tentu saja akan sangat berpengaruh pada kinerja dan
waktu yang diperlukan oleh computer mengingat proses pembagian merupakan salah
satu proses yang cukup rumit.
Tentu saja optimasi ini harus kita bayar dengan
menangani konversi bilangan octal ke biner. Akan tetapi jika kita gunakan
teknik perbandingan ( tanpa harus melakukan konversi secara manual ), maka
proses ini akan menjadi sangat cepat dan mudah. Penerapan algoritma ini adalah
dengan menggunakan sintaks case of. Begitu juga dengan permasalahan pemakaian
memori ( kompleksitas ruang ) yang lebih besar yang muncul akibat penggunaan
algoritma rekursif. Karena pada proses rekursif-nya kita tidak banyak
menggunakan variable yang memerlukan tempat yang begitu besar, maka hal ini
bias kita abaikan. Dengan penggunaan optimasi ini, maka seharusnya proses
konversi akan lebih cepat karena pemangkasan jumlah pembagian yang dilakukan.
Skema procedur utama Konversi dengan optimasi :
Skema procedur rekursif dengan menerapkan Algoritma
Divide and Conquer :
Kompleksitas waktu algoritma :
T(n) = O(n/3)
dengan n menyatakan eksponen terkecil dari 2 yang
mempunyai nilai 2n lebuh besar dari angka decimal.
Algoritma konversi system bilangan dengan menggunakan
algoritma dengan optimasi yang menerapkan algoritma Divide and Conquer lebih
mangkus daripada algoritma konversi dengan metode pembagian sisa biasa jika
dilihat dari segi kompleksitas waktunya. Hanya saja optimasi ini diimbangi
dengan kenaikan pada kompleksitas ruangnya, meskipun pengaruhnya tidak sebesar
optimasi yang kita lakukan.
4. Mencari
Pasangan Titik yang Jaraknya Terdekat (Closest Pair)
Persoalan : Diberikan himpunan titik, P, yang terdiri dari n buah titik, (xi,yi), pada bilangan 2-D. Tentukan jarak terdekat antara dua buah titik di dalam himpunan P. Jarak dua buah titik p1 = (x1, y1) dan p2 = (x2, y2) :
Penyelesaian dengan Algoritma Divide and Conquer :
a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).
b. Algoritma Closest Pair :
SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus
Euclidean.
DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight,
setiap bagian mempunyai jumlah titik yang sama
CONQUER : Secara rekursif, terapkan algoritma D-and-C pada masingmasing
bagian.
Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :
- Pasangan titik terdekat terdapat di bagian PLeft.
- Pasangan titik terdekat terdapat di bagian PRight.
- Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.
Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.
E. KEUNTUNGAN
ALGORITMA
1. Memecahkan
masalah yang sulit
Bagilah dan taklukkan adalah alat yang ampuh untuk
memecahkan masalah yang sulit secara konseptual: yang dibutuhkan hanyalah cara
memecahkan masalah menjadi sub-masalah, memecahkan kasus-kasus sepele dan
menggabungkan sub-masalah ke masalah asli. Demikian pula, mengurangi dan
menaklukkan hanya membutuhkan pengurangan masalah menjadi satu masalah yang
lebih kecil, seperti teka-teki Menara Hanoi klasik, yang mengurangi memindahkan
menara dengan ketinggian n untuk memindahkan menara dengan ketinggian n - 1
2. Efisiensi
algoritma
Paradigma divide-and-conquer sering membantu dalam
penemuan algoritma yang efisien. Itu adalah kunci, misalnya, untuk metode
perkalian cepat Karatsuba, algoritma quicksort dan mergesort, algoritma
Strassen untuk perkalian matriks, dan transformasi Fourier cepat.
Dalam semua contoh ini, pendekatan D&C mengarah pada
peningkatan biaya asimtotik solusi. Misalnya, jika (a) kasus dasar memiliki
ukuran batas konstan, pekerjaan pemecahan masalah dan penggabungan solusi
parsial sebanding dengan ukuran masalah n dan (b) ada bilangan terbatas p dari
sub-masalah dari size ~ n / p pada setiap tahap, maka biaya algoritma
divide-and-conquer adalah O ( n log p n ).
3. Paralelisme
Algoritme Divide-and-conquer secara alami diadaptasi untuk
eksekusi di mesin multi-prosesor, terutama sistem memori bersama di mana
komunikasi data antara prosesor tidak perlu direncanakan sebelumnya, karena
sub-masalah yang berbeda dapat dijalankan pada prosesor yang berbeda.
4. Akses memori
Algoritme bagi-dan-taklukkan secara alami cenderung
memanfaatkan cache memori secara efisien. Alasannya adalah setelah sub-masalah
cukup kecil, sub-masalah itu dan semua sub-masalah pada prinsipnya dapat
diselesaikan di dalam cache, tanpa mengakses memori utama yang lebih lambat.
Algoritme yang dirancang untuk mengeksploitasi cache dengan cara ini disebut
cache-oblivious , karena tidak memuat ukuran cache sebagai parameter eksplisit.
Selain itu, algoritme D&C dapat dirancang untuk algoritme penting
(misalnya, pengurutan, FFT, dan perkalian matriks) menjadi algoritme yang tidak
menyadari cache yang optimal - algoritme tersebut menggunakan cache dengan cara
yang mungkin optimal, dalam arti asimtotik, terlepas dari ukuran cache.
Sebaliknya, pendekatan tradisional untuk mengeksploitasi cache adalah memblokir
, seperti dalam pengoptimalan sarang loop , di mana masalahnya secara eksplisit
dibagi menjadi potongan-potongan dengan ukuran yang sesuai ini juga dapat menggunakan cache secara
optimal, tetapi hanya jika algoritme disetel untuk yang spesifik. ukuran cache
dari mesin tertentu.
Keuntungan yang sama terdapat pada sistem penyimpanan
hierarki lainnya, seperti NUMA atau memori virtual , serta untuk beberapa level
cache: setelah sub-masalah cukup kecil, sub-masalah dapat diselesaikan dalam
level hierarki tertentu, tanpa mengakses level yang lebih tinggi (lebih lambat).
5. Roundoff
kontrol
Dalam perhitungan dengan aritmatika bulat, misalnya dengan
bilangan floating-point , algoritme bagi-dan-taklukkan dapat menghasilkan hasil
yang lebih akurat daripada metode iteratif yang secara dangkal setara.
Misalnya, seseorang dapat menambahkan nomor N baik dengan loop sederhana yang
menambahkan setiap datum ke variabel tunggal, atau dengan algoritma D&C
yang disebut penjumlahan berpasangan yang memecah kumpulan data menjadi dua
bagian, secara rekursif menghitung jumlah setiap setengah, dan kemudian
menambahkan dua jumlah. Meskipun metode kedua melakukan jumlah penambahan yang
sama seperti yang pertama, dan membayar biaya tambahan dari panggilan rekursif,
metode ini biasanya lebih akurat.
Komentar
Posting Komentar