Algoritma Greedy Beserta Contoh : Apa Itu, Metode dan Pendekatan

Untuk memahami pendekatan greedy, Anda perlu memiliki pengetahuan dasar tentang rekursi dan pengalihan konteks. Ini membantu Anda memahami bagaimana caranya trace kode tersebut. Anda dapat mendefinisikan paradigma greedy dalam hal pernyataan yang diperlukan dan cukup menurut Anda sendiri.

Ada dua kondisi yang mendefinisikan paradigma serakah.

• Setiap solusi bertahap harus menyusun masalah menuju solusi terbaik yang dapat diterima.
• Cukuplah jika penataan masalah dapat dihentikan dalam sejumlah langkah serakah yang terbatas.

Dengan melanjutkan teori, mari kita uraikan sejarah yang terkait dengan pendekatan pencarian Greedy.

Sejarah Serakah Algorithms

Berikut adalah petunjuk penting dari algoritma serakah:

• Algoritme serakah dikonsep untuk banyak algoritma graph walk pada tahun 1950-an.
• Esdger Djikstra mengonsep algoritma untuk menghasilkan pohon merentang minimal. Ia bertujuan untuk memperpendek rentang rute di ibu kota Belanda, Amsterdam.
• Pada dekade yang sama, Prim dan Kruskal mencapai strategi optimasi yang didasarkan pada minimalisasi biaya jalur sepanjang rute yang ditimbang.
• Pada tahun 70-an, peneliti Amerika, Cormen, Rivest, dan Stein mengusulkan substrukturisasi rekursif dari solusi serakah dalam buku pengantar klasik mereka tentang algoritma.
• Paradigma pencarian Greedy terdaftar sebagai jenis strategi optimasi yang berbeda dalam catatan NIST pada tahun 2005.
• Hingga saat ini, protokol yang menjalankan web, seperti open-shortest-path-first (OSPF) dan banyak protokol perpindahan paket jaringan lainnya menggunakan strategi serakah untuk meminimalkan waktu yang dihabiskan di jaringan.

Strategi dan Keputusan yang Serakah

Logika dalam bentuknya yang paling sederhana diringkas menjadi “serakah” atau “tidak serakah”. Pernyataan-pernyataan ini ditentukan oleh pendekatan yang diambil untuk memajukan setiap tahap algoritma.

Misalnya, algoritma Djikstra menggunakan strategi greedy bertahap yang mengidentifikasi host di Internet dengan menghitung fungsi biaya. Nilai yang dikembalikan oleh fungsi biaya menentukan apakah jalur berikutnya adalah “serakah” atau “tidak serakah”.

Singkatnya, suatu algoritma akan berhenti menjadi serakah jika pada tahap mana pun ia mengambil langkah yang tidak serakah secara lokal. Masalah-masalah Greedy berhenti tanpa adanya ruang lingkup keserakahan lebih lanjut.

Ciri-ciri Algoritma Greedy

Karakteristik penting dari algoritma Greedy adalah:

• Ada daftar sumber daya yang diurutkan, dengan atribusi biaya atau nilai. Ini mengukur batasan pada suatu sistem.
• Anda akan mengambil sumber daya dalam jumlah maksimum selama batasan berlaku.
• Misalnya, dalam masalah penjadwalan aktivitas, biaya sumber daya dinyatakan dalam jam, dan aktivitas perlu dilakukan dalam urutan serial.

Mengapa menggunakan Pendekatan Serakah?

Berikut adalah alasan untuk menggunakan pendekatan serakah:

• Pendekatan serakah memiliki beberapa kelemahan, yang mungkin membuatnya cocok untuk optimasi.
• Salah satu alasan utama adalah untuk segera mencapai solusi yang paling layak. Dalam permasalahan pemilihan aktivitas (Dijelaskan di bawah), jika lebih banyak aktivitas dapat dilakukan sebelum menyelesaikan aktivitas saat ini, aktivitas tersebut dapat dilakukan dalam waktu yang sama.
• Alasan lainnya adalah membagi suatu masalah secara rekursif berdasarkan suatu kondisi, tanpa perlu menggabungkan semua solusi.
• Dalam masalah pemilihan aktivitas, langkah “pembagian rekursif” dicapai dengan memindai daftar item hanya sekali dan mempertimbangkan aktivitas tertentu.

Bagaimana Memecahkan masalah pemilihan aktivitas

Pada contoh penjadwalan aktivitas, terdapat waktu “mulai” dan “selesai” untuk setiap aktivitas. Setiap Aktivitas diindeks dengan nomor untuk referensi. Ada dua kategori kegiatan.

1. aktivitas yang dipertimbangkan: adalah Aktivitas, yang merupakan referensi dari mana kemampuan untuk melakukan lebih dari satu Aktivitas yang tersisa dianalisis.
2. sisa kegiatan: aktivitas pada satu atau lebih indeks sebelum aktivitas yang dipertimbangkan.

Durasi total menunjukkan biaya pelaksanaan aktivitas. Artinya (selesai – mulai) memberi kita durasi sebagai biaya suatu aktivitas.

Anda akan mengetahui bahwa tingkat keserakahan adalah jumlah sisa aktivitas yang dapat Anda lakukan dalam waktu aktivitas yang dipertimbangkan.

Architekstur pendekatan Greedy

LANGKAH 1) Pindai daftar biaya kegiatan, dimulai dengan indeks 0 sebagai Indeks yang dipertimbangkan.

LANGKAH 2) Bila lebih banyak kegiatan yang dapat diselesaikan pada saat kegiatan yang dimaksud telah selesai, mulailah mencari satu atau lebih kegiatan yang tersisa.

LANGKAH 3) Jika tidak ada lagi aktivitas yang tersisa, aktivitas yang tersisa saat ini menjadi aktivitas berikutnya yang dipertimbangkan. Ulangi langkah 1 dan langkah 2, dengan aktivitas baru yang dipertimbangkan. Jika tidak ada aktivitas tersisa, lanjutkan ke langkah 4.

LANGKAH 4) Kembalikan gabungan indeks yang dipertimbangkan. Ini adalah indeks aktivitas yang akan digunakan untuk memaksimalkan throughput.

Code Penjelasan

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

#define MAX_ACTIVITIES 12

Penjelasan kode:

1. Termasuk file/kelas header
2. Jumlah maksimal aktivitas yang disediakan oleh pengguna.

using namespace std;

class TIME
{
    public:
    int hours;

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

Penjelasan kode:

1. Ruang nama 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 dari aktivitas
2. Stempel waktu yang menentukan durasi
3. Semua stempel waktu diinisialisasi ke 0 di 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. Indeks yang Dianggap adalah titik awal untuk memindai susunan.
3. Indeks inisialisasi digunakan untuk menetapkan stempel waktu acak.
4. Serangkaian objek aktivitas dialokasikan secara dinamis menggunakan operator baru.
5. Penunjuk terjadwal menentukan lokasi dasar keserakahan saat ini.

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

Penjelasan kode:

1. Konstruktor penjadwal – bagian 2 dari definisi kelas penjadwal.
2. Indeks yang dipertimbangkan menentukan awal pemindaian saat ini.
3. Tingkat keserakahan saat ini tidak ditentukan 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);
 }
…
…

Penjelasan kode:

1. Perulangan for untuk menginisialisasi jam mulai dan jam berakhir setiap aktivitas yang saat ini dijadwalkan.
2. Inisialisasi waktu mulai.
3. Inisialisasi waktu akhir selalu setelah atau tepat pada jam mulai.
4. Pernyataan debug untuk mencetak durasi yang dialokasikan.

	public:
   		 Activity * activity_select(int);
};

Penjelasan kode:

