Algoritma Greedy Beserta Contoh : Apa Itu, Metode dan Pendekatan

Apa itu Algoritma Greedy?

A Algoritma serakah Membagi sekumpulan sumber daya secara rekursif berdasarkan ketersediaan langsung maksimum dari sumber daya tersebut pada setiap tahap eksekusi.

Penyelesaian masalah dengan pendekatan greedy memiliki dua tahap:

1. Memindai daftar item
2. Optimization

Kedua tahapan berjalan secara paralel seiring dengan pembagian bertahap pada larik input.

Untuk mengikuti pendekatan greedy, pengetahuan dasar tentang rekursi dan pengalihan konteks akan sangat membantu Anda. trace kode tersebut. Paradigma greedy dapat dijelaskan dengan sepasang pernyataan yang diperlukan dan cukup.

Ada dua kondisi yang mendefinisikan paradigma serakah.

• Setiap pilihan bertahap harus mengarahkan masalah menuju solusi terbaik yang dapat diterima.
• Struktur masalah harus berhenti dalam sejumlah langkah serakah yang terbatas.

Dengan teori yang sudah dipahami, mari kita lihat sejarah di balik pendekatan pencarian serakah (greedy search).

Sejarah Serakah Algorithms

Berikut adalah tonggak-tonggak penting dalam sejarah algoritma greedy:

• Algoritma greedy pertama kali dikonseptualisasikan untuk algoritma graph walk pada tahun 1950-an.
• Edsger Dijkstra mengembangkan algoritma jalur terpendeknya untuk mempersingkat rute di ibu kota Belanda, Amsterdam.
• Pada dekade yang sama, Prim dan Kruskal mengembangkan strategi optimasi yang meminimalkan biaya jalur di sepanjang rute berbobot untuk membangun pohon rentang minimum.
• Pada tahun 70-an, para peneliti Amerika Cormen, Leiserson, Rivest, dan Stein menggambarkan substruktur rekursif dari solusi greedy dalam karya klasik mereka. Introduction to Algorithms buku pelajaran.
• Paradigma pencarian serakah dikatalogkan sebagai strategi optimasi yang berbeda dalam catatan NIST pada tahun 2005.
• Hingga saat ini, protokol web seperti Open Shortest Path First (OSPF) dan banyak protokol pengalihan paket menggunakan strategi greedy untuk meminimalkan waktu transit pada jaringan.

Strategi dan Keputusan yang Serakah

Logika tersebut bermuara pada pilihan biner di setiap tahap — "rakus" atau "tidak rakus" — berdasarkan arah yang diambil algoritma untuk maju.

Sebagai contoh, algoritma Dijkstra mengidentifikasi host di Internet dengan mengevaluasi fungsi biaya pada setiap langkah. Nilai yang dikembalikan oleh fungsi biaya menentukan apakah jalur selanjutnya bersifat "rakus" atau "tidak rakus".

Singkatnya, suatu algoritma berhenti menjadi serakah (greedy) saat mengambil langkah yang bukan merupakan langkah optimal lokal, dan masalah serakah (greedy problems) berhenti ketika tidak ada lagi langkah serakah yang mungkin dilakukan.

Ciri-ciri Algoritma Greedy

Karakteristik penting dari algoritma Greedy adalah:

• Daftar sumber daya yang terurut memuat atribusi biaya atau nilai yang mengukur batasan pada sistem.
• Algoritma tersebut mengambil jumlah sumber daya maksimum dalam waktu yang ditentukan oleh batasan yang berlaku.
• Sebagai contoh, dalam masalah penjadwalan aktivitas, biaya sumber daya diukur dalam jam dan aktivitas harus dilakukan secara berurutan.

Mengapa Menggunakan Pendekatan Serakah?

Berikut adalah alasan untuk menggunakan pendekatan serakah:

• Pendekatan greedy memiliki kelebihan dan kekurangan yang membuatnya sangat cocok untuk optimasi.
• Alasan yang paling jelas adalah untuk menghasilkan solusi yang layak dengan segera. Dalam masalah pemilihan aktivitas yang dibahas di bawah ini, jika lebih banyak aktivitas yang sesuai sebelum aktivitas saat ini selesai, aktivitas tersebut dapat dijadwalkan dalam jendela waktu yang sama.
• Alasan lainnya adalah karena metode ini membagi masalah secara rekursif berdasarkan suatu kondisi, tanpa perlu menggabungkan sub-solusi.
• Dalam masalah pemilihan aktivitas, langkah pembagian rekursif dicapai dengan memindai daftar sekali dan hanya mempertimbangkan aktivitas yang memenuhi syarat.

Cara Memecahkan Masalah Pemilihan Aktivitas

Dalam contoh penjadwalan aktivitas, setiap aktivitas memiliki waktu mulai dan waktu selesai serta diindeks dengan angka untuk referensi. Terdapat dua kategori aktivitas:

1. Aktivitas yang dipertimbangkan: aktivitas referensi yang menjadi acuan untuk mengukur kemampuan dalam memasukkan aktivitas-aktivitas lain yang tersisa.
2. Kegiatan yang tersisa: aktivitas pada satu atau lebih indeks sebelum aktivitas yang dipertimbangkan.

Biaya pelaksanaan suatu aktivitas adalah durasinya, yang dihitung sebagai (waktu selesai – waktu mulai).

Luas cakupan serakah (greedy extent) hanyalah jumlah aktivitas tersisa yang dapat dilakukan dalam waktu yang dibutuhkan untuk menyelesaikan suatu aktivitas yang dipertimbangkan.

Archipendekatan Greedy

Langkah 1) Periksa daftar biaya aktivitas yang dimulai dengan indeks 0 sebagai indeks yang dipertimbangkan.

