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

Τι είναι ένας αλγόριθμος Greedy;

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

Η επίλυση ενός προβλήματος με την άπληστη προσέγγιση έχει δύο στάδια:

1. Σάρωση της λίστας στοιχείων
2. Απόδοσης

Και τα δύο στάδια εκτελούνται παράλληλα καθώς ο πίνακας εισόδου διαιρείται προοδευτικά.

Για να ακολουθήσετε την άπληστη προσέγγιση, η γνώση της αναδρομής και της εναλλαγής περιβάλλοντος σας βοηθά. tracε τον κώδικα. Το άπληστο παράδειγμα μπορεί να περιγραφεί με ένα ζεύγος αναγκαίων και επαρκών δηλώσεων.

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

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

Έχοντας θέσει τη θεωρία σε ισχύ, ας δούμε την ιστορία πίσω από την προσέγγιση της άπληστης αναζήτησης.

History of Greedy Algorithms

Ακολουθούν τα σημαντικά ορόσημα στην ιστορία των άπληστων αλγορίθμων:

• Οι άπληστοι αλγόριθμοι σχεδιάστηκαν για πρώτη φορά ως αλγόριθμοι γραφικού περιπάτου τη δεκαετία του 1950.
• Ο Edsger Dijkstra ανέπτυξε τον αλγόριθμο συντομότερης διαδρομής για να συντομεύσει τις διαδρομές στην ολλανδική πρωτεύουσα, το Άμστερνταμ.
• Την ίδια δεκαετία, οι Prim και Kruskal ανέπτυξαν στρατηγικές βελτιστοποίησης που ελαχιστοποιούν το κόστος διαδρομής κατά μήκος σταθμισμένων διαδρομών για την κατασκευή ελάχιστων δέντρων επέκτασης.
• Τη δεκαετία του '70, οι Αμερικανοί ερευνητές Cormen, Leiserson, Rivest και Stein περιέγραψαν την αναδρομική υποδόμηση άπληστων λύσεων στο κλασικό τους έργο. Introduction to Algorithms εγχειρίδιο
• Το παράδειγμα της άπληστης αναζήτησης καταγράφηκε ως ξεχωριστή στρατηγική βελτιστοποίησης στα αρχεία του NIST το 2005.
• Μέχρι σήμερα, πρωτόκολλα ιστού όπως το Open Shortest Path First (OSPF) και πολλά πρωτόκολλα μεταγωγής πακέτων χρησιμοποιούν την άπληστη στρατηγική για να ελαχιστοποιήσουν τον χρόνο μετάβασης σε ένα δίκτυο.

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

Η λογική περιορίζεται σε μια δυαδική επιλογή σε κάθε στάδιο — «άπληστος» ή «όχι άπληστος» — με βάση την κατεύθυνση που ακολουθεί ο αλγόριθμος για να προχωρήσει.

Για παράδειγμα, ο αλγόριθμος του Dijkstra αναγνωρίζει τους κεντρικούς υπολογιστές στο Διαδίκτυο αξιολογώντας μια συνάρτηση κόστους σε κάθε βήμα. Η τιμή που επιστρέφει η συνάρτηση κόστους καθορίζει εάν η επόμενη διαδρομή είναι «άπληστη» ή «μη άπληστη».

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

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

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

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

Γιατί να Χρησιμοποιήσετε την Απλήστευση;

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

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

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

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

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

Το κόστος εκτέλεσης μιας δραστηριότητας είναι η διάρκειά της, η οποία υπολογίζεται ως (λήξη – έναρξη).

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

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

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

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

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

Βήμα 4) Επιστρέψτε την ένωση των θεωρούμενων δεικτών — αυτοί είναι οι δείκτες δραστηριότητας που μεγιστοποιούν την απόδοση.

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

Code εξήγηση

#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. Η συνάρτηση init_index χρησιμοποιείται για την αντιστοίχιση τυχαίων χρονικών σημάνσεων κατά τη διάρκεια της ρύθμισης.
4. Ένας πίνακας αντικειμένων Δραστηριότητας κατανέμεται δυναμικά με τον νέο τελεστή.
5. Ο προγραμματισμένος δείκτης διατηρεί το τρέχον άπληστο αποτέλεσμα.

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

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

1. Ο κατασκευαστής του χρονοπρογραμματιστή — μέρος 2 του ορισμού της κλάσης.
2. Το considered_index σηματοδοτεί την έναρξη της τρέχουσας σάρωσης.
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);
 }
&#8230;
&#8230;

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

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

	public:
   		 Activity * activity_select(int);
};

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

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

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

1. Ο τελεστής ανάλυσης εμβέλειας (::) συνδέει τον ορισμό της συνάρτησης με την κλάση Scheduler.
2. Η συνάρτηση considered_index διαβιβάζεται με value και η συνάρτηση 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++;
    	}
&#8230;
...

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

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

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

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

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

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

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

1. Η συνάρτηση main καλεί τον Χρονοπρογραμματιστή.
2. Δημιουργείται ένα νέο αντικείμενο Scheduler.
3. Η συνάρτηση activity_select() επιστρέφει έναν δείκτη δραστηριότητας στον καλούντα μόλις ολοκληρωθεί η άπληστη αναζήτηση.

Παραγωγή:

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

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

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

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

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

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

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

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

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

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

• Αλγόριθμος ελάχιστου εκτεινόμενου δέντρου του Prim
• Πρόβλημα Περιοδεύοντος Πωλητή (κατά προσέγγιση)
• Χρωματισμός Γραφήματος Χάρτη
• Αλγόριθμος Ελάχιστου Δέντρου Εκτεινόμενου Δέντρου του Kruskal
• Αλγόριθμος Συντομότερης Διαδρομής του Dijkstra
• Κάλυμμα Κορυφής Γραφήματος
• Πρόβλημα με σακίδιο
• Ακολουθία εργασιών με προθεσμίες

Συχνές Ερωτήσεις