Algoritma Greedy

Implementasi Algoritma Greedy @ Agoritma greedy mirip algoritma yg memecahkan masalah langkah per langkah, pada setiap langkah membuat pilihan optimum (local optimum) pada setiap langkah dg harapan bahwa langkah berikutnya mengarah ke solusi optimum global (global optimum).

Algoritma greedy membuat keputusan berdasarkan pilihan yg ada sekarang, tidak melihat pilihan yg akan muncul kemudian. krn itulah algoritma greedy dikategorikan dlm algoritma yg ‘berpandangan pendek’ & tidak dpt diulang krn keputusan yg telah diambil pada suatu langkah tidak dpt diubah lagi pada langkah selanjutnya. Padahal dlm permasalahan optimasi terdpt banyak pilihan yg perlu dieksplorasi pada setiap langkah solusi.

Terkadang algoritma greedy mengambil keputusan yg diambil terlalu dini tanpa melihat yg akan ditemui berikutnya sehingga menimbulkan apa yg disebut “good next move, bad overall move”. Melihat kelemahan yg dimiliki, solusi optimum global yg didapatkan belum tentu merupakan solusi optimum (terbaik), tetapi sub-optimum / pseudo-optimum. krn algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternative solusi yg ada.

Namun begitu algoritma ini tetap mengambil pilihan utama untuk permasalahan yg sederhana krn ini mrp metode yg paling cepat dibanding metode yg lain & dpt memberikan solusi hampiran / aproksimasi terhadap nilai optimum yg diinginkan serta hasil yg diberikan masih merupakan solusi yg layak (feasible solution). Algoritma yg termasuk ke dlm tipe algoritma greedy antara lain kode Huffman,algoritma Dijkstra, algoritma Prim, & algoritma Kruskal yg ketiganya digunakan dlm menyelesaikan permasalahan optimasi pada graf.

Algoritma greedy merupakan salah satu dari sekian banyak algoritma yg sering di pakai dlm implementasi sebuah system / program yg menyangkut mengenai pencarian “optimasi”.

Berikut algoritmanya,

1.      Kelompokkan semua jalur (edge).

2.      Pilih jalur yang terpendek kemudian masukkan ke dalam himpunan solusi.

3.      Apakah sudah ada N jalur pada solusi? Jika tidak, ulangi langkah 2.

Dalam membentuk solusi, algoritma greedy pada setiap langkahnya akan mengambil pilihan yang merupakan optimum lokal atau pilihan yang sesuai dengan spesifikasi pembuat algoritma. Dengan pengambilan pilihan yang sesuai pada setiap langkah ini diharapkan solusi yang didapat optimum global atau sesuai keinginan pembuat algoritma. Pada setiap langkah algoritma greedy, kita akan mendapat optimum lokal. Bila algoritma berakhir maka diharapkan optimum lokal ini akan menjadi optimum global. Sehingga sebenarnya algoritma greedy mengasumsikan bahwa optimum lokal ini merupakan bagian dari optimum global.

Algoritma Greedy merupakan algoritma yang lazim untuk memecahkan persoalan optimasi meskipun hasilnya tidak selalu merupakan solusi yang optimum. Sesuai arti harafiah, Greedy berarti tamak. Prinsip utama dari algoritma ini adalah mengambil sebanyak mungkin apa yang dapat diperoleh sekarang. Untuk memecahkan persoalan dengan algoritma Greedy, kita memerlukan elemen-elemen sebagai berikut.

a. Himpunan Kandidat (C)

Himpunan ini berisi elemen-elemen pembentuk solusi.

b. Himpunan Solusi, (S)

Himpunan ini berisi kandidat yang terpilih sebagai solusi persoalan. Dengan kata lain, himpunan solusi adalah himpunan bagian dari himpunan kandidat.

c. Fungsi Seleksi

Fungsi seleksi merupakan fungsi yang ada pada setiap langkah memilih kandidat yang paling memungkinkan guna mencapai solusi optimal.

d. Fungsi Kelayakan (Feasible)

Fungsi kelayakan adalah fungsi yang memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak dan tidak melanggar batasan atau constraints yang ada.

e. Fungsi Objektif

Fungsi objektif adalah fungsi yang memaksimumkan atau meminimumkan nilai solusi.

Skema umum algoritma Greedy adalah sebagai berikut:

1.      Inisialisasi S dengan kosong.

2.      Pilih sebuah kandidat C dengan fungsi seleksi.

3.      Kurangi C dengan kandidat yang sudah dipilih dari langkah (b) di atas.

4.      Periksa apakah kandidat yang dipilih tersebut bersama-sama dengan himpunan solusi membentuk solusi yang layak atau feasible (dengan fungsi kelayakan).

5.      Periksa apakah himpunan solusi sudah memberikan solusi yang lengkap serta optimal (dengan fungsi objektif).

Di dlm mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu:

1.      Maksimasi (maxizimation)

2.    Minimasi (minimization)

3.      Sekarang kita lanjut ke contoh soal yg aja ya..biar lebih enak membedakan antara soal mengenai optimasi/maksimasi dg minimum/minimasi.

4.     1.Persoalan maksimasi

5.      ( MasalahPenukaranUang): Diberikan uang senilai A. Tukar A dg koin-koin yg ada. Berapa jumlah minimum koin yg diperlukan untuk penukaran tersebut?

6.     2. Persoalan minimasi

7.      Contoh1: tersedia banyak koin 1, 5, 10, 25
•Uang senilai A= 32 dpt ditukar dg banyak cara berikut:

8.      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)

Sebelum ditutup artikel tentang algoritma greedy ini saya akan menjelaskan tentang apa yg di pakai algoritma greddy

Dalam memecahkan masalah:

Algoritma greedy dlm menyelesaikan masalah dg langkah per langkah “bertahap”
Dengan definisi,
Pada setiap langkah algoritma greedy :

1. mengambil pilihan yg terbaik yang

      dpt diperoleh pada saat itu tanpa
Memperhatikan konsekuensi kedepan
(prinsip“take what you can get now!”)

2. berharap bahwa dg memilih optimum

     Local pada setiap langkah akan berakhir dg optimum global.

CONTOH SOAL PERHITUNGAN

      CONTOH PENERAPAN GREEDY DI DALAM TRANSPORTASI

Pada tabel 1 terdapat sebuah alat angkut dengan dengan kapasitas 100 kg terdapat 4 buah barang dengan ukuran sebagai berikut :

 

     Maka dengan menggunakan algoritma Greedy diperoleh Tabel 2 sebagai berikut :

    Keterangan :

      GBW : Greedy By Weight
GBP : Greedy By Profit
GBD : Greedy By Density
0 : Barang tidak diangkut
1 : Barang diangkut

      Algoritma:

1.  for i <- 1 to n do

2.  x[i] <- 0 { inisialisasi setiap status pengambilan objek i dengan 0 }

3.  endfor

4.  i <- 0

5.  TotalBobot <- 0

6.  Available <- true

7.  while (i < n) and (Available) do

8.  { cek objek ke-i }

9.  i <- i + 1

10. if TotalBobot + w[i] <- K then

11. { masukkan objek Ci ke dalam knapsack }

12. x[i] <- 1

13. TotalBobot <- TotalBobot + w[i]

14. else

15. Available <- false

16. x[i] <- 0

17. { objek Ci tidak dimasukkan ke dalam

18. knapsack }

19. endif

20. endwhile

21. { i > n or not Available }

22. return x

23.  

24.  

Gambar 2 menggambar Flowchart sistem secara umum untuk implementasi algoritma Greedy pada Knapsack problem

Sumber :
   http://www.metode-algoritma.com/2013/02/contoh-program-algoritma-greedy.html

Read More

Analisis Matematis Rekursif

Binary Search Recursive

FUNCTION BinarySearch(input a1,a2,..., an: array of integer, i:integer, j:integer, cari:integer) KAMUS i, j, mid : integer ketemu : boolean i ← 1 j ← n ALGORITMA if (i <= j) then        mid ← (i + j) / 2         if (cari = a[mid]) then               return mid // data ditemukan           else if (cari < a[mid]) then              return BinarySearch(a, i, mid - 1, cari)           else              return BinarySearch(a, mid + 1, j, cari)           endif       endif    return -1 // tidak ditemukan
Operator Utama =
Tmax(n)=log n	Tavg(n)=log n	Tmin(n)=1

Quick Sort

FUNCTION partition (input/output a :    array[1..n] of integer, input x,y :    integer, output p,q : integer) KAMUS    pivot, temp : integer ALGORITMA    pivot ← a [(x+y) div 2]    p ← x    q ← y repeat    while (a[p] < pivot) do        p ← p + 1    endwhile    while (pivot < a[q]) do        q ← q – 1    endwhile    if (p <= q) then        temp ← a[p]        a[p] ← a[q]        a[q] ← temp        p ← p + 1        q ← q – 1    endif until (p > q) FUNCTION quicksort (input/output a :    array [1..n] of integer, input x,y :    integer) KAMUS    k : integer ALGORITMA    if (x < y) then        partition(a,x,y,k)        quicksort(a,x,k)        quicksort(a,k+1,y)    endif
Operator Utama <
Tmax(n)= n log n	Tavg(n)= n log n	Tmin(n)=1

MaksMin

Procedure MaksMin (Input M :TabelInt, a, b, c : integer output Mn, Mks : integer) KAMUS      Mn1, Mn2, Mks1, Mks2 : integer ALGORITMA      if a=b then                Mn←Ma                Mks←Ma              elsed              if (a=b-1) then                 if Ma < Mb then                         Mks←Mb                         Mn←Ma                 else                         Mks←Ma                         Mn←Mb                 endif      else                c ←(a+b) div 2                MnMks2(M, a, c, Mn1, Mks1)                MnMks2(M, c+1, Mn2, Mks2)                If Mn1 <  Mn2 then                         Mn←Mn1                Else                         Mn←Mn2                   Endif                If Mks1<Mks2 then                          Mks←Mks1                Else                          Mks←Mks2                Endif

T(n)=0    , n=1       =1    , n =2       =2T(n/2) + 2 .  n > 2

T(n) = 3n / 2 - 2

Fibonacci

Procedure fibonacci(Input n : integer) KAMUS ALGORITMA  If n <= 1 then      return n  else      return fibonacci(n - 1) + fibonacci(n - 2)  endif

Operator Utama : + T(n) = 0 untuk n <= 1 T(n) = T(n-1) + T(n-2) untuk n > 1 Substitute : T(n-1) = T(n-2) + T(n-3) T(n-2) = T(n-3) + T(n-4) T(n) = [ T(n-2) + T(n-3) ] + [ T(n-3)+T(n-4) ] T(n) = O(2n-1) + O(2n-2) + O(1) T(n) = O(2n)

Read More