Algoritma Greedy dengan Contoh: Kaedah Greedy & Pendekatan

Isi kandungan:

Anonim

Apa itu Algoritma tamak?

Dalam Algoritma Greedy satu set sumber dibahagikan secara rekursif berdasarkan ketersediaan sumber daya maksimum dan segera pada tahap pelaksanaan tertentu.

Untuk menyelesaikan masalah berdasarkan pendekatan tamak, ada dua tahap

  1. Mengimbas senarai item
  2. Pengoptimuman

Tahap-tahap ini diliputi secara selari dalam tutorial algoritma Greedy ini, semasa pembahagian array.

Untuk memahami pendekatan tamak, anda perlu mempunyai pengetahuan yang baik mengenai pengulangan dan pertukaran konteks. Ini membantu anda memahami cara mengesan kod tersebut. Anda boleh menentukan paradigma tamak dari segi pernyataan anda sendiri yang perlu dan mencukupi.

Dua syarat menentukan paradigma tamak.

  • Setiap penyelesaian bertahap mesti menyusun masalah ke arah penyelesaian yang paling baik diterima.
  • Cukuplah jika penataan masalah dapat dihentikan dengan sejumlah langkah tamak.

Dengan teori terus berlanjut, marilah kita menerangkan sejarah yang berkaitan dengan pendekatan pencarian tamak.

Dalam tutorial algoritma Greedy ini, anda akan belajar:

  • Sejarah Algoritma tamak
  • Strategi dan Keputusan tamak
  • Ciri-ciri Pendekatan tamak
  • Mengapa menggunakan Pendekatan tamak?
  • Cara Menyelesaikan masalah pemilihan aktiviti
  • Senibina pendekatan tamak
  • Kekurangan Algoritma tamak

Sejarah Algoritma tamak

Berikut adalah mercu tanda penting algoritma tamak:

  • Algoritma tamak dikonseptualisasikan untuk banyak algoritma grafik berjalan pada tahun 1950-an.
  • Esdger Djikstra berkonsepkan algoritma untuk menghasilkan pokok rentang minimum. Dia bertujuan untuk memendekkan jarak rute di ibu kota Belanda, Amsterdam.
  • Pada dekad yang sama, Prim dan Kruskal mencapai strategi pengoptimuman yang berdasarkan pada meminimumkan kos jalan di sepanjang jalan yang ditimbang.
  • Pada tahun 70-an, penyelidik Amerika, Cormen, Rivest, dan Stein mencadangkan substruktur rekursif penyelesaian tamak dalam buku pengenalan klasik mereka kepada algoritma.
  • Paradigma carian Greedy telah didaftarkan sebagai jenis strategi pengoptimuman yang berbeza dalam rekod NIST pada tahun 2005.
  • Sehingga kini, protokol yang menjalankan web, seperti jalan terbuka-terpendek-jalan pertama (OSPF) dan banyak protokol pertukaran paket rangkaian lain menggunakan strategi tamak untuk meminimumkan masa yang dihabiskan di rangkaian.

Strategi dan Keputusan tamak

Logik dalam bentuk termudahnya disusun menjadi "tamak" atau "tidak tamak". Pernyataan ini ditentukan oleh pendekatan yang diambil untuk maju dalam setiap tahap algoritma.

Sebagai contoh, algoritma Djikstra menggunakan strategi tamak bertahap untuk mengenal pasti hos di Internet dengan mengira fungsi kos. Nilai yang dikembalikan oleh fungsi kos ditentukan sama ada jalan seterusnya adalah "tamak" atau "tidak tamak".

Ringkasnya, algoritma tidak lagi rakus jika pada tahap mana pun ia mengambil langkah yang tidak tamak tempatan. Masalah Keserakahan berhenti tanpa ruang lingkup ketamakan.

Ciri-ciri Pendekatan tamak

Ciri penting algoritma kaedah Greedy adalah:

  • Terdapat senarai sumber yang teratur, dengan kos atau atribusi nilai. Ini mengukur kekangan pada sistem.
  • Anda akan menggunakan jumlah sumber maksimum dalam masa kekangan berlaku.
  • Contohnya, dalam masalah penjadualan aktiviti, kos sumber daya adalah dalam beberapa jam, dan aktiviti perlu dilakukan secara berurutan.

Mengapa menggunakan Pendekatan tamak?

Berikut adalah alasan untuk menggunakan pendekatan tamak:

  • Pendekatan tamak mempunyai beberapa pertukaran, yang mungkin menjadikannya sesuai untuk pengoptimuman.
  • Salah satu sebab yang jelas adalah untuk mencapai penyelesaian yang paling pantas dengan segera. Dalam masalah pemilihan aktiviti (Dijelaskan di bawah), jika lebih banyak aktiviti dapat dilakukan sebelum menyelesaikan aktiviti semasa, aktiviti ini dapat dilakukan dalam waktu yang sama.
  • Sebab lain adalah untuk membahagikan masalah secara berulang berdasarkan keadaan, tanpa perlu menggabungkan semua penyelesaian.
  • Dalam masalah pemilihan aktiviti, langkah "bahagian rekursif" dicapai dengan mengimbas senarai item hanya sekali dan mempertimbangkan aktiviti tertentu.

Cara Menyelesaikan masalah pemilihan aktiviti

Dalam contoh penjadualan aktiviti, ada masa "permulaan" dan "selesai" untuk setiap aktiviti. Setiap Aktiviti diindeks oleh nombor untuk rujukan. Terdapat dua kategori aktiviti.

  1. aktiviti yang dipertimbangkan : adalah Aktiviti, yang merupakan rujukan dari mana kemampuan untuk melakukan lebih daripada satu Aktiviti yang tersisa dianalisis.
  2. baki aktiviti: aktiviti pada satu atau lebih indeks menjelang aktiviti yang dipertimbangkan.

Tempoh keseluruhan memberikan kos melaksanakan aktiviti. Iaitu (selesai - mula) memberi kita jangka masa sebagai kos aktiviti.

Anda akan mengetahui bahawa tahap tamak adalah jumlah baki aktiviti yang dapat anda lakukan pada masa aktiviti tersebut.

Senibina pendekatan tamak

LANGKAH 1)

Imbas senarai kos aktiviti, bermula dengan indeks 0 sebagai Indeks yang dipertimbangkan.

LANGKAH 2)

Apabila lebih banyak aktiviti dapat diselesaikan pada masa itu, aktiviti yang dipertimbangkan selesai, mulailah mencari satu atau beberapa aktiviti yang tersisa.

LANGKAH 3)

Sekiranya tidak ada lagi aktiviti yang tinggal, aktiviti yang tinggal sekarang menjadi aktiviti yang dipertimbangkan seterusnya. Ulangi langkah 1 dan langkah 2, dengan aktiviti yang baru dipertimbangkan. Sekiranya tidak ada lagi aktiviti yang tinggal, lanjutkan ke langkah 4

LANGKAH 4)

Kembalikan kesatuan indeks yang dipertimbangkan. Ini adalah indeks aktiviti yang akan digunakan untuk memaksimumkan hasil.

Senibina Pendekatan tamak

Penjelasan Kod

#include#include#include#define MAX_ACTIVITIES 12

Penjelasan kod:

  1. Fail header / kelas yang disertakan
  2. Sebilangan besar aktiviti yang disediakan oleh pengguna.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Penjelasan kod:

  1. Ruang nama untuk operasi penstriman.
  2. Definisi kelas untuk TIME
  3. Cap waktu sejam.
  4. Pembina lalai MASA
  5. Pembolehubah jam.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Penjelasan kod:

  1. Definisi kelas dari aktiviti
  2. Cap waktu yang menentukan jangka masa
  3. Semua cap waktu dimulakan hingga 0 pada konstruktor lalai
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Penjelasan kod:

  1. Bahagian 1 definisi kelas penjadual.
  2. Indeks yang dipertimbangkan adalah titik permulaan untuk mengimbas array.
  3. Indeks inisialisasi digunakan untuk menetapkan cap waktu rawak.
  4. Pelbagai objek aktiviti diperuntukkan secara dinamik menggunakan operator baru.
  5. Penunjuk berjadual menentukan lokasi asas semasa untuk keserakahan.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Penjelasan kod:

  1. Pembina penjadual - bahagian 2 dari definisi kelas penjadual.
  2. Indeks yang dipertimbangkan menentukan permulaan imbasan semasa.
  3. Tahap tamak semasa 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 kod:

  1. A untuk gelung untuk menginisialisasi waktu mula dan jam akhir setiap aktiviti yang dijadualkan.
  2. Permulaan masa permulaan.
  3. Permulaan waktu tamat selalu selepas atau tepat pada waktu permulaan.
  4. Penyataan debug untuk mencetak jangka masa yang diperuntukkan.
public:Activity * activity_select(int);};

Penjelasan kod:

  1. Bahagian 4 - bahagian terakhir definisi kelas penjadual.
  2. Fungsi pilih aktiviti mengambil indeks titik permulaan sebagai asas dan membahagi pencarian tamak menjadi sub-masalah tamak.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Dengan menggunakan operator resolusi skop (: :), definisi fungsi disediakan.
  2. Indeks yang dipertimbangkan adalah Indeks yang dipanggil oleh nilai. The greedy_extent adalah diinisialisasi hanya indeks 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 kod:

  1. Logik inti- Tahap tamak terhad kepada bilangan aktiviti.
  2. Waktu mula Aktiviti semasa diperiksa sebagai dijadualkan sebelum Aktiviti yang dipertimbangkan (diberikan oleh indeks dipertimbangkan) selesai.
  3. Selama ini mungkin, penyataan debug pilihan dicetak.
  4. Maju ke indeks seterusnya pada susunan aktiviti
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Penjelasan kod:

  1. Bersyarat memeriksa jika semua aktiviti telah dilindungi.
  2. Sekiranya tidak, anda boleh memulakan semula tamak anda dengan Indeks yang dianggap sebagai titik semasa. Ini adalah langkah rekursif yang dengan rakus membahagi penyataan masalah.
  3. Sekiranya ya, ia akan kembali kepada pemanggil tanpa ruang lingkup untuk meningkatkan keserakahan.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Penjelasan kod:

  1. Fungsi utama yang digunakan untuk memanggil penjadual.
  2. Penjadual baru dibuat.
  3. Fungsi pilih aktiviti, yang mengembalikan penunjuk jenis aktiviti kembali kepada pemanggil setelah pencarian tamak selesai.

Pengeluaran:

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

Kekurangan Algoritma tamak

Ia tidak sesuai untuk masalah tamak di mana penyelesaian diperlukan untuk setiap masalah seperti menyusun.

Dalam masalah praktik algoritma Greedy seperti itu, kaedah Greedy boleh salah; dalam keadaan terburuk malah membawa kepada penyelesaian yang tidak optimum.

Oleh itu, kelemahan algoritma tamak adalah dengan tidak mengetahui apa yang ada di hadapan keadaan tamak semasa.

Di bawah ini adalah gambaran mengenai kelemahan kaedah Greedy:

Dalam imbasan tamak yang ditunjukkan di sini sebagai pokok (nilai keserakahan lebih tinggi lebih tinggi), keadaan algoritma pada nilai: 40, kemungkinan mengambil 29 sebagai nilai seterusnya. Selanjutnya, pencariannya berakhir pada 12. Ini berjumlah 41.

Walau bagaimanapun, jika algoritma mengambil jalan yang tidak optimum atau menggunakan strategi penaklukan. maka 25 akan diikuti oleh 40, dan peningkatan keseluruhan biaya menjadi 65, yang dinilai 24 poin lebih tinggi sebagai keputusan suboptimal.

Contoh Algoritma tamak

Sebilangan besar algoritma rangkaian menggunakan pendekatan tamak. Berikut adalah senarai beberapa contoh algoritma tamak:

  • Algoritma Pokok Rentang Minimum Prim
  • Masalah Penjual Perjalanan
  • Graf - Pewarnaan Peta
  • Algoritma Pokok Rentang Minimum Kruskal
  • Algoritma Pokok Rentang Minimum Dijkstra
  • Grafik - Penutup Vertex
  • Masalah ransangan
  • Masalah Penjadualan Kerja

Ringkasan:

Ringkasnya, artikel tersebut mendefinisikan paradigma tamak, menunjukkan bagaimana pengoptimuman dan pengulangan tamak, dapat membantu anda mendapatkan penyelesaian terbaik hingga satu titik. Algoritma Greedy secara meluas dimasukkan ke dalam aplikasi untuk menyelesaikan masalah dalam banyak bahasa seperti algoritma Greedy Python, C, C #, PHP, Java, dll. Pemilihan aktiviti contoh algoritma Greedy digambarkan sebagai masalah strategik yang dapat mencapai throughput maksimum menggunakan tamak pendekatan. Pada akhirnya, kelemahan penggunaan pendekatan tamak dijelaskan.