ALGORITMA
GREEDY
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 merupakan jenis algoritma yang
menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum
sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan
istilah local maximum. Pada kebanyakan kasus, algoritma greedy tidak akan
menghasilkan solusi paling optimal, begitupun algoritma greedy biasanya
memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat. Greedy
sendiri diambil dari bahasa inggris yang artinya rakus, tamak atau serakah
.Prinsip algoritma greedy adalah: “take what you can get now!”.
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.
Persoalan optimasi (optimization problems): persoalan
yang menuntut pencarian solusi optimum. Persoalan optimasi ada dua macam:
Maksimasi (maximization) dan Minimasi (minimization)
Solusi optimum (terbaik) adalah solusi yang bernilai
minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.
Elemen persoalan optimasi: kendala (constraints) dan fungsi
objektif (atau fungsi optiamsi).
Solusi yang memenuhi semua kendala disebut solusi layak
(feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut
solusi optimum.
Studi kasus Algoritma Greedy
Mari kita lihat sebuah
masalah klasik yang sering dijumpai dalam kehidupan sehari-hari: mencari jarak
terpendek dari peta. Misalkan kita ingin bergerak dari titik A ke titik B, dan
kita telah menemukan beberapa jalur dari peta:
