Contoh Algoritma Greedy Dan Penyelesaiannya

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.

Skema umum Algoritma Greedy

Algoritma greedy disusun oleh elemen, dan elemen-elemen yang digunakan dalam penerapan algoritma greedy antara lain :

Himpunan yang berisi elemen pembentuk solusi.

Himpunan yang terpilih sebagai solusi persoalan.

Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal.

Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada.

Fungsi yang mengembalikan nilai boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap.

Fungsi yang mengoptimalkan solusi.

Di dalam mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu:

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 .

Masalah Sehari-Hari yang Menggunakan Prinsip Greedy

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

Pengertian Metode atau Algoritma Greedy

Metode/Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah 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.

Contoh Program Algoritma Greedy

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

Jenis-Jenis Algoritma Greedy

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

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.

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.

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.

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.

Kelebihan dan Kelemahan Utama Algoritma Greedy

Pengertian Metode Greedy Dan 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 metode yang paling populer untuk memecahkan persoalan optimasi. Greedy sendiri diambil dari bahasa inggris yang artinya rakus, tamak atau serakah .Prinsip algoritma greedy adalah: “take what you can get now!”.

– Memilih beberapa jenis investasi (penanaman modal) – Mencari jalur tersingkat dari Bandung ke Surabaya – Memilih jurusan di Perguruan Tinggi – Bermain kartu remi

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) danfungsi objektif(atau fungsi optiamsi)

Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum. Untuk LA kali ini saya akan menjelaskan program pengambilan koin, yang menggunakan algoritma greedy. Bahasa pemrograman yang saya gunakan adalah bahasa C++, dan software yang digunakan adalah borland C.

Keep your knowledge by sharing to everyone

Contoh Pseudocode Algoritma Greedy

• Contoh (1) : tinjau masalah penukaran uang.

(a) Koin: 5, 4, 3, dan 1

Uang yang ditukar = 7.

Solusi greedy: 7 = 5 + 1 + 1 ( 3 koin) → tidak optimal

Solusi optimal: 7 = 4 + 3 ( 2 koin)

(b) Koin: 10, 7, 1

Uang yang ditukar: 15

Solusi greedy: 15 = 10 + 1 + 1 + 1 + 1 + 1 (6 koin)

Solusi optimal: 15 = 7 + 7 + 1 (hanya 3 koin)

Uang yang ditukar: 20

Solusi greedy: 20 = 15 + 1 + 1 + 1 + 1 + 1 (6 koin)

Solusi optimal: 20 = 10 + 10 (2 koin)

Penyelesaian dengan exhaustive search

— Terdapat 2n kemungkinan solusi

(nilai-nilai X = {x1, x2, …, xn} )

— Untuk mengevaluasi fungsi obyektif = O(n)

— Kompleksitas algoritma exhaustive search seluruhnya = O(n × 2n ).

Strategi greedy: Pada setiap langkah, pilih koin dengan nilai terbesar dari himpunan koin yang tersisa

menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy

Masukan: himpunan kandidat C

Keluaran: himpunan solusi S

while (∑(nilai semua koin didalam S) ≠ A) and (C ≠ {} ) do

x ← Koin yang mempunyai nilai terbesar

if (∑ (nilai semua koin didalam S) + nilai koin x ≤ A then

if (∑ (nilai semua koin didalam S) = A then

write (“tidak ada solusi”)

procedure PenjadwalanPelanggan(input n:integer)

{ Mencetak informasi deretan pelanggan yang akan diproses oleh server tunggal

Masukan: n pelangan, setiap pelanggan dinomori 1, 2, …, n

Keluaran: urutan pelanggan yang dilayani

{pelanggan 1, 2, …, n sudah diurut menaik berdasarkan ti}

write(‘Pelanggan ‘, i, ‘ dilayani!’)

• Contoh (3) : Algoritma Greedy mencari jarak terpendek dari peta

Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta.

Untuk mencari jarak terpendek dari A ke B, sebuah algoritma greedy akan menjalankan langkah-langkah seperti berikut:

Kunjungi satu titik pada graph, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang. 1 Cari local maximum ke titik selanjutnya. 2 Tandai graph sekarang sebagai graph yang telah 3 dikunjungi, dan pindah ke local maximum yang telah ditentukan. 4 Kembali ke langkah 1 sampai titik tujuan didapatkan.

Dengan menggunakan algoritma greedy pada graph di atas hasil akhir jarak terpendek adalah ACDEFB. Hasil jarak terpendek ini sbenarnya tidak tepat dengan jarak pendek sebenarnya(A-G-E-F-B). Maka dari aalgoritma yang tidak selamanya benar namu algoritma yang mendekati nilai kebenaran.

Pemecahan Masalah dengan Algoritma Greedy

Strategi greedy untuk memilih job:

Pada setiap langkah, pilih job i dengan

pi yang terbesar untuk menaikkan nilai

(p1, p2, p3, p4) = (50, 10, 15, 30)

(d1, d2, d3, d4) = (2, 1, 2, 1)

Solusi optimal: J = {4, 1} dengan F = 80.

Function JobSchedulling(input C : himpunan_job) → himpunan_job

{menghasilkan barisan job yang akan diproses oleh mesin}

J: himpunan_job {solusi}

i ← job yang mempunyai p [i] terbesar

if (semua job di dalam J ᴜ {i} layak) then

Prinsip Utama Algoritma Greedy

Prinsip utama algoritma greedy adalah “take what you can get now!”. Maksud dari prinsip tersebut adalah sebagai berikut: Pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Sebagai contoh, jika kita manggunakan algoritma Greedy untuk menempatkan komponen diatas papan sirkuit, sekali komponen telah diletakkan dan dipasang maka tidak dapat dipindahkan lagi. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir.