Άπληστος αλγόριθμος με παραδείγματα: Άπληστη μέθοδος & Πλησιάζω

Πίνακας περιεχομένων:

Anonim

Τι είναι ένας άπληστος αλγόριθμος;

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

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

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

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

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

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

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

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

Σε αυτό το Greedy αλγόριθμο σεμινάριο, θα μάθετε:

  • Ιστορία των άπληστων αλγορίθμων
  • Άπληστες στρατηγικές και αποφάσεις
  • Χαρακτηριστικά της άπληστης προσέγγισης
  • Γιατί να χρησιμοποιήσω την άπληστη προσέγγιση;
  • Τρόπος επίλυσης του προβλήματος επιλογής δραστηριότητας
  • Αρχιτεκτονική της άπληστης προσέγγισης
  • Μειονεκτήματα των άπληστων αλγορίθμων

Ιστορία των άπληστων αλγορίθμων

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

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

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

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

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

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

Χαρακτηριστικά της άπληστης προσέγγισης

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

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

Γιατί να χρησιμοποιήσω την άπληστη προσέγγιση;

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

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

Τρόπος επίλυσης του προβλήματος επιλογής δραστηριότητας

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

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

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

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

Αρχιτεκτονική της άπληστης προσέγγισης

ΒΗΜΑ 1)

Σάρωση της λίστας των δαπανών δραστηριότητας, ξεκινώντας με το ευρετήριο 0 ως το εξεταζόμενο ευρετήριο.

ΒΗΜΑ 2)

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

ΒΗΜΑ 3)

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

ΒΗΜΑ 4)

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

Αρχιτεκτονική της Άπληστης Προσέγγισης

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

#include#include#include#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. Το θεωρούμενο ευρετήριο είναι το σημείο εκκίνησης για τη σάρωση του πίνακα.
  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. Εάν όχι, μπορείτε να κάνετε επανεκκίνηση της άπλησής σας με το θεωρούμενο Ευρετήριο ως το τρέχον σημείο. Αυτό είναι ένα αναδρομικό βήμα που διαιρεί με απληστία τη δήλωση προβλήματος.
  3. Εάν ναι, επιστρέφει στον καλούντα χωρίς δυνατότητα επέκτασης της απληστίας.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

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

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

Παραγωγή:

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

Μειονεκτήματα των άπληστων αλγορίθμων

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

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

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

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

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

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

Παραδείγματα άπληστων αλγορίθμων

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

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

Περίληψη:

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