Algoritma Greedy

Algoritma Greedy

• 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 bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.

·           Elemen persoalan optimasi:

1.       kendala (constraints)

2.       fungsi objektif (atau fungsi optimasi)

·           Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi 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:

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

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

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:

procedure greedy(input C: himpunan_kandidat;                  output S : himpunan_solusi) { menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy   Masukan: himpunan kandidat C   Keluaran: himpunan solusi S } Deklarasi        x : kandidat; Algoritma:        S¬{}                               { inisialisasi S dengan kosong }        while (belum SOLUSI(S)) and (C ¹ {} ) do        x¬SELEKSI(C);            { pilih sebuah kandidat dari C}        C¬ C - {x}      { elemen himpunan kandidat berkurang satu }             if LAYAK(S È {x}) then                 S¬S È {x}           endif      endwhile {SOLUSI(S) sudah diperoleh or C = {} }

      

• Pada akhir setiap lelaran, solusi yang terbentuk adalah optimum lokal. Pada akhir kadang while-do diperoleh optimum global.
• Namun adakalanya optimum global merupakan solusi sub-optimum atau pseudo-optimum. Alasan:

1.      algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada metode exhaustive search).  

2.      pemilihan fungsi SELEKSI: Mungkin saja terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma bekerja dengan benar dan menghasilkan solusi yang benar-benar optimum

·           Karena itu, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum.

·           Jika jawaban terbaik mutlak (benar-benar optimum) tidak diperlukan, maka algoritma greedy sering berguna untuk menghasilkan solusi yang menghampiri (approximation) optimum, daripada menggunakan algoritma yang lebih rumit untuk menghasilkan solusi yang eksak.

·           Bila algoritma greedy optimum, maka keoptimalannya itu dapat dibuktikan secara matematis

(Sekali Lagi) Masalah Penukaran Uang

Misalkan koin-koin dinyatakan dalam himpunan-ganda (multiset) {d₁, d₂, …, d_n}. 

Solusi persoalan dinyatakan sebagai tupel X = {x₁, x₂, …, x_n}, sedemikian sehingga x_i = 1 jika d_i dipilih, atau x_i = 0 jika d_i tidak dipilih. Misalkan uang yang akan ditukar dengan sejumlah koin adalah A.

Obyektif persoalan adalah

            Minimisasi  F =                        (fungsi obyektif)

            dengan kendala

Algoritma Exhaustive Search

• Karena setiap elemen X = {x₁, x₂, …, x_n} adalah 0 atau 1, maka terdapat 2ⁿ kemungkinan nilai X. 
• Waktu yang dibutuhkan untuk mengevaluasi fungsi obyektif adalah O(n), oleh karena itu kompleksitas algoritma exhaustive search untuk masalah ini adalah O(n × 2ⁿ ). 

Pemecahan Masalah dengan Algoritma Greedy

• Strategi greedy yang digunakan dalam memilih koin berikutnya:  

Pada setiap langkah, pilihlah koin dengan nilai sebesar mungkin dari himpunan koin yang tersisa dengan syarat tidak melebihi nilai uang yang ditukarkan.

• Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan himpunan koin dalam urutan yang menurun (nonincreasing order).

• Jika himpunan koin sudah terurut menurun, maka kompleksitas algoritma greedy adalah O(n). Jika waktu pengurutan diperhitungkan, maka kompleksitas algoritma greedy ditentukan dari kompleksitas algoritma pengurutan.
• Apakah algoritma greedy untuk masalah penukaran uang ini selalu menghasilkan solusi optimum? Jawabannya: tidak selalu, bergantung pada koin mata uang yang digunakan.

Contoh 2.

(a) Koin: 5, 4, 3, dan 1

     Uang yang ditukar = 7.

Solusi dengan algoritma greedy:

            7 = 5 + 1 + 1                           ( 3 koin) à tidak optimal

Solusi yang optimal: 7 = 4 + 3            ( 2 koin)

(b)  Koin: 10, 7, 1

       Uang yang ditukar: 15

Solusi dengan algoritma greedy:  

            15 = 10 + 1 + 1 + 1 + 1 + 1     (6 koin)

Solusi yang optimal: 15 = 7 + 7 + 1    (hanya 3 koin)

(c) Koin: 15, 10, dan 1

     Uang yang ditukar: 20

Solusi dengan algoritma greedy:

            20 = 15 + 1 + 1 + 1 + 1 + 1     (6 koin)

Solusi opgtimal: 20 = 10 + 10             (2 koin)

• Untuk sistem mata uang dollar AS, euro Eropa, dan crown Swedia, algoritma greedy selalu memberikan solusi optimum. Misalnya untuk menukarkan $6,39 dengan uang kertas (bill) dan koin sen (cent), kita dapat memilih:

·         Satu buah uang kertas senilai $5        

·         Satu buah uang kertas senilai $1 ($5 + $1 = $6))

·         Satu koin  25 sen         ($5 + $1 + 25^c = $6,25)

·         Satu koin 10 sen          ($5 + $1 + 25^c + 10^c = $6,35)

·         Empat koin 1 sen        ($5 + $1 + 25^c + 10^c + 1^c + 1^c + 1^c + 1^c = $6,39)

Bagaimana dengan mata uang rupiah Indonesia?

9.500 = 5000 + 2000 + 2000 + 500

155.700 = 100.000 + 50.000 + 5.000 +500 + 200

Minimisasi Waktu di dalam Sistem (Penjadwalan)

Persoalan: Sebuah server (dapat berupa processor, pompa, kasir di bank, dll) mempunai n pelanggan (customer, client) yang harus dilayani. Waktu pelayanan untuk setiap pelanggan sudah ditetapkan sebelumnya, yaitu pelanggan i membutuhkan waktu t_i. Kita ingin meminimumkan total waktu di dalam sistem,

            T = (waktu di dalam sistem untuk pelanggan i)

Karena jumlah pelanggan adalah tetap, meminimumkan waktu di dalam sistem ekivalen dengan meminimumkan waktu rata-rata.

Contoh 3. Misalkan kita mempunyai tiga pelanggan dengan

            t₁ = 5,   t₂ = 10,             t₃ = 3,

maka enam urutan pelayanan yang mungkin adalah:

Urutan             T 

=================================                                                

1, 2, 3: 5 + (5 + 10) + (5 + 10 + 3 ) = 38

1, 3, 2:             5 + (5 + 3) + (5 + 3 + 10) = 31

2, 1, 3: 10 + (10 + 5) + (10 + 5 + 3) = 43

2, 3, 1: 10 + (10 + 3) + (10 + 3 + 5) = 41

3, 1, 2: 3 + (3 + 5) + (3 + 5 + 10) = 29 ¬ (optimal)

3, 2, 1: 3 + (3 + 10) + (3 + 10 + 5) = 34

Pemecahan Masalah dengan Algoritma Exhaustive Search

• Urutan pelangan yang dilayani oleh server merupakan suatu permutasi
• Jika ada n orang pelanggan, maka tedapat n! urutan pelanggan. Waktu yang dibutuhkan untuk mengevaluasi fungsi obyektif adalah O(n), oleh karena itu kompleksitas algoritma exhaustive search untuk masalah ini adalah O(nn!)

Pemecahan Masalah dengan Algoritma Greedy

Strategi greedy untuk memilih pelanggan berikutnya adalah:

·         Pada setiap langkah, masukkan pelanggan yang membutuhkan waktu pelayanan terkecil di antara pelanggan lain yang belum dilayani.

• Agar proses pemilihan pelanggan berikutnya optimal, maka perlu mengurutkan waktu pelayanan seluruh pelanggan dalam urutan yang menaik. Jika waktu pengurutan tidak dihitung, maka kompleksitas algoritma greedy untuk masalah minimisasi waktu di dalam sistem adalah O(n).

procedure PenjadwalanPelanggan(input n:integer) { Mencetak informasi deretan pelanggan yang akan diproses oleh server tunggal   Masukan: n pelangan, setiap pelanggan dinomori 1, 2, …, n   Keluaran: urutan pelanggan yang dilayani }                       Deklarasi    i : integer Algoritma:   {pelanggan 1, 2, ..., n sudah diurut menaik berdasarkan ti}   for i¬1 to n do      write(‘Pelanggan ‘, i, ‘ dilayani!’)   endfor

Pemilihan srategi greedy untuk penjadwalan pelanggan akan selalu menghasilkan solusi optimum. Keoptimuman ini dinyatakan dengan Teorema 3.1 berikut:

Teorema 3.1. Jika t₁ £ t₂ £ … £ t_n maka pengurutan i_j = j,  1 £ j £ n meminimumkan

                               T =           

untuk semua kemungkinan permutasi i_j.

