Αλγόριθμος Greedy με Παράδειγμα: Τι είναι, Μέθοδος και Προσέγγιση

Για να κατανοήσετε την άπληστη προσέγγιση, θα χρειαστεί να έχετε γνώσεις σχετικά με την αναδρομή και την εναλλαγή περιβάλλοντος. Αυτό σας βοηθά να κατανοήσετε πώς να ανιχνεύσετε τον κώδικα. Μπορείτε να ορίσετε το άπληστο παράδειγμα με βάση τις δικές σας απαραίτητες και επαρκείς δηλώσεις.

Δύο συνθήκες καθορίζουν το άπληστο παράδειγμα.

• Κάθε σταδιακή λύση πρέπει να δομεί ένα πρόβλημα προς την καλύτερη αποδεκτή λύση του.
• Είναι αρκετό εάν η δόμηση του προβλήματος μπορεί να σταματήσει σε έναν πεπερασμένο αριθμό άπληστων βημάτων.

Με τη θεωρητική συνέχιση, ας περιγράψουμε το ιστορικό που σχετίζεται με την προσέγγιση της αναζήτησης Greedy.

History of Greedy Algorithms

Εδώ είναι ένα σημαντικό ορόσημο των άπληστων αλγορίθμων:

• Οι άπληστοι αλγόριθμοι δημιουργήθηκαν για πολλούς αλγόριθμους βάδισης γραφημάτων τη δεκαετία του 1950.
• Ο Esdger Djikstra δημιούργησε τον αλγόριθμο για να δημιουργήσει ελάχιστα εκτεινόμενα δέντρα. Στόχος του ήταν να συντομεύσει το εύρος των δρομολογίων εντός της ολλανδικής πρωτεύουσας, Άμστερνταμ.
• Την ίδια δεκαετία, οι Prim και Kruskal πέτυχαν στρατηγικές βελτιστοποίησης που βασίστηκαν στην ελαχιστοποίηση του κόστους διαδρομής κατά μήκος σταθμισμένων διαδρομών.
• Στη δεκαετία του '70, Αμερικανοί ερευνητές, οι Cormen, Rivest και Stein πρότειναν μια αναδρομική υποδομή άπληστων λύσεων στο κλασικό βιβλίο τους για την εισαγωγή στους αλγόριθμους.
• Το παράδειγμα αναζήτησης Greedy καταχωρήθηκε ως διαφορετικός τύπος στρατηγικής βελτιστοποίησης στις εγγραφές NIST το 2005.
• Μέχρι σήμερα, τα πρωτόκολλα που τρέχουν τον ιστό, όπως το open-shorttest-path-first (OSPF) και πολλά άλλα πρωτόκολλα μεταγωγής πακέτων δικτύου χρησιμοποιούν την άπληστη στρατηγική για να ελαχιστοποιήσουν τον χρόνο που δαπανάται σε ένα δίκτυο.

Άπληστες Στρατηγικές και Αποφάσεις

Η λογική στην πιο εύκολη μορφή της συνοψίστηκε σε «άπληστοι» ή «μη άπληστοι». Αυτές οι δηλώσεις ορίστηκαν από την προσέγγιση που ακολουθήθηκε για να προχωρήσουμε σε κάθε στάδιο αλγορίθμου.

Για παράδειγμα, ο αλγόριθμος του Djikstra χρησιμοποίησε μια σταδιακά άπληστη στρατηγική που εντοπίζει κεντρικούς υπολογιστές στο Διαδίκτυο υπολογίζοντας μια συνάρτηση κόστους. Η τιμή που επιστράφηκε από τη συνάρτηση κόστους καθόρισε εάν η επόμενη διαδρομή είναι "άπληστη" ή "μη άπληστη".

Εν ολίγοις, ένας αλγόριθμος παύει να είναι άπληστος εάν σε οποιοδήποτε στάδιο κάνει ένα βήμα που δεν είναι τοπικά άπληστο. Τα προβλήματα των Greedy σταματούν χωρίς περαιτέρω εύρος απληστίας.

Χαρακτηριστικά του αλγορίθμου Greedy

Τα σημαντικά χαρακτηριστικά ενός αλγορίθμου Greedy είναι:

• Υπάρχει μια ταξινομημένη λίστα πόρων, με κόστος ή αποδόσεις αξίας. Αυτά ποσοτικοποιούν τους περιορισμούς σε ένα σύστημα.
• Θα λάβετε τη μέγιστη ποσότητα πόρων στο χρόνο που θα εφαρμοστεί ένας περιορισμός.
• Για παράδειγμα, σε ένα πρόβλημα προγραμματισμού δραστηριότητας, το κόστος των πόρων είναι σε ώρες και οι δραστηριότητες πρέπει να εκτελούνται με σειριακή σειρά.

Γιατί να χρησιμοποιήσετε το Greedy Approach;

Εδώ είναι οι λόγοι για τη χρήση της άπληστης προσέγγισης:

• Η άπληστη προσέγγιση έχει μερικές ανταλλαγές, που μπορεί να την καταστήσουν κατάλληλη για βελτιστοποίηση.
• Ένας σημαντικός λόγος είναι να επιτευχθεί άμεσα η πιο εφικτή λύση. Στο πρόβλημα επιλογής δραστηριότητας (Εξηγείται παρακάτω), εάν μπορούν να γίνουν περισσότερες δραστηριότητες πριν από την ολοκλήρωση της τρέχουσας δραστηριότητας, αυτές οι δραστηριότητες μπορούν να εκτελεστούν στον ίδιο χρόνο.
• Ένας άλλος λόγος είναι να διαιρέσετε ένα πρόβλημα αναδρομικά με βάση μια συνθήκη, χωρίς να χρειάζεται να συνδυάσετε όλες τις λύσεις.
• Στο πρόβλημα επιλογής δραστηριότητας, το βήμα «αναδρομικής διαίρεσης» επιτυγχάνεται σαρώνοντας μια λίστα στοιχείων μόνο μία φορά και λαμβάνοντας υπόψη ορισμένες δραστηριότητες.

Πώς να λύσετε το πρόβλημα επιλογής δραστηριότητας

Στο παράδειγμα προγραμματισμού δραστηριότητας, υπάρχει ένας χρόνος «έναρξης» και «τερματισμού» για κάθε δραστηριότητα. Κάθε Δραστηριότητα ευρετηριάζεται με έναν αριθμό για αναφορά. Υπάρχουν δύο κατηγορίες δραστηριοτήτων.

1. θεωρείται δραστηριότητα: είναι η Δραστηριότητα, η οποία είναι η αναφορά από την οποία αναλύεται η δυνατότητα εκτέλεσης περισσότερων από μία υπόλοιπων Δραστηριοτήτων.
2. υπόλοιπες δραστηριότητες: δραστηριότητες σε έναν ή περισσότερους δείκτες πριν από την εξεταζόμενη δραστηριότητα.

Η συνολική διάρκεια δίνει το κόστος εκτέλεσης της δραστηριότητας. Δηλαδή (τέρμα – έναρξη) μας δίνει τη διάρκεια ως το κόστος μιας δραστηριότητας.

Θα μάθετε ότι η άπληστη έκταση είναι ο αριθμός των υπόλοιπων δραστηριοτήτων που μπορείτε να εκτελέσετε τη στιγμή μιας εξεταζόμενης δραστηριότητας.

Archiδομή της προσέγγισης Greedy

ΒΗΜΑ 1) Σαρώστε τη λίστα των δαπανών δραστηριότητας, ξεκινώντας με το δείκτη 0 ως το εξεταζόμενο δείκτη.

ΒΗΜΑ 2) Όταν περισσότερες δραστηριότητες μπορούν να ολοκληρωθούν μέχρι τη στιγμή, η εξεταζόμενη δραστηριότητα τελειώσει, ξεκινήστε την αναζήτηση για μία ή περισσότερες δραστηριότητες που απομένουν.

ΒΗΜΑ 3) Εάν δεν υπάρχουν άλλες δραστηριότητες, η τρέχουσα εναπομένουσα δραστηριότητα γίνεται η επόμενη εξεταζόμενη δραστηριότητα. Επαναλάβετε το βήμα 1 και το βήμα 2, με τη νέα εξεταζόμενη δραστηριότητα. Εάν δεν έχουν απομείνει δραστηριότητες, μεταβείτε στο βήμα 4.

ΒΗΜΑ 4) Επιστρέψτε την ένωση των εξεταζόμενων δεικτών. Αυτοί είναι οι δείκτες δραστηριότητας που θα χρησιμοποιηθούν για τη μεγιστοποίηση της απόδοσης.

Επεξήγηση κώδικα

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

#define MAX_ACTIVITIES 12

Επεξήγηση κωδικού:

1. Περιλαμβάνονται αρχεία κεφαλίδας/τάξεις
2. Ένας μέγιστος αριθμός δραστηριοτήτων που παρέχεται από τον χρήστη.

using namespace std;

class TIME
{
    public:
    int hours;

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

Επεξήγηση κωδικού:

1. Ο χώρος ονομάτων για λειτουργίες ροής.
2. Ένας ορισμός κλάσης για το TIME
3. Χρονική σήμανση ώρας.
4. Ένας προεπιλεγμένος κατασκευαστής TIME
5. Οι ώρες μεταβλητές.

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

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

Επεξήγηση κωδικού:

1. Ορισμός τάξης από δραστηριότητα
2. Χρονικές σημάνσεις που ορίζουν μια διάρκεια
3. Όλες οι χρονικές σημάνσεις αρχικοποιούνται στο 0 στον προεπιλεγμένο κατασκευαστή

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

Επεξήγηση κωδικού:

1. Μέρος 1 του ορισμού της κλάσης χρονοπρογραμματιστή.
2. Το Considered Index είναι το σημείο εκκίνησης για τη σάρωση του παράταξη.
3. Ο δείκτης αρχικοποίησης χρησιμοποιείται για την εκχώρηση τυχαίων χρονικών σφραγίδων.
4. Ένας πίνακας αντικειμένων δραστηριότητας εκχωρείται δυναμικά χρησιμοποιώντας τον νέο τελεστή.
5. Ο προγραμματισμένος δείκτης καθορίζει την τρέχουσα θέση βάσης για την απληστία.

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

Επεξήγηση κωδικού:

1. Ο κατασκευαστής χρονοπρογραμματιστή – μέρος 2 του ορισμού της κλάσης χρονοπρογραμματιστή.
2. Το εξεταζόμενο ευρετήριο ορίζει την τρέχουσα έναρξη της τρέχουσας σάρωσης.
3. Η τρέχουσα άπληστη έκταση είναι απροσδιόριστη στην αρχή.

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);
 }
…
…

Επεξήγηση κωδικού:

1. Ένας βρόχος για την προετοιμασία των ωρών έναρξης και λήξης καθεμιάς από τις δραστηριότητες που έχουν προγραμματιστεί αυτήν τη στιγμή.
2. Αρχικοποίηση ώρας έναρξης.
3. Αρχικοποίηση χρόνου λήξης πάντα μετά ή ακριβώς την ώρα έναρξης.
4. Μια δήλωση εντοπισμού σφαλμάτων για την εκτύπωση των κατανεμημένων διάρκειων.

	public:
   		 Activity * activity_select(int);
};

Επεξήγηση κωδικού:

1. Μέρος 4 – το τελευταίο μέρος του ορισμού της κλάσης χρονοπρογραμματιστή.
2. Η συνάρτηση επιλογής δραστηριότητας παίρνει ως βάση έναν δείκτη αφετηρίας και διαιρεί την άπληστη αναζήτηση σε άπληστα υποπροβλήματα.

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

1. Χρησιμοποιώντας τον τελεστή ανάλυσης εύρους (::), παρέχεται ο ορισμός της λειτουργίας.
2. Ο εξεταζόμενος δείκτης είναι ο δείκτης που ονομάζεται κατά τιμή. Το greedy_extent είναι το αρχικοποιημένο μόλις ένα ευρετήριο μετά το εξεταζόμενο Ευρετήριο.

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

Επεξήγηση κωδικού:

1. Η βασική λογική- Η άπληστη έκταση περιορίζεται στον αριθμό των δραστηριοτήτων.
2. Οι ώρες έναρξης της τρέχουσας Δραστηριότητας ελέγχονται ως προγραμματισμένες πριν από την ολοκλήρωση της εξεταζόμενης δραστηριότητας (που δίνεται από το εξεταζόμενο ευρετήριο).
3. Όσο αυτό είναι δυνατό, εκτυπώνεται μια προαιρετική δήλωση εντοπισμού σφαλμάτων.
4. Προχωρήστε στο επόμενο ευρετήριο στον πίνακα δραστηριοτήτων

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Επεξήγηση κωδικού:

1. Ο υπό όρους ελέγχει εάν έχουν καλυφθεί όλες οι δραστηριότητες.
2. Εάν όχι, μπορείτε να επανεκκινήσετε το greedy σας με το θεωρούμενο Ευρετήριο ως τρέχον σημείο. Αυτό είναι ένα αναδρομικό βήμα που διαιρεί άπληστα τη δήλωση προβλήματος.
3. Εάν ναι, επιστρέφει στον καλούντα χωρίς περιθώρια επέκτασης της απληστίας.

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

Επεξήγηση κωδικού:

1. Η κύρια συνάρτηση που χρησιμοποιείται για την κλήση του προγραμματιστή.
2. Ένα νέο Scheduler δημιουργείται.
3. Η λειτουργία επιλογής δραστηριότητας, η οποία επιστρέφει έναν δείκτη δραστηριότητας τύπου επιστρέφει στον καλούντα μετά την ολοκλήρωση της άπληστης αποστολής.

Παραγωγή:

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

Περιορισμοί της άπληστης τεχνικής

Δεν είναι κατάλληλο για προβλήματα Greedy όπου απαιτείται λύση για κάθε υποπρόβλημα όπως η ταξινόμηση.

Σε τέτοια προβλήματα εξάσκησης αλγορίθμων Greedy, η μέθοδος Greedy μπορεί να είναι λανθασμένη. στη χειρότερη περίπτωση ακόμη και να οδηγήσει σε μια μη βέλτιστη λύση.

Επομένως, το μειονέκτημα των άπληστων αλγορίθμων είναι ότι δεν γνωρίζουν τι βρίσκεται μπροστά από την τρέχουσα άπληστη κατάσταση.

Ακολουθεί μια απεικόνιση του μειονεκτήματος της μεθόδου Greedy:

Στην άπληστη σάρωση που εμφανίζεται εδώ ως δέντρο (υψηλότερη τιμή υψηλότερη απληστία), μια κατάσταση αλγορίθμου στην τιμή: 40, είναι πιθανό να λάβει το 29 ως την επόμενη τιμή. Επιπλέον, η αποστολή του τελειώνει στο 12. Αυτό ανέρχεται σε μια τιμή 41.

Ωστόσο, εάν ο αλγόριθμος ακολουθούσε μια μη βέλτιστη διαδρομή ή υιοθέτησε μια στρατηγική κατάκτησης. τότε το 25 θα ακολουθείται από το 40 και η συνολική βελτίωση του κόστους θα είναι 65, η οποία αποτιμάται κατά 24 μονάδες υψηλότερη ως μη βέλτιστη απόφαση.

Παραδείγματα Greedy Algorithms

Οι περισσότεροι αλγόριθμοι δικτύωσης χρησιμοποιούν την άπληστη προσέγγιση. Ακολουθεί μια λίστα με μερικά παραδείγματα αλγορίθμων Greedy:

• Ο αλγόριθμος ελάχιστης έκτασης του Prim
• Πρόβλημα πωλητή ταξιδιού
• Γράφημα – Χρωματισμός χάρτη
• Ο αλγόριθμος ελάχιστων δέντρων του Kruskal
• Ο αλγόριθμος του Minimal Spanning Tree της Dijkstra
• Γράφημα – Κάλυμμα κορυφής
• Πρόβλημα με σακίδιο
• Πρόβλημα προγραμματισμού εργασιών

Σύνοψη

Συνοψίζοντας, το άρθρο όρισε το άπληστο παράδειγμα, έδειξε πώς η άπληστη βελτιστοποίηση και η αναδρομή μπορούν να σας βοηθήσουν να αποκτήσετε την καλύτερη λύση μέχρι ένα σημείο. Ο αλγόριθμος Greedy χρησιμοποιείται ευρέως για την επίλυση προβλημάτων σε πολλές γλώσσες ως αλγόριθμος Greedy Python, C, C#, PHP, Java, κ.λπ. Η επιλογή δραστηριότητας του παραδείγματος αλγορίθμου Greedy περιγράφηκε ως ένα στρατηγικό πρόβλημα που θα μπορούσε να επιτύχει τη μέγιστη απόδοση χρησιμοποιώντας την προσέγγιση greedy. Στο τέλος, εξηγήθηκαν τα μειονεκτήματα της χρήσης της άπληστης προσέγγισης.