Tugas Algoritma dan Struktur Data

METODE GREEDY DAN DINAMIC PROGRAMING

OLEH :

RASMIATI ASWA (H12111287)

PRODI STATISTIKA JURUSAN MATEMATIKA

FAKULRAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS HASANUDDIN  MAKASSAR 2012

Metode greedy

·           Pengertian

Metode/Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah. Pada setiap langkah tersebut akan dipilih keputusan yang paling optimal. Keputusan tersebut tidak perlu memperhatikan keputusan selanjutnya yang akan diambil, dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya.

·           Prinsip Utama Algoritma Greedy

Prinsip utama algoritma greedy adalah ?take what you can get now!?. Maksud dari prinsip tersebut adalah sebagai berikut: Pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi 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.

·           Elemen Algoritma Greedy

Elemen-elemen yang digunakan dalam penerapan algoritma greedy antara lain

1. Himpunan Kandidat
    Himpunan yang berisi elemen pembentuk solusi.

2. Himpunan Solusi
    Himpunan yang terpilih sebagai solusi persoalan

3. Fungsi Seleksi
    Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal.

4. Fungsi Kelayakan

Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi   yang      layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada

5. Fungsi Solusi

Fungsi yang mengembalikan nilai boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap.

6. Fungsi Objektif

     Fungsi yang mengoptimalkan solusi.

·         Skema Umum Algoritma Greedy
Misal kita mengasumsikan elemen algoritma greedy sebagai berikut :
Himpunan Kandidat = C,
Himpunan Solusi = S,
Fungsi Seleksi = select(),
Fungsi Kelayakan = feasible(),
Fungsi Solusi = solution(), dan
Fungsi Obyektif = objective().
Skema umum dari algoritma greedy dapat kita tuliskan :
- Inisialisasi S dengan kosong.
- Pilih sebuah kandidat dari C (dengan select()).
- Kurangi C dengan kandidat yang telah terpilih di atas.
- Periksa apakah kandidat yang dipilih tersebut bersama ? sama dengan S membentuk solusi yang layak (dengan feasible()). Jika ya, masukkan kandidat ke S; jika tidak buang kandidat tersebut dan tidak perlu ditelaah lagi.
- Periksa apakah S yang sudah terbentuk telah memberikan solusi yang lengkap (dengan solution()). Jika ya, berhenti; jika tidak, ulangi dari langkah 2.

·         Kelebihan : cepat dalam menemukan solusi

·         Kekurangan : tidak semua masalah bisa diselesaikan dengan greedy.

Contoh :

Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Koin yang tersedia adalah koin-koin 1,5,10,dan 25. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?

Jawab:

Uang senilai 32 dapat ditukar dengan cara berikut :

32= 1+1+…….+1                             (32 koin)

32= 5+5+5+5+10+1+1                      (7 koin)

32=10+10+10=1+1                           (5 koin)

…. Dan seterusnya

Minimum 32=25+5+1+1 hanya 4 koin.

Strategi greedy yang digunakan adalah:

Pada setiap langkah , pilihlah kon dengan nilai sebesar mungkin dari himpunan koin yang tersisa dengan syarat (kendala) tidak melebihi nilai yang di tukarkan.

Tinjau masalah menukarkan uang 32 dengan koin 1,5,10, dan 25.

Langkah 1: pilih 1 buah kon 25 (total=25)

Langkah 2 : pilih I buah koin 5 (total= 25+5=30)

Langkah 3: pilih 2 buah koin 1 (total= 25+5+1+1=32)

Solusi: Jumlah koin minimum 4 (solusi optimal).

Program Dinamis (dynamic programming)

Program Dinamis (dynamic programming): metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan  yang saling berkaitan.

Pada penyelesaian persoalan dengan metode ini:

1.      terdapat sejumlah berhingga pilihan yang mungkin,

2.      solusi pada setiap tahap dibangun dari hasil solusi tahap sebelumnya,

3.      kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.

Prinsip Optimalitas

•          Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas.

•          Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal.

•          Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya.

