Algoritma Greedy

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.

a. 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.

b. 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.

c. 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.

 

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

Skema Umum Algoritma Greedy

Algoritma greedy disusun oleh elemen-elemen berikut:

1.       Himpunan kandidat.

Berisi elemen-elemen pembentuk solusi.

2.       Himpunan solusi

     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, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain). 

Contoh pada masalah penukaran uang, elemen-elemen algoritma greedy-nya adalah:

1.       Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.

2.       Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.

3.       Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.

4.       Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.

5.       Fungsi obyektif: jumlah koin yang digunakan minimum.

Pseudo-code algoritma greedy adalah sebagai berikut:

 

Algoritma Rekursif

Fungsi rekursi menghitung pangkat

function pangkat(input a,p:integer)->integer

 if p=0 then

   Pangkat <- 1

 else

   Pangkat <- a*pangkat(a,p-1)

 endif

endfunction

Menghitung kompleksitas fungsi pangkat

Operasi dasar utama : perkalian

T(p) => 0        ,p = 0

      => 1+T(p-1)

 = 1+1+T(p-2)= 2+T(p-2)

 = 1+1+1+T(p-2)= 3+T(p-3)

        = .......

        = n + T(0)

 = n + 0

 = O(n)

Source : http://onlygreatshare.blogspot.co.id/2015/03/program-pascal-pemangkatan-menggunakan.html

Fungsi rekursi menghitung jumlah deret aritmatika dengan beda 5

 function deret(input a:integer)->integer

 if a=1 then

   deret <- 1

 else

   deret <- 5*a+deret(a-1)

 endif

 endfunction

Menghitung kompleksitas fungsi deret dengan beda 5

Operasi dasar utama : penjumlahan

T(p) => 0        ,p = 0

      => 1+T(p-1)

 = 1+1+T(p-2)= 2+T(p-2)

 = 1+1+1+T(p-2)= 3+T(p-3)

        = .......

        = n + T(0)

 = n + 0

 = O(n)

Source : http://resstylulla.blogspot.co.id/2011/11/fungsi-rekursif.html

Fungsi rekursi menghitung jumlah deret bilangan ganjil

function deret(input a:integer)->integer

if a=1 then

   deret <- 1

else

   deret <- a+deret(a-2)

endfunction

Menghitung kompleksitas fungsi deret ganjil

Operasi dasar utama : penjumlahan

T(p) => 0        ,p = 0

      => 1+T(p-1)

 = 1+1+T(p-2)= 2+T(p-2)

 = 1+1+1+T(p-2)= 3+T(p-3)

        = ......

        = n + T(0)

 = n + 0

 = O(n)

Source menghitung :

http://phg-simulation-laboratory.com/wp-content/uploads/2016/02/M06Kompleksitas-Waktu-untuk-Algoritma-Rekursif.pdf

Program Indeks Nilai

1. Big Oh (O)

a. Apakah Tmax(n) = 8n + 2 € O(n)

  8n + 2  ≤  8n + 2n  (untuk semua n ≥ 1)

  8n + 2  ≤  10n

  c = 10, n_{0 =} 1 

      Tmax(n) termasuk anggota O(n).

b. Apakah Tmin(n) = 4n + 2 € O(n)

  4n + 2  ≤  4n + 2n  (untuk semua n ≥ 1)

  4n + 2  ≤  6n

  c = 6, n_{0 =} 1 

      Tmin(n) termasuk anggota O(n).

c. Apakah Taverage(n) = 6n + 1 € O(n)

  6n + 1  ≤  6n + n  (untuk semua n ≥ 1)

  6n + 1  ≤  7n

  c = 7, n_{0 =} 1 

      Taverage(n) termasuk anggota O(n).

2. Big Omega (Ω)

a. Apakah Tmax(n) = 8n + 2 € Ω(n)

  8n + 2  ≥   n  (untuk semua n ≥ 0)

  8n + 2  ≥   n

  c = 1, n_{0 =} 0 

      Tmax(n) termasuk anggota Ω(n).

