Blog Tentang Informasi Tutorial Desain Web Dan Info Terkini

Algoritma Greedy



ini merupakan solusi optimum).Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian solusi optimum.



Persoalan optimasi ada dua macam:

1.    Maksimasi (maximization)

2.    Minimasi (minimization)



Solusi optimum (terbaik) adalah solusi yang bern

ilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.



Elemen persoalan optimasi:

1.    kendala (constraints)

2.    fungsi objektif(atau fungsi optiamsi)



Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut so

lusi optimum.


Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.



Greedy = rakus, tamak, loba, ….


Prinsip greedy adalah: “take what you can get now!”.


Contoh masalah sehari-hari yang menggunakan prinsip greedy:

Memilih beberapa jenis investasi (penanaman modal)


o  Mencari jalur tersingkat dari Bandung ke Surabaya

o  Memilih jurusan di Perguruan Tinggi

o  Bermain kartu remi

       



·              Algoritma greedy membentuk solusi langkah per langkah (step by step).



·              Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.



·              Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya  mengarah ke solusi optimum global (global optimm).









·                  Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah, pada setiap langkah:

1.               mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)

2.               berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.



·              Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.







Contoh 1 (Masalah Penukaran uang):

Persoalan: Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?



Contoh: tersedia koin-koin 1, 5, 10, dan 25

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 koin dengan nilai sebesar mungkin dari himpunan koin yang tersisa dengan syarat (kendala) tidak melebihi nilai uang yang ditukarkan.



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



Langkah 1: pilih 1 buah koin 25  (Total = 25)



Langkah 2: pilih 1 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!)





Pada setiap langkah di atas kita memperoleh optimum lokal, dan pada akhir algoritma kita memperoleh optimum global (yang pada contoh ini merupakan solusi optimum).








Tag : MATA KULIAH
0 Komentar untuk "Algoritma Greedy"

INFO NEWS UPDATE

loading...
Back To Top