•          Pada metode greedy hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.

Karakteristik Persoalan Program Dinamis

1.      Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.

2.      Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut

3.      Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.

4.      Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.

5.      Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.

6.      Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.

7.      Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.

8.      Prinsip optimalitas berlaku pada persoalan tersebut.

·         Kelebihan :Lebih akurat dalam menemukan solusi dan dapat menyelesaikan semua masalah

·         Kekurangan : membutuhkan waktu yang cukup lama dalam menemukan solusi

Tentukan jalur terpendek  yang data ditempuh dari A ke L

                                          

                                          5                   I            4

                                                    6                           3

                                       I            5  

                        3             I                                      I    4            3              I                                                                                     

                                       I           4                                                       I                            5                           

                             2        I            5                                                      I

                                        I                                      I                 6                     I

                       3                   I        5          6                                   2                            6

                                        I             2                                                Step 3

                                                                           I                   5      

                                                Step 1              4

                                                                        Step 2

Dengan Metode Greedy :

Dari A ke L = 2+4+3+5 = 14 yaitu dilihat kedepannya yang mana lebih kecil.

Dynamic Programming :

Langkah 2

Dist (E) =                 cost (E) = 8

Dist (F) =                 cost (F) = 6

Dist (G) =                cost (G) = 7

Dist (H) =               cost (H) = 5

Dist (I) =                  cost (I)  = 7

langkah 3

Dist (J) =               cost (J) =  6+3 = 9

Dist (K) =            cost (K) = 5+2 = 7

Dist (L) =         cost (L) = 7 + 6= 13

1.    Metode greedy

Dengan menggunakan metode greedy kita akan mmemasukkan potongan- potongan bangun didalam sebuah kotak sehingga meyisahkan luas kotak yag sangat. Pada metode ini kita meletakkan gabungan  potongan-potongan bangun sehingga bebentuk persegi panjang sehingga lebih mudah  diletakkan pada kotak tersebut. Kotak ini memiliki ukuran 15 cm x 35 cm. Misalnya gabungan 2 potong bangun    2 m      

dan 2 potong bangun  2m                  

sehingga berbentuk persegi panjang dengan ukuran 6 cm x 8 cm

                                 2 m                2 m

 

                                                         6   6m 

                                                                  

Dengan memasukkan persegi panjang diatas yang dikombinasikan dengann persegi panjang yang berukuran 2 cm x 4 cm. Kita memperoleh luas sisa bangun 53 cm²           .

                                                                                                            2      1

                       8

                                       6

 

2                                                                                                                        

1                                                     

Keterangan :

                                                       

                                                             = 6 m x 8 m = 48 m²

                                                                                = 2 m x 4 m = 8 m²

                                                      

                                                            =   1 m x 32 m = 32 m²

 

                                                             = 3 m x 2 m = 6 m²

Luas Sisa       =  1m x 32 m + 3 m x 2m + 1 m x 15 m

                       = 53 m²

2.      Metode dinamic programing

Dengan metode dynamic programing kita akan mmemasukkan potongan- potongan bangun didalam sebuah kotak sehingga meyisahkan luas kotak yag sangat. Pada metode ini kita meletakkan gabungan  potongan-potongan bangun sehingga bebentuk persegi panjang sehingga lebih mudah  diletakkan pada kotak tersebut. Dibawah ini 2 potong bangun digabung sehigga berbentuk persegi panjang yang berukuran 4 m x 7m = 28 m²

                                         

                                         

 

 Kemudian kotak dibagi menjadi dua

Kemudian persegi panjang yang berukuran  18 bangun yag bertukura 4 m x 7 cm  dan 1 bangun yang berukuran 2 m x 4 m dimasukkan dalam kotak sehigga isi kotak menjadi

Luas Sisa       = Luas Keseluruhan – Luas yang Terisi

                       = (35x15) –(18.28 + 1.8)

                       = 525 – (18.28 + 8)

                       = 525 – (512 )

                       = 13 m²

Dengan melihat sisa luas dari kotak , metode yang paling efektif adalah metode dynamic programming.