Algoritma Divide and Conquer

 

ㅤㅤ

ㅤㅤDalam era globalisasi ini, teknologi semakin berkembang pesat. Hampir semua orang di dunia ini membutuhkan teknologi untuk mempermudah semua pekerjaan mereka. Perkembangan teknologi sangat membantu manusia untuk mengerjakan berbagai persoalan dengan efektif dan efisien. 

ㅤㅤHampir setiap hari benda – benda elektronik ditemukan disekitar manusia. Hal tersebut bukanlah hal yang tabuh untuk zaman sekarang, sebaliknya benda elektronik tersebut membantu manusia untuk mempersingkat waktu mereka dalam mengerjakan suatu tugas, seperti halnya printer bisa digunakan untuk mencetak dokumen yang diperlukan. Dalam pencetakan tersebut terdapat suatu pembagian dan penggabungan area yang akan menggunakan algoritma divide and conquer.

ㅤㅤA. Sejarah Algoritma Divide and Conquer

ㅤㅤㅤ Pada zaman dahulu, divide and conquer merupakan strategi militer yang dikenal dengannama divide ut imperes. Saat ini strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama divide and conquer. Algoritma divide and conquer ini ditemukan oleh seorang ilmuwan Rusia bernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya beliau menemukan algoritma yang lebih mangkus untuk mengalikan dua buah bilangan bulat yang besar dengan kompleksitas O(nlog 3).

ㅤㅤB. Definisi Algoritma Divide and Conquer

ㅤㅤㅤ Divide and conquer merupakan algoritma yang sangat popular di dunia ilmu komputer. Divide and conquer merupakan algorita yang berprinsip memecah – mecah suatu permasalahan yang terlalu besar menjadi bagian – bagian kecil, sehingga lebih mudah untuk diselesaikan. Langkah – langkah umum algoritma untuk divide and conquer adalah, sebagai berikut: 

ㅤㅤ• Divide 

ㅤㅤ Membagi masalah menjadi beberapa upamasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama). 

ㅤㅤ• Conquer 

ㅤㅤ Memecahkan atau menyelesaikan masing – masing upa-masalah secara rekursif 

ㅤㅤ• Combine 

ㅤㅤ  Menggabungkan solusi masing – masing upa-masalah sehingga membentuk solusi masalah semula.

ㅤㅤC. Cara Kerja 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.

ㅤㅤ

ㅤㅤ

Ditulis oleh:

Mahasiswi Universitas Teknokrat Indonesia, Fakultas Teknik dan Ilmu Komputer dengan nama Clifansi Remi Siwi Hati (21312004) dari IF 21 A