Metode Greedy

Metode greedy adalah metode yang digunakan untuk memecahkan persoalan optimasi, ada 2 macam persoalan optimasi, yaitu maksimasi dan minimasi, artinya dengan metode greedy kita bemaksud mencari solusi terbaik, yaitu solusi yang benilai minimum atau maksimum dari sekumpulan alternatif solusi yang ada. Arti kata greedy sendiri adalah RAKUS, namun maksud dari metode greedy adalah solusi yang kita dapat setelah melakukan metode itu adalah solusi yang maksimal dan optimal.

Solusi optimal itu sendiri biasanya memiliki arti bagaimana kita mendapat jalan pintas dengan hasil maksimal atau sesuai dengan apa yang kita inginkan. Metode greedy dapat digunakan untuk mendapat solusi optimal namun perlu digarisbawahi bahwa metode greedy juga harus bergantung pada kondisi yang ditentukan. Oleh karena itu metode greedy tidak bisa selalu diterapkan untuk mendapat solusi optimal. Metode ini mempunyai 2 indikator yaitu tujuan dan batasan. Rumus umunya adalah

PROCEDURE GREEDY (data, batasan)
Solusi = 0

FOR I = 1 TO batasan DO
      X = SELECT (data)
      IF FEASIBLE (Solusi, X)
           THEN Solusi = UNION (Solusi, X)
      END IF
REPEAT
RETURN (Solusi)
END GREEDY

Ket :

SELECT = Print variabel

FEASIBLE = Penyeleksian kondisi

UNION = Penggabungan variabel

Untuk lebih jelasnya masuk ke contoh soal saja.

Himpunan A merupakan himpunan pasangan terurut (x,y), yaitu {(2,1),(3,2),(7,1), dan (1,0)}. Dari data-data tersebut akan ditentukan suatu pasangan terurut yang memiliki jumlah x dan y yang minimum. Adapun batasan dari x dan y masing-masing lebih besar dari nol.

Solusi = 0

N = 1 : x=2 > 0

            Y=1 > 0          FEASIBLE (solusi, x)

            Solusi = {(2,1)}

N = 2 : x=3 > 0

             Y=2 > 0         FEASIBLE (solusi, x)

            Solusi = {(2,1),{3,2)}

N = 3 : x=7 > 0

            Y = 1 > 0        FEASIBLE (solusi, x)

            Solusi = {(2,1),(3,2),(7,1)}

N = 4 : x = 1  > 0

            Y  = 0 > 0       TIDAK FEASIBLE

            Solusi = {(2,1),{3,2),(7,1)}

Dari himpunan solusi yang mungkin tersebut diperoleh solusi yang optimal  (dalam hal ini minimum) adalah (2,1) yang jumlahnya sebesar 2 + 1 = 3.

Jadi solusi optimal = (2,1)

Metode Greedy banyak digunakan dalam berbagai penyelesaian masalah, antara lain adalah :

1. Optimal Storage on Tapes Problem 
2. Kanpsack Problem
3.  Minimum Spanning Tree Problem
4. Shortest Path Problem