1. Bagian 4 – bagian terakhir dari definisi kelas penjadwal.
2. Fungsi pemilihan aktivitas mengambil indeks titik awal sebagai dasar dan membagi pencarian serakah menjadi sub-masalah serakah.

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

1. Menggunakan operator resolusi lingkup (::), definisi fungsi disediakan.
2. Indeks yang dipertimbangkan adalah Indeks yang disebut berdasarkan nilai. Greedy_extent adalah indeks yang diinisialisasi setelah Indeks yang dipertimbangkan.

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++;
    	}
…
...

Penjelasan kode:

1. Logika inti- Tingkat keserakahan terbatas pada jumlah aktivitas.
2. Jam mulai dari Aktivitas saat ini diperiksa sebagai dapat dijadwalkan sebelum Aktivitas yang dipertimbangkan (diberikan oleh indeks yang dipertimbangkan) selesai.
3. Selama ini memungkinkan, pernyataan debug opsional akan dicetak.
4. Maju ke indeks berikutnya pada larik aktivitas

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Penjelasan kode:

1. Kondisional memeriksa apakah semua aktivitas telah tercakup.
2. Jika tidak, Anda dapat memulai kembali keserakahan Anda dengan Indeks yang dianggap sebagai poin saat ini. Ini adalah langkah rekursif yang dengan rakus membagi pernyataan masalah.
3. Jika ya, ia kembali ke penelepon tanpa ruang 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 yang digunakan untuk memanggil penjadwal.
2. Penjadwal baru dibuat.
3. Fungsi pemilihan aktivitas, yang mengembalikan penunjuk jenis aktivitas kembali ke pemanggil setelah pencarian serakah selesai.

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

Ini tidak cocok untuk masalah Greedy yang memerlukan solusi untuk setiap submasalah seperti pengurutan.

Dalam soal latihan algoritma Greedy seperti itu, metode Greedy bisa saja salah; bahkan dalam kasus terburuk akan menghasilkan solusi yang tidak optimal.

Oleh karena itu, kerugian dari algoritma serakah adalah tidak mengetahui apa yang ada di depan keadaan serakah saat ini.

Berikut ini gambaran kelemahan metode Greedy:

Dalam pemindaian serakah yang ditampilkan di sini sebagai pohon (nilai lebih tinggi, keserakahan lebih tinggi), suatu algoritma menyatakan pada nilai: 40, kemungkinan akan mengambil 29 sebagai nilai berikutnya. Selanjutnya, pencariannya berakhir pada 12. Nilainya adalah 41.

Namun, jika algoritme mengambil jalur yang kurang optimal atau mengadopsi strategi penaklukan. kemudian 25 akan diikuti oleh 40, dan peningkatan biaya keseluruhan akan menjadi 65, yang dinilai 24 poin lebih tinggi sebagai keputusan suboptimal.

Contoh Serakah Algorithms

Kebanyakan algoritma jaringan menggunakan pendekatan serakah. Berikut adalah daftar beberapa contoh algoritma Greedy:

• Algoritma Pohon Rentang Minimal Prim
• Traveling Salesman Problem
• Grafik – Pewarnaan Peta
• Algoritma Pohon Rentang Minimal Kruskal
• Algoritma Pohon Rentang Minimal Dijkstra
• Grafik – Penutup Titik
• Masalah Ransel
• Masalah Penjadwalan Pekerjaan

Ringkasan

Singkatnya, artikel ini mendefinisikan paradigma greedy, menunjukkan bagaimana optimisasi greedy dan rekursi dapat membantu Anda memperoleh solusi terbaik hingga titik tertentu. Algoritma greedy banyak digunakan untuk memecahkan masalah dalam banyak bahasa sebagai algoritma greedy. Python, C, C#, PHP, Java, dll. Pemilihan aktivitas contoh algoritma Greedy digambarkan sebagai masalah strategis yang dapat mencapai throughput maksimum dengan menggunakan pendekatan serakah. Pada akhirnya, kerugian dari penggunaan pendekatan serakah dijelaskan.