Langkah 2) Jika masih ada aktivitas lain yang dapat diselesaikan sebelum aktivitas yang sedang dipertimbangkan berakhir, carilah aktivitas-aktivitas yang tersisa tersebut.

Langkah 3) Jika tidak ada lagi aktivitas yang dapat dijadwalkan, aktivitas yang tersisa saat ini menjadi aktivitas yang dipertimbangkan selanjutnya. Ulangi Langkah 1 dan Langkah 2 dengan aktivitas yang dipertimbangkan yang baru. Jika tidak ada aktivitas yang tersisa, lanjutkan ke Langkah 4.

Langkah 4) Mengembalikan gabungan dari indeks yang dipertimbangkan — ini adalah indeks aktivitas yang memaksimalkan throughput.

Archipendekatan Greedy

Code Penjelasan

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Penjelasan kode:

1. Termasuk file/kelas header
2. Jumlah maksimum aktivitas yang dapat dikonfigurasi oleh pengguna.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Penjelasan kode:

1. Mendeklarasikan namespace standar untuk operasi streaming.
2. Definisi kelas untuk TIME
3. Stempel waktu satu jam.
4. Konstruktor default TIME
5. Jamnya bervariasi.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Penjelasan kode:

1. Definisi kelas untuk Activity.
2. Cap waktu yang secara bersama-sama menentukan suatu durasi.
3. Semua stempel waktu diinisialisasi ke 0 dalam konstruktor default.

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Penjelasan kode:

1. Bagian 1 dari definisi kelas penjadwal.
2. considered_index adalah titik awal untuk memindai array.
3. `init_index` digunakan untuk menetapkan stempel waktu acak selama proses pengaturan.
4. Serangkaian objek Activity dialokasikan secara dinamis dengan operator new.
5. Pointer terjadwal menyimpan hasil greedy saat ini.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Penjelasan kode:

1. Konstruktor Scheduler — bagian 2 dari definisi kelas.
2. considered_index menandai awal pemindaian saat ini.
3. Luas jangkauan serakah tidak terdefinisi pada awalnya.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
&#8230;
&#8230;

Penjelasan kode:

1. Sebuah perulangan for menginisialisasi jam mulai dan jam berakhir dari setiap aktivitas yang dijadwalkan.
2. Menginisialisasi waktu mulai.
3. Mengatur waktu akhir agar berada pada atau setelah jam mulai.
4. Pernyataan debug mencetak durasi yang dialokasikan.

	public:
   		 Activity * activity_select(int);
};

Penjelasan kode:

1. Bagian 4 — bagian terakhir dari definisi kelas Scheduler.
2. activity_select() mengambil indeks awal sebagai dasar dan membagi pencarian serakah menjadi submasalah.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. Operator resolusi cakupan (::) menghubungkan definisi fungsi ke kelas Scheduler.
2. considered_index dilewatkan berdasarkan nilai, dan greedy_extent diinisialisasi ke indeks tepat setelahnya.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
&#8230;
...

Penjelasan kode:

1. Logika intinya — jangkauan serakah dibatasi pada MAX_ACTIVITIES.
2. Jam mulai dari aktivitas saat ini diperiksa dan dibandingkan dengan jam selesai dari aktivitas yang dipertimbangkan.
3. Selama kondisi tersebut terpenuhi, pernyataan debug opsional akan dicetak.
4. Jangkauan serakah kemudian berlanjut ke indeks berikutnya dalam larik aktivitas.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Penjelasan kode:

1. Kondisi tersebut memeriksa apakah semua aktivitas telah tercakup.
2. Jika tidak, algoritma akan memulai kembali pencarian serakah dari indeks saat ini — langkah rekursif yang membagi masalah secara serakah.
3. Jika ya, kendali kembali ke pemanggil tanpa ruang lingkup untuk memperluas keserakahan.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Penjelasan kode:

1. Fungsi utama memanggil Scheduler.
2. Objek Scheduler baru dibuat.
3. Fungsi activity_select() mengembalikan pointer Activity ke pemanggil setelah pencarian serakah berakhir.

Keluaran:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5
finish6
 activity:3

Schedule start:9
finish10
 activity:5

Keterbatasan Teknik Serakah

Pendekatan greedy tidak cocok untuk masalah yang membutuhkan solusi optimal untuk setiap submasalah, seperti pengurutan.

Dalam kasus seperti itu, metode greedy bisa salah — dalam kasus terburuk, metode ini menghasilkan solusi yang tidak optimal.

Kelemahan utama dari algoritma greedy adalah bahwa algoritma tersebut memilih tanpa mengetahui apa yang ada di depan keadaan greedy saat ini.

Diagram di bawah ini menggambarkan kelemahan dari metode greedy.

Dalam pemindaian serakah yang ditunjukkan di sini sebagai pohon (nilai yang lebih tinggi berarti keserakahan yang lebih tinggi), algoritma dengan nilai 40 akan memilih 29 selanjutnya, kemudian berakhir pada 12, dengan total 41.

Sebaliknya, strategi bagi-dan-taklukkan akan menambahkan 40 poin setelah 25 poin, sehingga totalnya menjadi 65 poin, yang 24 poin lebih tinggi daripada pilihan serakah lokal.

Contoh Serakah Algorithms

Sebagian besar algoritma jaringan bergantung pada pendekatan greedy. Contoh algoritma greedy yang umum meliputi:

• Algoritma Pohon Rentang Minimum Prim
• Masalah Penjual Keliling (perkiraan)
• Pewarnaan Peta Grafik
• Algoritma Pohon Rentang Minimum Kruskal
• Algoritma Jalur Terpendek Dijkstra
• Penutup Simpul Graf
• Masalah Ransel
• Pengurutan Pekerjaan dengan Batas Waktu

Pertanyaan Umum Demo Slot