METODE GREEDY

METODE  GREEDY

   A.    Pengertian Metode Greddy

Metode  greedy adalah salah satu jenis algoritma, Metode  greedy menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara dalam setiap langkah atau local maxium.

Metode ini banyak digunakan dalan berbagai penyelesaian masalah

 antara lain adalah :                              

      1.      Optimal Storage On Tape problem

·         Bagaimana mengoptimalkan penyimpanan, agar data yang disimpan dapat termuat dengan optimal.

·         Bagaimana susunan yang harus dibentuk.

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

     3.      Minimum Spanning Tree Problem

Permasalahan umum dari minimum spanning tree adalah mencari minimum biaya (cost) spanning tree dari setiap ruas (edge) suatu graph yang mebentuk pohon (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

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

4.      Fungsi kelayakan (feasible)

5.      Fungsi objektif yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).