Algoritma Greedy dengan Contoh: Metode Greedy & Pendekatan

Daftar Isi:

Anonim

Apa itu Algoritma Greedy?

Dalam Algoritme Greedy, sekumpulan sumber daya secara rekursif dibagi berdasarkan ketersediaan sumber daya tersebut yang maksimum dan langsung pada tahap eksekusi tertentu.

Untuk menyelesaikan suatu masalah berdasarkan pendekatan rakus, ada dua tahapan

  1. Memindai daftar item
  2. Optimasi

Tahapan ini dibahas secara paralel dalam tutorial algoritma Greedy ini, pada saat pembagian array.

Untuk memahami pendekatan serakah, Anda perlu memiliki pengetahuan kerja tentang rekursi dan peralihan konteks. Ini membantu Anda memahami cara melacak kode. Anda dapat mendefinisikan paradigma serakah dalam istilah pernyataan Anda sendiri yang perlu dan cukup.

Dua kondisi mendefinisikan paradigma rakus.

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

Dengan terus berteori, mari kita gambarkan sejarah yang terkait dengan pendekatan pencarian Greedy.

Dalam tutorial algoritma Greedy ini, Anda akan belajar:

  • Sejarah Algoritma Greedy
  • Strategi dan Keputusan Serakah
  • Karakteristik Pendekatan Serakah
  • Mengapa menggunakan Pendekatan Serakah?
  • Bagaimana Memecahkan masalah pemilihan aktivitas
  • Arsitektur pendekatan Greedy
  • Kekurangan Algoritma Greedy

Sejarah Algoritma Greedy

Berikut adalah tengara penting dari algoritme serakah:

  • Algoritme serakah dikonseptualisasikan untuk banyak algoritme grafik berjalan di tahun 1950-an.
  • Esdger Djikstra mengkonseptualisasikan algoritme untuk menghasilkan pohon rentang minimal. Dia bermaksud mempersingkat rentang rute di ibu kota Belanda, Amsterdam.
  • Dalam dekade yang sama, Prim dan Kruskal mencapai strategi pengoptimalan yang didasarkan pada meminimalkan biaya jalur di sepanjang rute yang ditimbang.
  • Pada tahun 70-an, peneliti Amerika, Cormen, Rivest, dan Stein mengusulkan substrukturisasi rekursif dari solusi serakah dalam pengantar klasik mereka ke buku algoritme.
  • Paradigma pencarian Greedy telah didaftarkan sebagai jenis strategi pengoptimalan yang berbeda dalam catatan NIST pada tahun 2005.
  • Hingga saat ini, protokol yang menjalankan web, seperti open-shortest-path-first (OSPF) dan banyak protokol pengalihan paket jaringan lainnya menggunakan strategi serakah untuk meminimalkan waktu yang dihabiskan di jaringan.

Strategi dan Keputusan Serakah

Logika dalam bentuknya yang paling mudah diringkas menjadi "serakah" atau "tidak serakah". Pernyataan ini ditentukan oleh pendekatan yang diambil untuk maju dalam setiap tahap algoritma.

Misalnya, algoritme Djikstra menggunakan strategi serakah bertahap yang mengidentifikasi host di Internet dengan menghitung fungsi biaya. Nilai yang dikembalikan oleh fungsi biaya menentukan apakah jalur berikutnya "serakah" atau "tidak serakah".

Singkatnya, algoritme tidak lagi serakah jika pada tahap mana pun ia mengambil langkah yang tidak serakah secara lokal. Masalah Greedy berhenti tanpa cakupan keserakahan lebih lanjut.

Karakteristik Pendekatan Serakah

Karakteristik penting dari algoritma metode Greedy adalah:

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

Mengapa menggunakan Pendekatan Serakah?

Berikut alasan untuk menggunakan pendekatan serakah:

  • Pendekatan serakah memiliki beberapa pengorbanan, yang mungkin membuatnya cocok untuk pengoptimalan.
  • Salah satu alasan utamanya adalah untuk segera mencapai solusi yang paling memungkinkan. Dalam masalah pemilihan aktivitas (Dijelaskan di bawah), jika lebih banyak aktivitas dapat dilakukan sebelum menyelesaikan aktivitas saat ini, aktivitas ini dapat dilakukan dalam waktu yang bersamaan.
  • Alasan lain adalah membagi 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

Dalam contoh penjadwalan aktivitas, ada waktu "mulai" dan "selesai" untuk setiap aktivitas. Setiap Aktivitas diindeks dengan nomor untuk referensi. Ada dua kategori aktivitas.

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

