26 Februari 2016

Algoritma Greedy

Algoritma Greedy
Algoritma Greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.
Persoalan optimasi (optimization problems) yaitu persoalan yang menuntut pencarian solusi optimum.
Persoalan optimasi hanya ada dua macam:
                1. Maksimasi (maximization)
                2. Minimasi (minimization)

Contoh algorita greedy

Algoritma Greedy - artikel

Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.
Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.

Greedy = rakus, tamak, loba
     
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

Contoh persoalan optimasi:
  ( Masalah Penukaran Uang): Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
Contoh 1: tersedia banyak koin 1, 5, 10, 25
Uang senilai A = 32 dapat ditukar dengan banyak 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)
                  … dst                
Minimum: 32 = 25 + 5 + 1 + 1       (4 koin)

Skema Umum Algoritma Greedy

Algoritma greedy disusun oleh elemen-elemen berikut:
Himpunan kandidat.
                Berisi elemen-elemen pembentuk solusi.
Himpunan solusi
                Berisi kandidat-kandidat yang terpilih sebagai solusi  persoalan.
Fungsi seleksi (selection function)
Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.

Fungsi kelayakan (feasible)
Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi.      

Baca juga >>  5 anime bergenre musik paling bagus

Fungsi obyektif, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).

Pada masalah penukaran uang:
Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.
Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
Fungsi obyektif: jumlah koin yang digunakan minimum

Contoh kasus algoritma greedy :
Misalkan tersedia koin : 1, 3, 5.
Uang senilai X=8 dapat di tukar dengan cara :
1+1+1+1+1+1+1+1 = 8 (8 koin)
1+1+1+1+1+3=8 (6 koin)
1+1+1+5=8 (4 koin)
1+1+3+3=8 (4 koin)
3+5=8 (2 koin)                                    solusi optimal.
Maka solusi optimal dari kasus penukaran koin di atas adalah 2 koin.

Knapsack Problem
Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.
Contoh kasus knapsack
w1 = 10;  p1 = 2
w2 = 5;     p2 = 3
w3 = 15;   p3 = 5
w4 = 7;     p4 = 7
w5 = 6;     p5 = 1
w6 = 18;   p6 = 4
w7 = 3;     p7 = 1
M = 15

Algoritma Greedy - artikel


Perhitungan kompleksitas waktu

Algoritma Greedy - artikel

Kompleksitas waktu algoritma = O(n).
T(n) = O(n)
Disebut algoritma linear, dimana waktu eksekusinya sebanding dengan jumlah data, dan merupakan kondisi optimal dalam membuat algoritma.
Contoh Program Pascal :
Begin
For I := 1 to n do
            Begin
            A:=A+1;
            End;
End.
Maka T(n) = O(n) karena program dieksekusi sejumlah n kali.
Jadi
Pengaruh jumlah data pada lama operasi
Karena Kompleksitas waktu algoritma = O(n).
Jadi jumlah data yang dimasukan akan mempengaruhi lama operasi program tesebut.
Karena O(n) berarti program dieksekusi sejumlah n kali.

Kesimpulan
Algoritma greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu mendapatkan solusi terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistem real-time atau game.

SHARE:
artikel 0 Replies to “Algoritma Greedy”
Riski
Lulusan S1 informatika, bekerja sebagai fulltime blogger, content writter, dan android developer... Berpengalaman bekerja dari sma, dan sekarang memilih menjalani usaha kecil kecilan.. pencinta musik folk, yang gemar membaca, menulis, dan membuat game...

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

This site uses Akismet to reduce spam. Learn how your comment data is processed.