b. Apakah Tmin(n) = 4n + 2 € Ω(n)

  4n + 2  ≥   n  (untuk semua n ≥ 0)

  4n + 2  ≥   n

  c = 1, n_{0 =} 0 

      Tmin(n) termasuk anggota Ω(n).

c. Apakah Taverage(n) = 6n + 1 € Ω(n)

  6n + 1  ≥   n  (untuk semua n ≥ 0)

  6n + 1  ≥   n

  c = 1, n_{0 = 0} 

      Taverage(n) termasuk anggota Ω(n).

3. Big Theta (Θ)

a. Apakah Tmax(n) = 8n + 2 € Θ(n)

*batas atas

  8n + 2  ≤  8n + 2n  (untuk semua n ≥ 1)

  8n + 2  ≤  10n   

*batas bawah

  8n + 2  ≥   n  (untuk semua n ≥ 0)

  8n + 2  ≥   n

c_{1 =} 10, c_{2 =} 1, n_{0 =} 1

      Tmax(n) termasuk anggota Θ(n).

b. Apakah Tminn) = 4n + 2 € Θ(n)

*batas atas

  4n + 2  ≤  4n + 2n  (untuk semua n ≥ 1)

  4n + 2  ≤  6n   

*batas bawah

  4n + 2  ≥   n  (untuk semua n ≥ 0)

  4n + 2  ≥   n

c_{1 =} 6, c_{2 =} 1, n_{0 =} 1

      Tmin(n) termasuk anggota Θ(n).

c. Apakah Taverage(n) = 6n + 1 € Θ(n)

*batas atas

  6n + 1  ≤  6n + n  (untuk semua n ≥ 1)

  6n + 1  ≤  7n   

*batas bawah

  6n + 1  ≥   n  (untuk semua n ≥ 0)

  6n + 1  ≥   n

c_{1 =} 7, c_{2 =} 1, n_{0 =} 1

      Taverage(n) termasuk anggota Θ(n).

Procedure SeqSearchWithSentinel

a.  Big Oh (O)

T(n) ≤ c.g(n)

Tmin (n) = 1

1 ≤ 1 n (dengan n ≥ 1)

1 ≤ 1 (1)

1 ≤ 1

c = 1, n₀ = 1, maka Tmin (n) adalah anggota dari Big O

Tmax(n) = n

n ≤ n (dengan n ≥ n)

0 ≤ 0

c = n, n₀ = 0, maka Tmax (n) adalah anggota dari Big O

Tavrg(n) = (n + 1)/2

(n + 1)/2  ≤ n(n + 1)/2

((1)+1)/2 ≤ (1)((1)+1)/2

1≤1

c = (n+1)/2 , n₀ = 1, maka Tavg (n) adalah anggota dari Big O

b. Big Omega (Ω)

T(n) ≥ c.g(n)

Tmin (n) = 1

1 ≥ 1 n (dengan n ≥ 0)

1 ≥ 1 (0)

1 ≥ 0

c = 0, n₀ = 0, maka Tmin (n) adalah anggota dari Big Omega

Tmax(n) = n

n ≥ n (dengan n≥n)

0≥ 0

c = n, n₀ = 0, maka Tmax (n) adalah anggota dari Big O

Tavrg(n) = (n + 1)/2

(n + 1)/2  ≥ n(n + 1)/2

((1)+1)/2 ≥ (1)((1)+1)/2

1≥1

c = (n+1)/2 , n₀ = 1, maka Tavg (n) adalah anggota dari Big O

c. Big Theta

c₂g(n) ≤ t (n) ≤ c₁g(n)

Tmin (n) = 1

Bagian atas :

1 ≤ 1 n (dengan n ≤ 1)

1 ≤ 1 (1)

1 ≤ 1

Bagian bawah :

1 ≥ 1 n (dengan n ≥ 0)

1 ≥ 1 (0)

1 ≥ 0

c₁ = 1, c₂ = 0, n₀ = 1, maka Tmin (n) adalah anggota dari Big Theta

Tmax (n) = n

Bagian atas :

n ≤ n (dengan n ≥ n)

0≤ 0

Bagian bawah :

n ≥ n (dengan n≥n)

0≥ 0

c1 = 0, c2 = 0, n₀ = 1, maka Tmax (n) adalah anggota dari Big Theta

Tavg (n) = (1+2+3)/3 = 2

Bagian atas :

(n + 1)/2  ≤ n(n + 1)/2

((1)+1)/2 ≤ (1)((1)+1)/2

1≤1

Bagian bawah :

(n + 1)/2  ≥ n(n + 1)/2

((1)+1)/2 ≥ (1)((1)+1)/2

1≥1

c1 = 1, c2 = 1, n₀ = 1, maka Tavg (n) adalah anggota dari Big Theta

Big O, Big Omega, dan Big Theta

1. Fungsi Cek Password

a. Big Oh (O)

T(n) ≤ c.g(n)

Tmin (n) = 1

1 ≤ 1 n (dengan n ≥ 1)

1 ≤ 1 (1)

1 ≤ 1

c = 1, n₀ = 1, maka Tmin (n) adalah anggota dari Big O

Tmax (n) = 3

3 ≤ 3 n (dengan n ≥ 1)

3 ≤ 3 (1)

3 ≤ 3

c = 3, n₀ = 1, maka Tmax (n) adalah anggota dari Big O

Tavg (n) = (1+2+3)/3 = 2

2 ≤ 2 n (dengan n ≥ 1)

2 ≤ 2 (1)

2 ≤ 2

c = 2, n₀ = 1, maka Tavg (n) adalah anggota dari Big O

b. Big Omega (Ω)

T(n) ≥ c.g(n)

Tmin (n) = 1

1 ≥ 1 n (dengan n ≥ 0)

1 ≥ 1 (0)

1 ≥ 0

c = 0, n₀ = 0, maka Tmin (n) adalah anggota dari Big Omega

Tmax (n) = 3

3 ≥ 3 n (dengan n ≥ 0)

3 ≥ 3 (0)

3 ≥ 0

c = 3, n₀ = 0, namun pada saat n > 1, 3 tidak lebih besar sama dengan c.g(n), sehingga Tmax (n) bukan anggota dari Big Omega

Tavg (n) = (1+2+3)/3 = 2

2 ≥ 2 n (dengan n ≥ 0)

2 ≥ 2 (0)

2 ≥ 0

c = 2, n₀ = 0 , namun pada saat n > 1, 2 tidak lebih besar sama dengan c.g(n), sehingga Tavg bukanlah anggota dari Big Omega

c. Big Theta

c₂g(n) ≤ t (n) ≤ c₁g(n)

Tmin (n) = 1

Bagian atas :

1 ≤ 1 n (dengan n ≤ 1)

1 ≤ 1 (1)

1 ≤ 1

Bagian bawah :

1 ≥ 1 n (dengan n ≥ 0)

1 ≥ 1 (0)

1 ≥ 0

c₁ = 1, c₂ = 0, n₀ = 1, maka Tmin (n) adalah anggota dari Big Theta

Tmax (n) = 3

Bagian atas :

3 ≤ 3 n (dengan n ≤ 1)

3 ≤ 3 (1)

3 ≤ 3

Bagian bawah :

3 ≥ 3 n (dengan n ≥ 0)

3 ≥ 3 (0)

3 ≥ 0

c1 = 3, c2 = 0, n₀ = 1, maka Tmax (n) adalah anggota dari Big Theta

Tavg (n) = (1+2+3)/3 = 2

Bagian atas :

2 ≤ 2 n (dengan n ≤ 1)

2 ≤ 2 (1)

2 ≤ 2

Bagian bawah :

2 ≥ 2 n (dengan n ≥ 0)

2 ≥ 2 (0)

2 ≥ 0

c1 = 2, c2 = 0, n₀ = 1, maka Tavg (n) adalah anggota dari Big Theta