Rezha Pahlevi: Metode Greedy dan Divide & Conquer

Nama : Muhammad Rezha Pahlevi
Npm : 57414491
Kelas : 1IA24

Metode Greedy

Metode ini digunakan untuk memperoleh solusi yang optimal dari suatu masalah yang mempunyai 2 indikator yaitu : adanya fungsi tujuan & pembatas (Constrain).

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

CONTOH :

Himpunan A merupakan himpunan pasangan terurut (x,y), yaitu { (2,1),(3,2),(7,1), dan (1,0)}. Dari data-data tersebut akan ditentukan suatu pasangan terurut yang memiliki jumlah x dan y yang minimum. Adapun batasan dari x dan y masing-masing lebih besar dari nol.

Penyelesaiannya :

Solusi ß 0

N = 1 : x=2 > 0

Y=1 > 0 FEASIBLE (solusi, x)

Solusi ß {(2,1)}

N = 2 : x=3 > 0

Y=2 > 0 FEASIBLE (solusi, x)

Solusi ß {(2,1),{3,2)}

N = 3 : x=7 > 0

Y = 1 > 0 FEASIBLE (solusi, x)

Solusi ß {{2,1),(3,2),(7,1)}

N = 4 : x = 1 > 0

Y = 0 > 0 TIDAK FEASIBLE

Solusi ß {(2,1),{3,2),(7,1)}

Dari himpunan solusi yang mungkin tersebut diperoleh solusi yang optimal (dalam hal ini minimum) adalah (2,1) yang jumlahnya sebesar 2 + 1 = 3.

Jadi solusi = (2,1)

METODE GREEDY banyak digunakan dalam berbagai penyelesaian maslah, antara lain adalah :

1. Optimal Storage on Tapes Problem

2. Kanpsack Problem

3. Minimum Spanning Tree Problem

4. Shortest Path Problem

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.

n Obyek permasalahan yang dibagi :

masukan (input) atau instances yang berukuran n seperti:

- tabel (larik),

- matriks,

- eksponen,

- dll, bergantung pada masalahnya