Algoritma - Pemecahan dan Penyelesian

Algoritma Divide (pemecahan) and Conquer (penyelesaian) dikembangkan karena semakin besarnya ruang lingkup hal yang dilakukan oleh komputer sehingga perangkat lunak yang dikembangkan juga menjadi semakin kompleks. Maka disini Divide and Conquer dijadikan sebagai algoritma dengan teknik memecah-mecah masalah yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Ketika kita terus membagi masalah menjadi sub-masalah yang lebih kecil, akhirnya nanti bisa mencapai tahap di mana tidak ada lagi pembagian yang mungkin. Sub-masalah terkecil (fractions) dapat dipecahkan sehingga solusi dari semua sub-masalah akhirnya digabungkan untuk mendapatkan solusi dari masalah asli.

images5

Objek masalah yang di bagi inilah yang menjadi input atau instances yang berukuran n bisa berupa tabel, matriks, dsb. Tiap-tiap sub-masalah dibuat mempunyai karakteristik yang sama dengan karakteristik masalah asal, sehingga metode ini memang cocok diungkapkan dalam skema rekursif. Karena karakteristik pembagian dan pemecahan masalah maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri)atau juga bisa diimplementasikan dengan cara iteratif ( perulangan biasa ). Secara umum, kita dapat memahami pendekatan Divide and Conquer dalam proses:

Divide/Break artinya Memecah: pada langkah ini kita melibatkan pemecahan masalah atau data ke dalam bentuk yang sama, tetapi menjadi sub-masalah yang lebih kecil, dalam ukuran yang lebih kecil. Pendekatan yang dilakukan adalah rekursif sehingga bisa membagi masalah sampai tidak ada lagi sub-masalah yang dapat dibagi. Pada tahap ini, sub-masalah menjadi bersifat atom tetapi masih mewakili beberapa bagian dari masalah yang sebenarnya

Conquer/solve artinya menaklukkan: Disinilah langkah dimana banyak sub-masalah yang lebih kecil untuk dipecahkan masalah atau datanya sebagaimana hasil dari pada langkah pertama dengan penggunaan algoritma sederhana.Bahkan pada tingkat ini, masalah dianggap ‘terpecahkan’ sendiri.

Merge/Combine artinya Menggabungkan: Setelah menjalankan langkah conquer, sub-masalah yang lebih kecil diselesaikan, tentunya harus melakukan penggabungan kembali hasil dari masing-masing pecahan yang ada, sampai mereka merumuskan solusi dari masalah asli. Pendekatan algoritmik ini bekerja secara rekursif dengan langkah Divide and Conquer yang begitu dekat sehingga tampak sebagai satu.

Penggunaan algoritma komputer didasarkan pada pendekatan pemrograman divide-and-conquer yang sering digunakan adalah Merge Sort, Quick Sort, Binary Search, Strassen’s Matrix Multiplication, Closest pair (points)

Algoritma Divide and Conquer memiliki kelebihan sehingga banyak diterapkan atau digunakan dalam aplikasi dunia nyata, yaitu bias menyelesaikan masalah yang sulit, atau masalah rumit yang hingga kini sangat cukup sulit dipecahkan oleh komputer biasa, seperti Tower of Hanoi Problem. Pada Algoritma ini penggunaannya sangat efisien pada kasus tertentu semisal Sorting sehingga dilakukan dengan kompleksitas algoritma O(n log n) dari algoritma lainnya yang hanya mampu mencapai kompleksitas O (n2). Algoritma ini juga bekerja secara paralel sehingga memaksimalkan penggunaan dari cache memory.

Baik contoh sederhananya seperti ini: Kita akan mencari nilai minimum dan maksimum suatu table:

images1 Ide dasar divide-and-conquer, adalah membagi masalah DIVIDE

images2

Menemukan Conquer masalah dengan menentukan minimum dan maksimum masing2 Divide

images3

Combine, menggabungkan kembali images4

Setelah melihat hasil sub-masalah dapat melihat hasil minimum maksimum nilai Minimum: 1 - Maksimum : 35

Penjelasan Algoritma MinMaks : Jika pada kasus n = 1 atau n = 2, maka SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks. Sedangkan pada kasus n > 2, lakukan divide dengan membagi dua tabel A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.

Kemudian Conquer / Solve dengan menerapkan algoritma Divide and Conquer pada masing-masing bagian, disini terdapat min dan maks dari table bagian kiri yang dinyatakan dalam peubah min1 dan maks1, begitupun min dan maks dari tabel bagian kanan dinyatakan dalam peubah min2 dan maks2.

Setelah itu combine dengan membandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.