Sabtu, 03 Desember 2016

ALGORITMA GREEDY

           No comments   
Secara Harfiah Greedy artinya rakus atau tamak, sifat yang berkonotasi negatif. Orang yang memiliki sifat ini akan mengambil sebanayak mungkin atau mengambil yang paling bagus atau yang paling mahal. Sesuai dengan arti tersebut, Prinsip Greedy adalah take what you can get now. Dalam kehidupan sehari hari Greedy dapat digunakan dalam masalah seperti :
1.      Memilih beberapa jenis investasi.
2.      Mencari jalur tersingkat dari Bandung ke Surabaya.
3.      Memilih jurusan di Perguruan Tinggi
4.      Bermain Kartu Remi
5.      Memilih spesifikasi komputer yang terbaik dengan budget maksimum tertentu.

1.1          Definisi Algoritma Greedy

Algoritma greedy adalah langkah per langkah dalam mencari solusi atas sebuah masalah. 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. Algoritma greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai dalam implementasi sebuah system atau program yang menyangkut mengenai pencarian “optimasi”.

1.2          Personal Optimasi

Persoalan Optimasi adalah persoalan yang tidak hanya mencari sekedar solusi, tetapi mencari solusi terbaik. Dalam kehidupan sehari hari, banyak terdapat persoalan yang menuntut pencarian solusi optimum. Persoalan tersebut dinamakan persoalan optimasi(optimization Problems).

Persoalan optimasi ada dua macam :
        ·         Maksimasi (maximization)
        ·         Minimasi (minimization)

Contoh Persoalan Optimasi :
( Masalah Penukaran Uang): Diberikan uang senilai A = 32. Tukar A dengan koin-koin uang yang tersedia banyak koin 1, 5, 10, 25. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
              ·         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)

1.3          Solusi Optimasi

Solusi optimum adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.

1.4          Skema Umum Algoritma Greedy

Elemen-elemen algoritma greedy :

       1.     Himpunan kandidat, C
       Berisi elemen-elemen pembentuk solusi.
       2.     Himpunan solusi, S
       Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.
       3.      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.
       4.      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.
       5.      Fungsi obyektif
       Fungsi objektif yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi(misalnya            panjang lintasan, keuntungan, dan lain-lain).

      Contoh :
       Pada masalah penukaran uang:
a.       Himpunan kandidat, C : Himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
b.      Himpunan solusi, S : Total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.
c.       Fungsi seleksi: Pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
d.      Fungsi layak : Memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
e.       Fungsi obyektif: Jumlah koin yang digunakan minimum.

 

1.5          Skema Umum Algoritma Greedy Dalam Notasi Algoritma

             Skema Algoritma dapat dirumuskan sebagai berikut :
                                                   i.            Inisialisasi S dengan nilai kosong.
                                                  ii.            Pilih sebuah kandidat (dengan fungsi SELEKSI) dari C
                                                  iii.          Kurangi C dengan kandidat yang sudah dipilih dari langkah ii
                                                  iv.           Periksa apakah kandidat yang dipilih bersama” himpunan solusi membentuk solusi 
                                   yang layak (diperiksa oleh Fungsi FEASIBLE).
               Jika YA à masukkan kandidat ke himpunan solusi ,
               TIDAK à buang kandidat
                                                    v.            Periksa apakah himpunan solusi sudah memberikan solusi lengkap (dengan fungsi 
                                   SOLUSI)
               Jika YA à berhenti ,
               TIDAK à ulangi langkah ii

Skema umum algoritma greedy dalam pscedu-code :



        ·         Pada akhir setiap lelaran, solusi yang terbentuk adalah optimum lokal.

        ·         Pada akhir dikalangan while-do diperoleh optimum global.

         Referensi :

Knapsack Problem

           No comments   
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

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
Jawaban :

Kesimpulan : Pada soal ini, algoritma greedy dengan strategi pemilihan objek berdasarkan profit memberikan solusi optimal, sedangkan pemilihan objek berdasarkanweight dan density tidak memberikan solusi optimal.

Pseudo_code :


Sumber :

http://gbaruchkrisnanta.blogspot.co.id/2015/06/metode-greedy-divide-and-conquer.html?m=1

Algoritma Greedy

           No comments   

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


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.
       
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 Kasus:
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)




Pseudo Code:
function CoinExchange(input C : himpunan_koin, A : integer) -> himpunan_koin
{ mengembalikan koin-koin yang total nilainya = A,tetapi jumlah koinnya minimum}

Deklarasi
      S : himpunan_koin
      x : koin
  
Algoritma
S <-  {}
while (∑ (nilai semua koin di dalam S) ≠ A) and (C ≠ {} ) do
      x <- koin yang mempunyai nilai terbesar
      C <- C – {x}
      if  (∑ (nilai semua koin di dalam S) + nilai koin x < A then
            S <- S È  {x}
      endif
endwhile

if  (∑ (nilai semua koin di dalam S) = A  then
       return S
else
       write(“tidak ada solusi”)
endif

Referensi:

http://kurniadi-addi.blogspot.co.id/2015/07/materi-analisis-algortima-algoritma.html

Job Scheduling dengan Deadline

           No comments   


Greedy adalah sebuah algoritma untuk mencari solusi yang paling optimum yang mana bernilai maksimum pada setiap langkahnya, atau bisa juga disebut local maximum. Namun pada kebanyakan kasus, greedy tidak bisa menghasilkan nilai optimal, tapi biasanya bisa memberikan solusi yang mendekati nilai paling optimum.
Untuk skema umum algoritma greedy dalam pscedu-code, bisa dilihat di sini.
Kita bisa menemukan masalah sehari-hari yang dapat kita selesaikan dengan algoritma greedy.
Dari gambar di atas, diibaratkan huruf sebagai sebuah tempat yang berbeda dan jarak yang berbeda dengan garis sebagai jalur. Kita akan mencoba mencari jalur terpendek untuk bisa mengelilingi semua tempat dari posisi A dan kembali lagi ke posisi A, menggunakan algoritma greedy.
Dari semua tempat, pilih jarak terdekat dan tempat yang belum pernah dikunjungi kecuali akhir di saat kembali lagi ke titik awal.
A ke E ke D ke C ke B ke G ke F ke A
9 + 12 + 13 + 14 + 11 + 10 + 15 = 84

Kita berharap dengan menggunakan algoritma greedy kita bisa mendapatkan nilai yang optimum. Namun nyatanya algoritma greedy hanya mengambil pilihan terbaik pada tiap langkahnya tanpa memikirkan apa yang akan terjadi selanjutnya. Padahal jika kita menggunakan exhaustive search (solusi optimal), kita bisa mendapatkan nilai yang lebih optimum.

A ke E ke F ke G ke B ke C ke D ke A
9 + 13 + 10 + 11 + 14 + 13 + 12 = 82

Jadi tidak selamanya algoritma tersebut benar, namun masih bisa dikatakan mendekati nilai kebenaran.

Pemecahan Masalah dengan Algoritma Greedy
Strategi greedy untuk memilih job:    
                        Pada setiap langkah, pilih job i dengan
                        pi yang terbesar untuk menaikkan nilai
                        fungsi obyektif F.
Contoh:
(p1, p2, p3, p4) = (50, 10, 15, 30)
(d1, d2, d3, d4) = (2, 1, 2, 1)

 

Solusi optimal: J = {4, 1} dengan F = 80.

 
Kompleksitas algoritma greedy : O(n2).

Kesimupulan
Algoritma greedy merupakan algoritma yang bersifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu medapatkan solusi terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistem real-time atau game.
Dari implementasi yang kita lakukan, dapat dilihat bagaimana algoritma greedy memiliki beberapa fungsionalitas dasar, yaitu:
  1. Fungsi untuk melakukan penelusuran masalah.
  2. Fungsi untuk memilih local maximum dari pilihan-pilihan yang ada tiap langkahnya.
  3. Fungsi untuk mengisikan nilai local maximum ke solusi keseluruhan.
  4. Fungsi yang menentukan apakah solusi telah didapatkan.
Tentunya fungsi-fungsi di atas juga dapat digabungkan atau dipecah lebih lanjut lagi, menyesuaikan dengan strategi greedy yang dikembangkan.

Referensi: