Makalah algoritma metode Greedy

Algoritma Metode “Greedy”

Disusun oleh      :

1.       Bagus Panji Syahputro

2.       Rodiatul Ardi

3.       Wahyu Nuril

4.       Johan Renaldi

5.       Dede Yusdika

6.       Mahardi

7.       Dimas Fatwa Mufti

8.       Ajeng AL

9.       Winda Wahyuni

10.   Nia Tri Selvia

11.   Muhammad Rafly

12.   Bentua Simbolon

…………………………………………………………………………………………………….  

A. PENDAHULUAN

Algoritma adalah langkah dalam mencari solusi atas sebuah masalah. Banyak sekali algoritma yang dapat kita gunakan dalam membangun sebuah program, salah satunya adalah algoritma greedy.

Algoritma Greedy adalah algoritma yang berusaha memecahkan masalah dengan cara mengambil pilihan terbaik atau solusi optimum yang di peroleh saat itu tanpa mempertimbangkan kosekwensi yang diterimanya kemudian. Dengan kata lain algoritma Greedy berusaha mencari solusi optimum local dan berharap dari optimum-optium local ini ditemukan optimum globalnya.

B.  PEMBAHASAN

Proses Kerja Metode Greedy

           

Untuk menyelesaikan suatu permasalahan dengan n input data yang terdiri dari beberapa fungsi pematas dan satu fungsi tujuan yang diselesaikan dengan memilih beberapa solusi yang mungkin (feasible solution/feasible sets), yaitu bila telah memenuhi fungsi tujuan/obyektif.

Prinsip Algoritma Greedy adalah algoritma yang memecahkan masalah langkah per langka, pada setiap langkah :

1.       Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan “Take what you can get now!”.

2.       Berharap bahwa dengan memilih optimum local pada setiap langkah akan berakhir dengan optimum global.

Skema umum dari algoritma greedy disusun oleh elemen-elemen sebagai berikut :

a)      Himpunan Kandidat

Himpunan ini berisi elemen-elemen pembentuk solusi.

b)      Himpunan Solusi

Himpunan ini berisi bagian dari himpunan kandidat yang terpilih sebagai solusi perosalan.

c)       Fungsi Seleksi

Fungsi ini adalah fungsi yang pada setiap langkah memilih solusi yang paling memungkinkan mencapa solusi optimal.

d)      Fungsi Kelayakan

Fungsi ini memasukkan kandidat-kandidat yang layak dari himpunan kandidat ke himpunan solusi.

e)      Fungsi Obyektif

Yaiuti fungsi yang memaksimumkan atau meminimumkan nilai solusi.

C.  ISI

·      Metode Greedy digunakan untuk dalam penyelesaian masalah :

a)   Optimal Storage on Tapes Problem

b)   Knapsack Problem

c)    Minimum Spanning Tree problem

d)   Shortest Path Problem

A.   Optimal Storage on Tapes Problem

Ø Permasalahan bagaimana mengoptimalisasikan storage/memory dalam komputer agar data yang tersimpan dalam komputer dapat termuat dengan optimal.

Ø Misalkan terdapat n program yang akan disimpan didalam pita(tape). Pita tersebut mempunyai panjang maksimal sebesar L, masing-masing program yang akan disimpan mempunyai panjang L1,L2,L3,….Ln. Cara penyimpanan adalah penyimpanan secara terurut (sekuensial).

·      Proses Pemecahanya :

Ø Nilai panjang data (L), waktu penyimpanan (t) dan waktu  rata-rata (MRT) jika ada.

Ø Tentukan urutan penyimpanan datanya.

Ø Hitung total penyimpanan (jika ada kapasitas media penyimpanan maka total tidak boleh melebihi).

Ø Pilih total yang minimum (sesuai dengan unsur efisiensi dan efektifitas).

·      Contoh :

            Diketahui 3 program yang akan disimpan dalam media penyimpanan dengan panjang masing-masing 5, 10, dan 3. Bagaimana proses penyimpanan yang optimal dengan metode greedy.

Jawab :

Tentukan nilai panjang, waktu, dan waktu rata-rata Ada 3 program, dimisalkan panjangnya

L1, L2, dan L3 dengan nilai L1=5, L2=10, dan L3=3

Waktu, disini tidak diketahui, berarti dianggap waktu tidak mempengaruhi proses

penyimpanan, berarti tidak ada waktu rata-rata.

Berarti dalam kasus ini yang berpengaruh hanya panjang dari setiap datanya.

Urutan penyimpanan dengan menggunakan teknik faktorial sesuai dengan jumlah data.

Dari kasus diketahui jumlah data (n) adalah 3, berarti kombinasi yang dibutuhkan adalah n!,

yaitu 3!=3*2*1 = 6. Jadi dibutuhkan 6 langkah dalam proses penyusunannya.

No   Order       D(L)       Total

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

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

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

4   2,3,1           10+(10+3)+(10+3+5)                 41

5   3,1,2           3+(3+5)+(3+5+10)                     29

6   3,2,1           3+(3+10)+(3+10+5)                   34

Ket. No:1 :  Order 1 = 5

Order 1, 2 =5+10

Order 1,2,3 = 5+10+3

Jadi Total Order 1,2,3 = 5+(5+10)+(5+10+3)

Dari nilai di atas didapat nilai minimal adalah

Nilai terkecil pertama adalah 29, yaitu untuk posisi penyimpanan urutan ke-3 pada posisi

pertama

Nilai terkecil kedua adalah 31, yaitu untuk posisi penyimpanan urutan ke-1 pada posisi

pertama

Nilai terkecil ketiga bukan 34 dan 38, sebab urutan penyimpanan pada posisi ke-3 dan ke-1

sudah diwakili oleh 29 dan 31, sehingga untuk urutan ketiga adalah 41.

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

Knapsack 0/1

Knapsack 0/1, Yaitu Suatu Objek Diambil Seluruh Bagiannya Atau Tidak Sama Sekali.

Cara Terbaik Agar Menguntungkan : Bukan Hanya Dari Hasilnya Optimal Tetapi Juga

Banyaknya Langkah Yang Dibutuhkan

Diberikan N Buah Objek Dan Sebuah Knapsack Dengan  Kapasitas  Bobot  W.

Setiap  Objek    Memiliki Properti Bobot (Weigth) Wi Dan Keuntungan(Profit) Pi.

Persoalan  Adalah  Memilih  Memilih  Objek-Objek    Yang    Dimasukkan    Ke    Dalam   

Knapsack Sedemikian Sehingga  Memaksimumkan Keuntungan. Total   Bobot   Objek   Yang 

Dimasukkan   Ke Dalam   Knapsack   Tidak   Boleh   Melebihi   Kapasitas Knapsack.

Solusi  Persoalan  Dinyatakan  Sebagai  Vektor N :

X = {X1, X2, …  , Xn}

Xi = 1 Jika Objek Ke-I Dimasukkan Ke Dalam Knapsack,

Xi = 0 Jika Objek Ke-I Tidak Dimasukkan.

Persoalan  0/1  Knapsack  Dapat  Kita  Pandang  :

Sebagai   Mencari   Himpunan   Bagian   (Subset)   Dari  Keseluruhan Objek Yang Muat Ke Dalam Knapsack Dan Memberikan Total Keuntungan Terbesar.

Penyelesaian Dengan Greedy:

1.    Greedy By Profit

Pada Setiap Langkah Knapsack Diisi Dengan Obyek Yang Mempunyai Keuntungan Terbesar.

Strategi Ini Mencoba Memaksimumkan Keuntungan Dengan Memilih Objek Yang Paling

Menguntungkan  Terlebih Dahulu.

Pertama Kali Dilakukan Adalah Menurutkan Secara Menurun Obyek-Obyek Berdasarkan

Profitnya .  Kemudian Obyek-Obyek Yang Dapat Ditampung Oleh Knapsack Diambil Satu

Persatu Sampai Knapsack Penuh Atau (Sudah Tidak Ada Obyek Lagi Yang Bisa Dimasukan).

Data Awal :

W1  = 6;    P1  = 12

W2  = 5;    P2  = 15

W3  = 10;  P3  = 50

W4  = 5;    P4  = 10

Kapasitas Knapsack W = 16

2.    Greedy By Wight

Pada Setiap Langkah, Knapsack Diisi Dengan Objek Yang Mempunyai Berat Paling

Ringan.  Strategi Ini Mencoba Memaksimumkan Keuntungan Dengan Memasukan

Sebanyak Mungkin Objek Kedalam Knapsack.

Pertama Kali Yang Dilakukan Adalah Mengurutkan Secara Menaik Objek-Objek

Berdasarkan Weight-Nya. Kemudian Obyek-Obyek Yang Dapat Ditampung Oleh

Knapsack Diambil Satu Persatu Sampai Knapsack Penuh Atau (Sudah Tidak Ada

Obyek Lagi Yang Bisa Dimasukan).

3.    Greedy By Density

Pada Setiap Langkah, Knapsack Diisi Dengan Obyek Yang Mempunyai Densitas

Terbesar (Perbandingan Nilai Dan Berat Terbesar).

Strategi Ini Mencoba Memaksimumkan Keuntungan Dengan Memilih Objek Yang

Mempunyai Keuntungan Per Unit Berat Terbesar.

Pertama Kali Yang Dilakukan Adalah Mencari Nilai Profit Per Unit/ Density Dari Tiap

Tiap Objek. Kemudian Obyek-Obyek Diurutkan Berdasarkan Densitasnya.

Kemudian Obyek-Obyek Yang Dapat Ditampung Oleh Knapsack Diambil Satu Persatu

Sampai Knapsack Penuh Atau (Sudah Tidak Ada Obyek Lagi Yang Bisa Dimasukan).

Perbandingan Hasil:

Penggunaan 3 Strategi Diatas Tidak Menjamin Akan Memberikan Solusi Optimal.

Contoh :

Kapasitas M=20, dengan jumlah barang =3

Berat Wi masing-masing barang (W1,W2,W3) à (18,15,,10)

Nilai Profit masing-masing barang (P1,P2,P3) à (25,24,15)

Pilih Barang dengan nilai profit maksimal

P1=25 à x1=1.  batas atas nilai

P2=24 à x2=2/15.

P3=15 à x3 =0. batas bawah nilai.

Pilih barang dengan berat minimal

W1= 18  à x1=0.  batas bawah

W2=15  à x2 = 2/3

W3=10 à x3=1. batas atas.

Pilih barang dengan menghitung perbandingan yang terbesar dari profit dibagi Berat

(Pi/Wi) diurut secara tidak naik.

P1/w1=25/18   (1.38)  à x1=0. karena terkecil x1=0

P2/w2=24/ 15   (1.6)à x2=1.    karena terbesar x2=1

P3/w3=15/10  (1.5)à x3=1/2    dicari dengan fungsi pembatas x3=1/2.

Buat Tabel

Nilai profit maksimal  = 31.5.

C.   Minimum Spanning Tree Problem

Permasalahan umum dari minimum spanning tree adalah mencari minimum biaya (cost) spanning tree dari setiap ruas (edge) suatu graph yang membentuk pohon (tree).

Dalam mendapatkan solusi yang diharapkan maka akan dipilih ruas menurut kriteria

optimisasi yang menghasilkan biaya minimum. Dengan demikian penambahan jumlah

biayanya relatif kecil dari setiap ruas yang telah terpilih dan membentuk spanning tree.

Untuk masalah minimum spanning tree, syarat graph dapat dicari minimum spanning

treenya adalah :

·      Graph harus terhubung

·      Ruasnya punya bobot / nilai

·      Graphnya tidak berarah

Algoritma yang dapat dipakai untuk menentukan minimum spanning tree adalah :

·      Algoritma Solin

·      Algoritma Kruskal

·      Algoritma Prim’s

1.    Algoritma Solin

Suatu Graph G, seperti gambar di bawah ini.Ini adalah graf berbobot awal. Graf ini bukan

pohon karena ada sirkuit. Nama yang lebih tepat untuk diagram ini adalah Graf atau

Network. Angka-angka dekat garis penghubung/ruas adalah bobotnya. Nilai bobot dari Graf

tesebut adalah : 86

Kita akan mencari MST dengan menggunakan Algoritma Solin dan Kruskal untuk Graf G

diatas.

Penyeselaian :

1.    Urutkan Ruas Graf (G) menurut bobotnya dari bobot yang terbesar sampai bobot yang

terkecil.

Bobot RUAS

15 D,E

9 B,D E,F

8 B,C B,E F,G

7 A,D C,E

6 A,B E,G

5 D,F

1.    Lakukan penghapusan masing-masing ruas yang tidak menyebabkan graf menjadi tidak

terhubung atau membentuk sirkuit.

Kita mulai melakukan tahapan penghapusan dengan ruas dengan nilai bobot

terbesar sampai bobot terkecil :

Tahap Penghapusan Selesai, Gambar 6 adalah Minimun Spanning Tree dari Graf G

dengan Nilai Bobot : 56

2.    Algoritma Kruskal

Untuk mencari pohon rentang minimum dari graph dengan algoritma yang ditemukan

Kruskal, mula-mula semua garis dalam graph diurut berdasarkan bobotnya dari kecil ke

besar. Kemudian pilih garis dengan bobot terkecil. Pada setiap langkah dipilih garis dengan

bobot terkecil, tetapi tidak membentuk loop garis-garis yang sudah dipilih terdahulu.

Dengan Graph yang sama, kita akan mencari Minimun Spanning Tree dengan algoritma

Kruskal.

1. Mula-mula kita buat Graf G hanya terdiri dari Simpul saja.

Urutkan Ruas dari bobot kecil ke besar (DF, AB, EG, AD, CE, BC, BE, FG, BD,

EF,DE), kemudian berdasarkan urutan tersebut, kita menambahkan ruas dengan

mencegah terbentuknya sirkuit.

D.   Shortest Path Problem

·      Permasalahan = menghitung jalur terpendek dari sebuah graph berarah.

·      bagaimana mencari sebuah jalur pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut.

Ada beberapa macam persoalan lintasan terpendek,

Antara lain:

1.    Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).

2.    Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).

3.    Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shoertes path).

4.    Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).

Kriteria utk permasalahan jalur terpendek/SP problem tsb :

1.    Setiap ruas pd graph hrs mpy nilai (label graph)

2.    Setiap ruas pd graph tdk hrs terhubung (unconnected)

3.    Setiap ruas pd graph tsb hrs mempunyai arah (graph berarah).

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

E.    KESIMPULAN

Algoritma Greedy tidak beroperasi secara menyeluruh terhadap semua alternative solusi yang ada (sebagaimana pada metode exhaustive search)

Terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algorita menghasilkan solusi optimal.

Kesimpulan

Jadi, pada sebagian masalah, metode greedy tidak selalu berhasil memberika solusi yang optimal.

Kelebihan dan kelemahan metode greedy :

Kelebihan

Kompleksitas ruangnya rendah. Memori yang dibutuhkan tidak besar, karena langkah sebelumnya tidak disimpan. Kita terus memperhatikan langkah di depan saja. Sehingga sangat kecil kemungkinan mengalami masalah ketersediaan memori.

Mudah diimplementasikan, algoritma greedy sangat mudah untuk diimplementasikan pada persoalan-persoalan yang ada.

Kompleksitas waktunya rendah, sehingga jarang mengalami masalah dalam lamanya waktu pencarian langkah.

Kelemahan

Hasilnya belum tentu optimal

Hanya mencari solusi terbaik saat itu, padahal belum tentu terbaik untuk langkah berikutnya.