Coretan Kuliah: June 2015

Tugas Algoritma dan Pemrograman 2C (Metode Greedy dan Divide and Conquer)

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.

Metode greedy dipakai dalam masalah :

1. Optimal On tape Storage Problem

2. Knapsack Problem

3. Minimum Spanning Tree Problem

4. Shortest Path Problem

Contoh :

Pada kasus penukaran uang, misalnya kita memiliki uang senilai 50 dan akan kita tukarkan dengan uang koin, pecahan yang tersedia adalah 2, 5, 15, 25. Jika kita mengharapkan agar pecahan yang kita miliki seminim mungkin maka kita bisa menggunakan metode greedy dengan cara memilih pecahan terbesar terlebih dahulu.

Penyelesaian :

Uang 50

Pecahan 2,5,15,25

Dengan metode greedy kita harus memilih pecahan terbesar terlebih dahulu yaitu 25, kemudian selanjutnya menghitung sampai sesuai dengan uang yang kita miliki.
yaitu 25+25= 50 (2 koin)

Ada beberapa alternatif solusi pemecahan masalah diatas sebagai berikut :

50 = 2+2+2+2+...+2 (25 koin)
50 = 2+2+2+2+2+5+5+15+15 (9 koin)
50 = 5+5+5+5+15+15 (6 koin)

50 = 5+5+15+25 (4 koin)

Dalam hal ini metode greedy berhasil mendapat kan hasil maksimal secara global atau secara keseluruhan dengan mengambil koin yang terbesar terlebih dahulu.

Namun ada kalanya metode greedy gagal mendapatkan solusi optimal, hal ini juga dikarenakan oleh sifat metode greedy itu sendiri yang memperhatikan keuntungan lokal(diawal) tanpa memperhatikan kemungkinan solusi yang lain, contoh:

Uang yang ditukar sebesar 9

Pecahan yang tersedia 6,5,4,2, dan 1

Jika kita menukarkan uang tersebut dengan metode greedy maka kita harus mengambil pecahan terbesar lebih dulu yaitu 6, baru kemudian kita memilih pecahan berikutnya hingga berjumlah 9

9 = 6+2+1 (3 koin) sedangkan alternatif solusi 9 = 5+4 (2 koin).

Pada contoh diatas jelas terlihat bahwa metode greedy gagal memberikan solusi optimal.

DIVIDE AND CONQUER

Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang prinsip nya adalah 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 sub-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).

Conquer : Memecahkan ( menyelesaikan ) masing-masing sub-masalah ( secara rekursif ).

Combine : Menggabungkan solusi masing-masing sub-masalah sehingga membentuk solusi masalah semula.

Skema Umum Algoritma Divide and Conquer :

Procedure DNC ( i,j : integer )

Var K : integer ;

If SMALL (i,j) then SOLVE (i,j)

Else begin

K : = DIVIDE (i,j)

COMBINE (DNC(i,k),DNC(k+1,j))

End if

Contoh Kasus :

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 :