Persoalan Knapsack

(a)  0/1 Knapsack

maksimasi F =

                                    dengan kendala (constraint)                 

                          

yang dalam hal ini, x_i = 0 atau 1,    i = 1, 2, …, n

Algoritma Exhaustive Search

• Algoritma exhaustive search untuk persoalan 0/1 Knapsack mempunyai kompleksitas O(n × 2ⁿ). 

Algoritma Greedy

• Masukkan objek satu per satu ke dalam knapsack. Sekali objek dimasukkan ke dalam knapsack, objek tersebut tidak bisa dikeluarkan lagi.
• Terdapat beberapa strategi greedy yang heuristik yang dapat digunakan untuk memilih objek yang akan dimasukkan ke dalam knapsack:

1. Greedy by profit.

Pada setiap langkah, knapsack diisi dengan objek yang mempunyai keuntungan terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu.

2. Greedy by weight..

Pada setiap langkah, knapsack diisi dengan objek yang mempunyai berat paling ringan. Strategi ini mencoba memaksimumkan keuntungan dengan memasukkan sebanyak mungkin objek ke dalam knapsack.

3.  Greedy by density.

Pada setiap langkah, knapsack diisi dengan objek yang mempunyai densitas, p_i /w_i terbesar.  Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar.

• Pemilihan objek berdasarkan salah satu dari ketiga strategi di atas tidak menjamin akan memberikan solusi optimal. Bahkan ada kemungkinan ketiga stategi tersebut tidak memberikan solusi optimum. Contoh 4 berikut memberikan ilustrasi kedua kasus ini.

Contoh 4.  Tinjau persoalan 0/1 Knapsack dengan n = 4.                  w₁ = 6;    p₁ = 12

                        w₂ = 5;    p₁ = 15

                        w₃ = 10;  p₁ = 50

                        w₄ = 5;    p₁ = 10

                        Kapasitas knapsack W = 16

Solusi dengan algoritma greedy:

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi /wi	profit	Weight	density
1	6	12	2	0	1	0	0
2	5	15	3	1	1	1	1
3	10	50	5	1	0	1	1
4	5	10	2	0	1	0	0
Total bobot				15	16	15	15
Total keuntungan				65	37	65	65

• Pada contoh ini, algoritma greedy dengan strategi pemilihan objek berdasarkan profit dan density memberikan solusi optimal, sedangkan pemilihan objek berdasarkan berat tidak memberikan solusi optimal.

Tinjau persoalan 0/1 Knapsack lain dengan 6 objek:

w₁ = 100;  p₁ = 40

                        w₂ = 50;    p₂ = 35

                        w₃ = 45;    p₃ = 18

                        w₄ = 20;    p₄ = 4

w₅ = 10;    p₅ = 10

                        w₆ = 5;      p₆ = 2

                        Kapasitas knapsack W = 100

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi /wi	profit	weight	density
1	100	40	0,4	1	0	0	0
2	50	35	0,7	0	0	1	1
3	45	18	0,4	0	1	0	1
4	20	4	0,2	0	1	1	0
5	10	10	1,0	0	1	1	0
6	5	2	0,4	0	1	1	1
Total bobot				100	80	85	100
Total keuntungan				40	34	51	55

           

• Pada contoh ini, algoritma greedy dengan ketiga strategi pemilihan objek tidak berhasil memberikan solusi optimal.  Solusi optimal permasalah ini adalah X = (0, 1, 1, 0, 0, 1) dengan total keuntungan = 55.

Kesimpulan: Algoritma greedy tidak selalu berhasil menemukan solusi optimal untuk masalah 0/1 Knapsack.

(b)  Fractional Knapsack

Serupa dengan persoalan 0/1 Knapsack di atas, tetapi

0 £ x_i £ 1, untuk   i = 1, 2, …, n

maksimasi F =   

            dengan kendala (constraint)                 

                          

yang dalam hal ini, 0 £ x_i £ 1,  i = 1, 2, …, n

Algoritma Exhaustive Search

• Oleh karena 0 £ x_i £ 1, maka terdapat tidak berhingga nilai-nilai x_i. Persoalan Fractional Knapsack menjadi malar (continuous) sehingga tidak mungkin dipecahkan dengan algoritma  exhaustive search.     

Pemecahan Masalah dengan Algoritma Greedy

• Ketiga strategi greedy yang telah disebutkan di atas dapat digunakan untuk memilih objek yang akan dimasukkan ke dalam knapsack.

Contoh 5. Tinjau persoalan fractional knapsack dengan n = 3.

                        w₁ = 18;    p₁ = 25

                        w₂ = 15;    p₁ = 24

                        w₃ = 10;    p₁ = 15

                        Kapasitas knapsack W = 20

Solusi dengan algoritma greedy:

Properti objek				Greedy by
i	wi	pi	pi /wi	profit	Weight	density
1	18	25	1,4	1	0	0
2	15	24	1,6	2/15	2/3	1
3	10	15	1,5	0	1	1/2
Total bobot				20	20	20
Total keuntungan				28,2	31,0	31,5

• Penyelesaian persoalan knapsack yang memakai strategi pemilihan objek berdasarkan p_i /w_i terbesar memberikan keuntungan yang maksimum (optimum).
• Solusi optimal persoalan knapsack di atas adalah X = (0, 1, 1/2) yang memberikan keuntungan maksimum 31,5.
• Agar proses pemilihan objek berikutnya optimal, maka kita perlu mengurutkan objek terlebih dahulu berdasarkan p_i /w_i dalam urutan yang menurun,  sehingga objek berikutnya yang dipilih adalah objek sesuai dalam urutan itu.
• Algoritma persoalan fractional knapsack:

    1. Hitung harga p_i/w_i , i = 1, 2, ..., n

    2. Urutkan seluruh objek berdasarkan nilai p_i/w_i yang menurun

    3. Panggil SolveFractinonalKnapsack untuk mencari solusi optimum.

procedure SolveFractionalKnapsack(input p, w, : Tabel,                              W : real, n : integer,                                                output x : Tabel, TotalUntung : real) { Penyelesaian persoalan fractional knapsack dengan algoritma greedy yang menggunaka strategi pemilihan objek berdasarkan density (pi/wi)  Asumsi: Sebelum pemanggilan SolveFractionalKnapsack, harus dilakukan prosedur pendahuluan sebagai berikut :   1. Hitung harga pi/wi , i = 1, 2, ..., n   2. Urutkan seluruh objek berdasarkan nilai pi/wi yang menurun   3. Baru kemudian panggil procedure SolveFractionalKnapsack ini } Deklarasi     i         : integer;     kapasitas : real;     MasihMuatUtuh : boolean; Algoritma:    for i¬1 to n do       xi ¬ 0   { inisialisasi setiap fraksi objek i dengan 0 }         endfor    kapasitas¬W  { kapasitas knapsack awal }    TotalUntung¬0    i¬1    MasihMuatUtuh¬true    while (i £ n) and (MasihMuatUtuh) do      if wi £ kapasitas then         xi¬1         TotalUntung¬TotalUntung + pi         kapasitas¬kapasitas - wi          i¬i+1;      else              MasihMuatUtuh¬false      endif    endwhile    { i > n or not MasihMuatUtuh }    if i £ n then   { objek terakhir yang akan dimasukkan}       xi ¬ kapasitas/wi       TotalUntung¬TotalUntungt + xi*pi    endif

• Kompleksitas waktu asimptotik algoritma di atas (dengan mengabaikan waktu pengurutan objek) adalah O(n).
• Algoritma greedy untuk persoalan fractional knapsack dengan strategi pemilihan objek berdasarkan p_i /w_i terbesar akan selalu memberikan solusi optimal. Hal ini dinyatakan dalam Teorema 3.2 berikut ini.

Teorema 3.2. Jika p₁/w₁ ³ p₂/w₂ ³ ... ³ p_n/w_n maka algoritma greedy dengan strategi pemilihan objek berdasarkan p_i /w_i terbesar menghasilkan solusi yang optimum.

Latihan:

Sebuah kapal besar akan diisi dengan muatan. Muatan tersebut disimpan di dalam peti kemas dan tiap peti kemas berukuran sama, tetapi berat peti kemas (yang sudah berisi muatan) berbeda belum tentu sama. Misalkan w_i adalah berat peti kemas ke-i, 1 £ i £ n. Kapasitas kapal membawa muatan adalah C. Kita ingin memuat kapal sehingga jumlah peti kemas yang diangkut maksimum. Seperti soal nomor  satu, rumuskan persoalan ini dengan metode greedy. Lakukan perhitungan untuk n = 8, dengan w = (100, 200, 50, 90, 150, 50, 20, 80), dan C = 400.