Reyka Firdhaulisia Julyanti: Metode Greedy dan Algoritma Divide and Conquer

Metode Greedy dan Algoritma Divide and Conquer

Pengertian metode greedy

Metode/Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah. Prinsip utama algoritma greedy adalah “take what you can get now!”. Maksud dari prinsip tersebut adalah pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir.

Salah satu penggunaan metode greedy adalah untuk menyelesaiakan permasalahan Knapsack (Knapsack problem), knapsack problem bisa kita gambarkan, misalnya kita mempunyai sebuah kantong atau tas dengan kapasitas tertentu sedangkan dihadapan kita terdapat begitu banyak pilihan barang, maka kita harus memilih barang mana saja yang kira-kira akan kita ungkut sesuai kapasitas kantong yang kita miliki supaya kita bisa mendapatkan keuntungan yang sebesar-besarnya atau maksimal.

Contoh persoalan Knapsack lain dengan 6 objek:

w₁ = 100; p₁ = 40

w₂ = 50; p₂ = 35

w₃ = 45; p₃ = 18

w₄ = 20; p₄ = 4

w₅ = 10; p₅ = 10

w₆ = 5; p₆ = 2

Kapasitas knapsack W = 100

Properti objek				Greedy by			Solusi Optimal
i	w_i	p_i	p_i/w_i	profit	weight	density	Solusi Optimal
1	100	40	0,4	1	0	0	0
2	50	35	0,7	0	0	1	1
3	45	18	0,4	0	1	0	1
4	20	4	0,2	0	1	1	0
5	10	10	1,0	0	1	1	0
6	5	2	0,4	0	1	1	0
Total bobot				100	80	85	100
Total keuntungan				40	34	51	55

Pada contoh terlihat algoritma greedy dengan ketiga strategi pemilihan objek tidak berhasil memberikan solusi optimal. Solusi optimal permasalah ini adalah X = (0, 1, 1, 0, 0, 0) dengan total keuntungan = 55.

Kesimpulan: Algoritma greedy tidak selalu berhasil menemukan solusi optimal untuk masalah Knapsack.

Algoritma Divide and Conquer

Algoritma Divide and Conquer adalah strategi pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil secara rekursif hingga masalah tersebut dapat dipecahkan secara langsung. Solusi yang didapat dari setiap bagian kemudian digabungkan untuk membentuk sebuah solusi yang utuh.

Pada algoritma Divide and Conquer ini memiliki tiga proses utama yaitu :

1. Divide

membagi masalah menjadi beberapa upa masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama).

2. Conquer

memecahkan (menyelesaikan) masing-masing upa masalah (secara rekursif).

3. Combine

mengabungkan solusi masing-masing upa masalah sehingga membentuk solusi masalah semula.

Ada 4 hal penting yang harus dipahami dalam strategi ini :

1. Branching Factor
Branching factor dalam algoritma divide and conquer adalah jumlah dari subproblem yang akan dibagi dari sebuah problem awal. Ini adalah langkah nyata dari algoritma divide and conquer, didalam proses pembagian yang sebenarnya, jumlah dari branching factor harus 2 atau lebih, karena jika tidak problem tidak bisa dibagi. Banyak jenis algoritma ini termasuk pula algoritma komputasi geometric yang memiliki branching factor berjumlah 2.

2. Balance
Sebuah algoritma divide and conquer dikatakan balance jika problem awal dibagi menjadi sub-sub problem dengan ukuran yang sama. Yang artinya jumlah dari keseluruhan ukuran subproblem sama dengan ukuran problem awal (initial problem). Algoritma Mergesort dan binary tree, dan sama halnya dengan algoritma reduksi & prefix sum adalah beberapa contoh algoritma divide and conquer yang seimbang (balance).

3. Data Dependence of Divide Function
Algoritma divide and conquer memiliki sebuah fungsi pembagian terhadap data yang memiliki ketergantungan, artinya jika ukuran relatif dari sebuah Pseudocode untuk model algoritma n-way divide and conquer subproblem tergantung pada proses input datanya. Ini adalah salah satu ciri dari algoritma yang tidak seimbang, salah satu contohnya adalah algoritma quicksort yang akan membagi subproblem dengan fungsi data-dependent divide.

4. Control Parallelism or Sequentiality
Algoritma divide and conquer dikatakan berurutan (sequential) jika subproblem dieksekusi sesuai dengan perintah program.

Skema Umum Algoritma Divide and Conquer :

Contoh 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 :

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.

Nama : Reyka Firdhaulisia Julyanti

NPM : 59414130

Kelas : 1IA25

sumber :

http://bloglogika.blogspot.com/2011/01/knapsack-problem.html

http://indahyanda.blogspot.com/2012/10/metode-greedy-dan-dynamic-programming_7509.html

http://mumhanaartanti.blogspot.com/2013/10/pengertian-metode-divide-conquer-dan.html

https://andikafisma.wordpress.com/algoritma-divide-and-conquer/