Εφαρμογή Greedy Reasoning με αλγόριθμους - ανδρείκελα

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

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

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

• Το ελάχιστο δέντρο του Kruskal (MST): Αυτός ο αλγόριθμος δείχνει μια από τις αρχές των άπληστων αλγορίθμων που οι άνθρωποι ίσως δεν σκέφτονται αμέσως. Σε αυτή την περίπτωση, ο αλγόριθμος επιλέγει την άκρη μεταξύ δύο κόμβων με τη μικρότερη τιμή και όχι τη μέγιστη τιμή, όπως η λέξη άπληστος μπορεί αρχικά να μεταδώσει. Αυτός ο τύπος αλγορίθμου μπορεί να σας βοηθήσει να βρείτε τη συντομότερη διαδρομή μεταξύ δύο τοποθεσιών σε ένα χάρτη ή να εκτελέσετε άλλες εργασίες σχετικές με γραφήματα.
• MST του Prim: Αυτός ο αλγόριθμος διαιρεί σε μισό ένα μη κατευθυνόμενο γράφημα (το ένα με ποια κατεύθυνση δεν θεωρείται). Στη συνέχεια επιλέγει την άκρη που συνδέει τα δύο μισά έτσι ώστε το συνολικό βάρος των δύο ημίσεων να είναι το μικρότερο που μπορεί να είναι. Μπορεί να βρείτε αυτόν τον αλγόριθμο που χρησιμοποιείται σε ένα παιχνίδι λαβυρίνθων για να εντοπίσετε τη μικρότερη απόσταση μεταξύ της έναρξης και του τερματισμού του λαβυρίνθου.
• Huffman Κωδικοποίηση: Αυτός ο αλγόριθμος είναι αρκετά διάσημος στους υπολογιστές επειδή αποτελεί τη βάση για πολλές τεχνικές συμπίεσης δεδομένων. Ο αλγόριθμος εκχωρεί έναν κώδικα σε κάθε μοναδική καταχώρηση δεδομένων σε μια ροή καταχωρήσεων, έτσι ώστε η πιο συχνά χρησιμοποιούμενη καταχώρηση δεδομένων να λαμβάνει τον συντομότερο κώδικα. Για παράδειγμα, το γράμμα E θα λαμβάνει κανονικά τον συντομότερο κώδικα κατά τη συμπίεση αγγλικού κειμένου, επειδή το χρησιμοποιείτε συχνότερα από οποιοδήποτε άλλο γράμμα στο αλφάβητο. Αλλάζοντας την τεχνική κωδικοποίησης, μπορείτε να συμπιέσετε το κείμενο και να το καταστήσετε σημαντικά μικρότερο, μειώνοντας τον χρόνο μετάδοσης.