METODE DEVIDE AND CONQUER DAN PENYELESAIANNYA

1. Metode Greedy

Algoritma Greedy adalah salah satu jenis algoritma, algoritma greedy menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara dalam setiaplangkahnya atau local maxium.Algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktuyang cukup cepat. 

Persoalan:

Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat maksimum 15 Kg dan sehimpunan benda A = {a₀, a₁, a₂, a₃} yang berbobot (dalam Kg) W = {5,9,2,4}. Setiap benda tersebut diberikan nilai profit P = {100, 135, 26, 20}. Jika kita diperbolehkan memasukkan zi  bagian dari benda ai yang ada ke dalam knapsack dimana 0 ≤ zi ≤ 1 , maka tentukanlah Z = {z0,z1,z2,z3} agar diperoleh total profit yang maksimal !

Jawab :

Dik : 

n = 4; M = 15;       

W = { 5,9,2,4 };        

P = { 100,135,26,20 }, 

Dit : total profit yang maksimal ?

Barang ke -	Berat(Wi)	Keuntungan(Pi)	Pi/Wi
Z0	5	100	20
Z1	9	135	15
Z2	2	26	13
Z3	4	20	5

Z ← 0

cu ← 15

i = 0

karena W(0) 〈 cu yaitu : 5 〈 15 berarti : Z(0) ← 1

cu ← 15 - 5 = 10

i = 1

karena W(1) 〈 cu yaitu : 9 〈 10 berarti : Z(1) ← 1

cu ← 10 - 9 = 1i = 2

karena W(2) 〉 cu yaitu : 2 〉 1 berarti : keluar dari loop (exit)

Karena 2 ≤ 3 maka Z(2) ← cu/W(2) = 1/2 = 0,5

Jadi optimisasi masalah knapsack diperoleh bila Z = { 1; 1; 0,5; 0 }

Sehingga Q = 1 x 100 + 1 x 135 + 0,5 x 26 + 0 x 20

= 100 + 135 + 13 + 0

= 248

2. Metode 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.

Rumus Algoritma Divide and Conquer:

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 :1. 

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.

2. 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.

Optimasi Konversi Bilangan Desimal Ke Biner

Skema procedur utama Konversi dengan optimasi

Skema procedur rekursif dengan menerapkan Algoritma Divide and Conquer

Penyelesaian dengan Algoritma Divide and Conquer secara umum :

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 masing - masing 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.