Dalam postingan ini, saya akan menerangkan secara sederhana tentan Algoritma Divide and Conquer beserta pengimplementasiannya di Java.
Algoritma Divide and Conquer
Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.
Langkah-langkah umum algoritma Divide and Conquer :
Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-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.
Contoh Algoritma Divide and Conquer
berikut adalah contoh penerapannya :
Pemecahan Masalah Convex Hull dengan 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 dan mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.
Pada algoritma di atas, dapat dilihat bahwa terdapat prosedur untuk mencari lower tangen dan upper tangen. Algoritmanya merupakan suatu algoritma berjalan yang biasa. Pada kasus ini, a diinisialisasi sebagai titik paling kanan dari HA dan b merupakan titik paling kiri dari HB. Jika pasangan ab belum merupakan lower tangen untuk HA dan HB , maka “nailkkan” a menjadi suksesor dari a dan “turunkan” b menjadi predesesor dari b, sesuai dengan kaidah arah jarum jam.
Berikut adalah gambaran umum dalam pencarian lower tangen dari HA dan HB : LowerTangen(HA, HB) :
- Misalkan a merupakan titik terkanan dari HA
- Misalkan b merupakan titik terkanan dari HB
- While (ab bukan merupakan lower tangen dari HA dan HB)do - While(ab bukan merupakan lower tangen dari HA) do a -> a.predesesor - While(ab bukan merupakan lower tangen dari HA) do b-> b.suksesor
- Return ab.
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.
Contoh kasus
Persoalan : Misalnya diketahui table A yang berukuran n elemen 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 :
3-10-20-5-17-1-31-2-19
Lalu algoritma melakukan divide seperti berikut :
3-10-20-5 & 17-1-31-2-19
Lalu algoritma melakukan solve seperti berikut :
dari 3-10-19-5 diketahui min=3;maks=20 , dan dari 17-1-31-2-20 diketahui min=1;maks=20.
Setelah melakukan solve, algoritma kemudian menggabungkan kedua data tersebut dan menentukan nilai min dan maks berdasarkan dari kedua data yang didapat, sehingga didapatlah min=1 maks=20.
Ilustrasi dari contoh kasus diatas bisa dilihat seperti gambar dibawah ini :
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.
Implementasi di Java
berikut adalah source code bagaimana pengimplementasiannya di Java :
import
java.io.BufferedReader;
import
java.io.IOException;
import
java.io.InputStreamReader;
import
java.util.Random;
public
class DivideConquer
{
public DivideConquer()
{
System.out.println("Divide
and Conquer: maximum subarray");
System.out.println("Enter
number of elements in the array");
int array_elements = 2;
try
{
BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
array_elements =
Integer.parseInt(reader.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
if (array_elements < 2)
{
System.out.println("Number of elements in the array should be
greater or equal 2");
}
else
{
Random random = new
Random();
int[] A = new
int[array_elements];
for (int i = 0; i <
A.length; i++)
A[i] =
random.nextInt(1000) - 500;
System.out.println("Original array");
for (int i : A)
{
System.out.print(String.format("%5d", i));
}
System.out.println();
int[] result = find_maximum_subarray(A, 0, A.length-1);
System.out.println("Maximum
sub-array");
System.out.println("Low " + result [0]);
System.out.println("High " + result [1]);
System.out.println("Sum " + result [2]);
}
}
private int[]
find_maximum_subarray(int[] A, int low, int high)
{
if( high == low)
{
int[] result = {low,
high, A[low]}; //base case: only one element
return result;
}
else
{
int mid = (low + high)
/2;
int[] result1 =
find_maximum_subarray (A, low, mid);
int[] result2 =
find_maximum_subarray (A, mid+1, high);
int[] result3 =
find_max_crossing_subarray(A, low, mid, high);
if( result1[2] >=
result2[2] && result1[2] >= result3[2] )
{
return result1;
}
else if (result2[2]
>= result1[2] && result2[2] >= result3[2])
{
return result2;
}
else
{
return result3;
}
}
}
private int[]
find_max_crossing_subarray(int[] A, int low, int mid, int high)
{
int left_sum =
Integer.MIN_VALUE;
int sum = 0;
int max_left = -1;
int max_right = -1;
for(int i = mid; i > low;
i--)
{
sum += A[i];
if (sum > left_sum)
{
left_sum = sum;
max_left = i;
}
}
int right_sum =
Integer.MIN_VALUE;
sum = 0;
for(int j = mid+1; j < high;
j++)
{
sum += A[j];
if (sum > right_sum)
{
right_sum =
sum;
max_left = j;
}
}
int[] result = {max_left, max_right, left_sum + right_sum};
return result;
}
}
Semoga membantu. :D
method main.nya mana bang
BalasHapus