Metode Greedy dan Algoritma Divide and Conquer

A. Metode Greedy

(a). Pengertian Metode Greedy

Metode greedy adalah metode yang digunakan untuk memecahkan persoalan optimasi, ada 2 macam persoalan optimasi, yaitu maksimasi dan minimasi, artinya dengan metode greedy kita bemaksud mencari solusi terbaik, yaitu solusi yang benilai minimum atau maksimum dari sekumpulan alternatif solusi yang ada.

arti kata greedy sendiri adalah RAKUS, namun maksud dari metode grredy adalah kita melihat solusi optimal lokal, atau solusi optimal yang tampak didepan mata, dengan harapan mendapatkan solusi optimal secara global atau secara keseluruhan

(b). Contoh Soal Metode Greedy

Kita mempunyai suatu Himpunan , yaitu Himpunan A. Himpunan A adalah himpunan pasangan yang terurut (x,y), yaitu ( 2,3), (3,4),(4,5) (0,1). lalu dari data diatas kita akan tentukan suatu pasangan terurut yang memiliki jumlah x dan y yang paling kecil atau minimum.. dengan ketentuan batasan dari x dan y itu harus lebih besar dari 0.

Jawab:

N= 1: x = 2 > 0

          y = 3 > 0   FEASIBLE (Solusi , x)

          Solusi = {(2,3)}

N= 2: x = 3 > 0

          y = 4 > 0   FEASIBLE (Solusi , x)

          Solusi = {(2,3),(3,4)}

N= 3: x = 4 > 0

          y = 5 > 0   FEASIBLE (Solusi , x)

          Solusi = {(2,3),(3,4),(4,5)} 

N= 4: x = 0 > 0

          y = 1 > 0   TIDAK FEASIBLE 

          Solusi = {(2,3),(3,4),(4,5)} 

Jadi, dari Himpunan diatas solusi optimalnya (minimum) adalah (2,3) yang jumlahnya 2 + 3 = 5

B. Algoritma Divide and Conquer.

(a). Pengertian

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.

(b). Contoh Soal.

untuk contoh soal Metode Greedy dan Algoritma Divide and Conquer dibuat sama. 

Kita mempunyai suatu Himpunan , yaitu Himpunan A. Himpunan A adalah himpunan pasangan yang terurut (x,y), yaitu ( 2,3), (3,4),(4,5) (0,1). lalu dari data diatas kita akan tentukan suatu pasangan terurut yang memiliki jumlah x dan y yang paling kecil atau minimum.. dengan ketentuan batasan dari x dan y itu harus lebih besar dari 0

Jawab:

Disini kita mempunyai 4 data, 4 data tersebut kita bagi menjadi 2 sub masalah.

{(2,3),(3,4),(4,5),(0,1)}.

Sedangkan kondisi untuk bisa masuk ke proses berikutnya atau proses perbandingan adalah x dan y harus lebih besar dari nol. lalu kita lakukan seleksi untuk menentukan sub masalah mana yang bisa masuk ke proses perbandingan. dan yang tidak masuk ke proses berikutnya yaitu (0,1). berarti sisa (2,3),(3,4), dan (4,5). Selanjutnya kita akan cari nilai minimum dari x+y.

{(2 + 3 = 5), (3 + 4 = 7), dan (4 + 5 = 9)}

Maka nilai minimum yang di dapat adalah 5
Jadi pasangan Minimumnya adalah (2,3)