Total durasi memberikan biaya melakukan aktivitas. Artinya (finish - start) memberi kita durasi sebagai biaya suatu kegiatan.

Anda akan belajar bahwa tingkat keserakahan adalah jumlah aktivitas tersisa yang dapat Anda lakukan pada saat aktivitas dipertimbangkan.

Arsitektur pendekatan Greedy

LANGKAH 1)

Pindai daftar biaya aktivitas, dimulai dengan indeks 0 sebagai Indeks yang dipertimbangkan.

LANGKAH 2)

Ketika lebih banyak aktivitas dapat diselesaikan pada waktunya, aktivitas yang dipertimbangkan selesai, mulailah mencari satu atau lebih aktivitas yang tersisa.

LANGKAH 3)

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

LANGKAH 4)

Kembalikan penyatuan indeks yang dianggap. Ini adalah indeks aktivitas yang akan digunakan untuk memaksimalkan throughput.

Arsitektur Pendekatan Serakah

Penjelasan Kode

#include#include#include#define MAX_ACTIVITIES 12

Penjelasan kode:

  1. File / kelas header yang disertakan
  2. Jumlah aktivitas maksimal yang disediakan oleh pengguna.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Penjelasan kode:

  1. Namespace untuk operasi streaming.
  2. Definisi kelas untuk TIME
  3. Stempel waktu satu jam.
  4. Konstruktor default TIME
  5. Variabel jam.
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 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. Indeks yang Dianggap adalah titik awal untuk memindai larik.
  3. Indeks inisialisasi digunakan untuk menetapkan cap waktu acak.
  4. Larik objek aktivitas dialokasikan secara dinamis menggunakan operator baru.
  5. Penunjuk terjadwal menentukan lokasi dasar saat ini untuk keserakahan.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Penjelasan kode:

  1. Pembuat penjadwal - bagian 2 dari definisi kelas penjadwal.
  2. Indeks yang dipertimbangkan menentukan awal pemindaian saat ini.
  3. Tingkat keserakahan saat ini tidak ditentukan di awal.
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 akhir setiap aktivitas yang saat ini dijadwalkan.
  2. Mulai waktu inisialisasi.
  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 rakus menjadi sub-masalah rakus.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Menggunakan operator resolusi cakupan (: :), definisi fungsi disediakan.
  2. Indeks yang dipertimbangkan adalah Indeks yang disebut dengan nilai. Greedy_extent adalah yang diinisialisasi hanya indeks setelah Indeks 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) akan 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. Pemeriksaan bersyarat jika semua aktivitas telah tercakup.
  2. Jika tidak, Anda dapat memulai kembali keserakahan Anda dengan Indeks yang dianggap sebagai titik saat ini. Ini adalah langkah rekursif yang dengan rakus membagi pernyataan masalah.
  3. Jika ya, itu 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 yang digunakan untuk memanggil penjadwal.
  2. Penjadwal baru dibuatkan.
  3. Fungsi pemilihan aktivitas, yang mengembalikan penunjuk aktivitas jenis kembali ke pemanggil setelah pencarian serakah selesai.

Keluaran:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

Kekurangan Algoritma Greedy

Ini tidak cocok untuk masalah Greedy di mana solusi diperlukan untuk setiap subproblem seperti pengurutan.

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

Oleh karena itu, kerugian dari algoritme serakah adalah menggunakan tidak mengetahui apa yang ada di depan status serakah saat ini.

Di bawah ini adalah gambaran kerugian dari metode Greedy:

Dalam pemindaian serakah yang ditampilkan di sini sebagai pohon (nilai lebih tinggi lebih tinggi keserakahan), status algoritme pada nilai: 40, kemungkinan akan mengambil 29 sebagai nilai berikutnya. Selanjutnya, pencariannya berakhir pada 12. Jumlah ini bernilai 41.

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

Contoh Algoritma Greedy

Sebagian besar algoritme jaringan menggunakan pendekatan serakah. Berikut adalah daftar beberapa contoh algoritma Greedy:

  • Algoritma Pohon Rentang Minimal Prim
  • Masalah Penjual Bepergian
  • Grafik - Pewarnaan Peta
  • Algoritma Pohon Rentang Minimal Kruskal
  • Algoritma Pohon Rentang Minimal Dijkstra
  • Grafik - Penutup Vertex
  • Masalah Knapsack
  • Masalah Penjadwalan Pekerjaan

Ringkasan:

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