Algoritma Greedy: Pengertian ,Jenis dan Contoh Program

Pengertian Algoritma Greedy

Algoritma Greedy adalah pendekatan dalam pemrograman yang memecahkan persoalan optimasi dengan cara yang tampaknya rakus. Pendekatan ini berfokus pada pengambilan keputusan sekarang dengan harapan bahwa setiap langkah akan membawa kita lebih dekat ke solusi akhir yang optimal.

Dalam konteks greedy, kita selalu memilih opsi yang paling menguntungkan saat ini tanpa mempertimbangkan konsekuensi di masa depan. Ini mirip dengan mengambil sejumlah uang tunai yang tersedia dari mesin ATM tanpa memikirkan bagaimana pengeluaran itu akan memengaruhi saldo akhir .

Kegunaan Algoritma Greedy

Kegunaan utama dari algoritma greedy adalah untuk menemukan solusi optimal dalam persoalan optimasi dengan cepat. Pendekatan ini sangat berguna dalam banyak kasus di mana kita perlu memaksimalkan atau meminimalkan sesuatu dengan cara yang efisien. Contoh penerapannya termasuk perencanaan jadwal, pengkodean data, manajemen sumber daya, dan banyak lagi.

Jenis-Jenis Algoritma Greedy

Terdapat beberapa jenis algoritma greedy yang digunakan dalam berbagai konteks. Beberapa di antaranya termasuk:

1. Huffman Coding

Digunakan dalam kompresi data. Ini adalah metode yang efisien untuk mengurangi ukuran data dengan mengassign kode biner yang lebih pendek untuk karakter yang lebih sering muncul dalam teks.

2. Activity Selection

Algoritma ini digunakan dalam manajemen waktu dan penjadwalan. Ketika Anda memiliki sejumlah kegiatan dengan waktu mulai dan selesai yang berbeda, algoritma ini membantu Anda memilih sejumlah kegiatan yang tidak saling tumpang tindih untuk mendapatkan jadwal yang paling efisien.

3. Kruskal Algorithm

Digunakan dalam masalah pohon minimal (Minimum Spanning Tree) pada grafik. Ini membantu menemukan subset dari semua edge dalam grafik yang membentuk pohon tanpa siklus dengan total bobot yang minimal.

4. Prim’s Algorithm

Seperti Kruskal, Prim’s Algorithm juga digunakan dalam masalah pohon minimal, tetapi fokus pada membangun pohon dari satu simpul awal dengan memilih edge terkecil yang terhubung.

Contoh Program Algoritma Greedy

Berikut adalah contoh sederhana implementasi algoritma greedy dalam bahasa Python untuk menyelesaikan masalah Fractional Knapsack:

def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[1] / x[0], reverse=True)
    knapsack = []
    total_value = 0

    for item in items:
        if capacity >= item[0]:
            knapsack.append(item)
            total_value += item[1]
            capacity -= item[0]
        else:
            fraction = capacity / item[0]
            knapsack.append((item[0] * fraction, item[1] * fraction))
            total_value += item[1] * fraction
            break

    return knapsack, total_value

# Contoh penggunaan
items = [(2, 10), (3, 5), (5, 15), (7, 7), (1, 6)]
capacity = 15
result, total = fractional_knapsack(items, capacity)
print("Barang yang dipilih:", result)
print("Total nilai yang diperoleh:", total)

Masalah Sehari-Hari yang Menggunakan Prinsip Greedy

Prinsip greedy digunakan dalam banyak masalah sehari-hari, seperti:

1. Manajemen Keuangan Pribadi: Ketika Anda harus memutuskan bagaimana mengalokasikan anggaran bulanan Anda, Anda mungkin akan memilih untuk membayar utang dengan suku bunga tertinggi terlebih dahulu (pendekatan “utang tertinggi terlebih dahulu”).
2. Rute Perjalanan: Saat merencanakan perjalanan dengan anggaran terbatas, Anda mungkin akan memilih untuk mengunjungi tempat-tempat yang memberikan pengalaman terbaik dengan biaya terendah.
3. Penjadwalan Pekerjaan: Dalam sebuah proyek, Anda mungkin akan memilih tugas-tugas yang paling penting atau memiliki prioritas tertinggi untuk dikerjakan terlebih dahulu.

Kelebihan dan Kelemahan Utama Algoritma Greedy

Kelebihan:

1. Sederhana dan Cepat: Algoritma greedy relatif mudah dipahami dan diimplementasikan, dan sering kali memiliki kinerja yang cepat.
2. Solusi Terdekat: Algoritma ini cenderung menghasilkan solusi yang cukup mendekati optimal dalam waktu yang singkat.

Kelemahan:

1. Tidak Selalu Optimal: Algoritma greedy tidak selalu menghasilkan solusi optimal. Ada kasus di mana solusi yang dihasilkan jauh dari solusi terbaik.
2. Pemilihan Kriteria: Kegagalan dalam pemilihan kriteria rakus yang tepat dapat mengakibatkan hasil yang tidak optimal.
3. Pengabaian Konsekuensi Masa Depan: Algoritma ini tidak mempertimbangkan konsekuensi jangka panjang dari setiap langkah, sehingga dapat menghasilkan solusi yang suboptimal dalam beberapa kasus.