Οι άπληστοι αλγόριθμοι εξηγούνται με παραδείγματα

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

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

  • Ωμής βίας
  • Διαίρει και βασίλευε
  • Άπληστος προγραμματισμός
  • Δυναμικός προγραμματισμός για να αναφέρουμε μερικά. Σε αυτό το άρθρο, θα μάθετε για το τι είναι ένας άπληστος αλγόριθμος και πώς μπορείτε να χρησιμοποιήσετε αυτήν την τεχνική για να λύσετε πολλά προβλήματα προγραμματισμού που διαφορετικά δεν φαίνονται ασήμαντα.

Φανταστείτε ότι πρόκειται για πεζοπορία και ο στόχος σας είναι να φτάσετε στην υψηλότερη δυνατή κορυφή. Έχετε ήδη τον χάρτη πριν ξεκινήσετε, αλλά υπάρχουν χιλιάδες πιθανές διαδρομές που εμφανίζονται στον χάρτη. Είστε πολύ τεμπέλης και απλά δεν έχετε το χρόνο να αξιολογήσετε καθένα από αυτά. Βιδώστε τον χάρτη! Ξεκινήσατε την πεζοπορία με μια απλή στρατηγική - να είστε άπληστοι και κοντόφθαλμοι. Απλά ακολουθήστε μονοπάτια που έχουν μεγαλύτερη κλίση προς τα πάνω. Αυτό φαίνεται σαν μια καλή στρατηγική για πεζοπορία. Αλλά είναι πάντα το καλύτερο;

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

Επίσημος ορισμός

Ας υποθέσουμε ότι έχετε μια αντικειμενική συνάρτηση που πρέπει να βελτιστοποιηθεί (είτε μεγιστοποιηθεί είτε ελαχιστοποιηθεί) σε ένα δεδομένο σημείο. Ένας άπληστος αλγόριθμος κάνει άπληστες επιλογές σε κάθε βήμα για να διασφαλίσει ότι η αντικειμενική λειτουργία είναι βελτιστοποιημένη. Ο αλγόριθμος Greedy έχει μόνο ένα πλάνο για να υπολογίσει τη βέλτιστη λύση, ώστε να μην επιστρέψει ποτέ και να αντιστρέψει την απόφαση.

Οι άπληστοι αλγόριθμοι έχουν μερικά πλεονεκτήματα και μειονεκτήματα:

  • Είναι πολύ εύκολο να βρείτε έναν άπληστο αλγόριθμο (ή ακόμα και πολλαπλούς άπληστους αλγόριθμους) για ένα πρόβλημα. Η ανάλυση του χρόνου εκτέλεσης για τους άπληστους αλγόριθμους θα είναι γενικά πολύ πιο εύκολη από ό, τι για άλλες τεχνικές (όπως το Divide και η κατάκτηση). Για την τεχνική Divide and winer, δεν είναι σαφές εάν η τεχνική είναι γρήγορη ή αργή. Αυτό συμβαίνει επειδή σε κάθε επίπεδο υποτροπής το μέγεθος των μικρότερων και ο αριθμός των υπο-προβλημάτων αυξάνεται.
  • Το δύσκολο μέρος είναι ότι για τους άπληστους αλγόριθμους πρέπει να εργαστείτε πολύ πιο σκληρά για να κατανοήσετε τα ζητήματα ορθότητας. Ακόμα και με τον σωστό αλγόριθμο, είναι δύσκολο να αποδειχθεί γιατί είναι σωστός. Η απόδειξη ότι ένας άπληστος αλγόριθμος είναι σωστός είναι περισσότερο τέχνη παρά επιστήμη. Περιλαμβάνει πολλή δημιουργικότητα. Συνήθως, η εμφάνιση ενός αλγορίθμου μπορεί να φαίνεται ασήμαντη, αλλά η απόδειξη ότι είναι πραγματικά σωστή, είναι ένα εντελώς διαφορετικό πρόβλημα.

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

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

  • Σας δίνεται ένα σύνολο προγραμμάτων Ν διαλέξεων για μια μέρα στο πανεπιστήμιο. Το πρόγραμμα για μια συγκεκριμένη διάλεξη έχει τη μορφή ( ώρα, ώρα f ) όπου ο χρόνος αντιπροσωπεύει την ώρα έναρξης για τη συγκεκριμένη διάλεξη και παρομοίως ο χρόνος f αντιπροσωπεύει τον χρόνο λήξης. Λαμβάνοντας υπόψη μια λίστα με τα προγράμματα διαλέξεων Ν, πρέπει να επιλέξουμε το μέγιστο σύνολο διαλέξεων που θα πραγματοποιηθούν κατά τη διάρκεια της ημέρας έτσι ώστε   καμία από τις διαλέξεις να μην αλληλεπικαλύπτεται μεταξύ τους, δηλαδή εάν η διάλεξη Li και Lj περιλαμβάνονται στην επιλογή μας, τότε η ώρα έναρξης του j > = χρόνος λήξης i ή αντίστροφα .
  • Ο φίλος σας εργάζεται ως σύμβουλος στρατόπεδων και είναι υπεύθυνος για την οργάνωση δραστηριοτήτων για ένα σύνολο κατασκηνωτών. Ένα από τα σχέδιά του είναι η ακόλουθη άσκηση mini-triathlon: κάθε διαγωνιζόμενος πρέπει να κολυμπήσει 20 γύρους πισίνας, μετά ποδήλατο 10 μίλια και στη συνέχεια να τρέξει 3 μίλια.
  • Το σχέδιο είναι να στείλετε τους διαγωνιζόμενους με σταδιακό τρόπο, μέσω του ακόλουθου κανόνα: οι διαγωνιζόμενοι πρέπει να χρησιμοποιούν το pool ένα κάθε φορά. Με άλλα λόγια, ο πρώτος διαγωνιζόμενος κολυμπά τους 20 γύρους, βγαίνει και ξεκινά ποδηλασία.
  • Μόλις αυτό το πρώτο άτομο βγει από την πισίνα, ένας δεύτερος διαγωνιζόμενος αρχίζει να κολυμπά στους 20 γύρους. μόλις βγει έξω και αρχίσει ποδηλασία, ένας τρίτος διαγωνιζόμενος αρχίζει να κολυμπά και ούτω καθεξής.
  • Κάθε διαγωνιζόμενος έχει έναν προβλεπόμενο χρόνο κολύμβησης, έναν προβλεπόμενο χρόνο ποδηλασίας και έναν προβλεπόμενο χρόνο λειτουργίας. Ο φίλος σας θέλει να αποφασίσει για ένα πρόγραμμα για το triathlon: μια σειρά με την οποία θα ακολουθήσει τις εκκινήσεις των διαγωνιζομένων.
  • Ας πούμε ότι ο χρόνος ολοκλήρωσης ενός προγράμματος είναι ο πρώτος χρόνος κατά τον οποίο όλοι οι διαγωνιζόμενοι θα τελειώσουν με τα τρία σκέλη του τριάθλου, υποθέτοντας ότι οι προβολές του χρόνου είναι ακριβείς. Ποια είναι η καλύτερη παραγγελία για την αποστολή ατόμων, εάν θέλει να ολοκληρωθεί το συντομότερο δυνατόν ολόκληρος ο διαγωνισμός; Πιο συγκεκριμένα, δώστε έναν αποτελεσματικό αλγόριθμο που παράγει ένα πρόγραμμα του οποίου ο χρόνος ολοκλήρωσης είναι όσο το δυνατόν μικρότερος

Το πρόβλημα προγραμματισμού διαλέξεων

Ας δούμε τις διάφορες προσεγγίσεις για την επίλυση αυτού του προβλήματος.

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

Πρώτα η πρώτη ώρα έναρξης

Μικρότερο διάστημα Πρώτα,  δηλαδή καταλήγετε να επιλέγετε τις διαλέξεις με τη σειρά του συνολικού τους διαστήματος που δεν είναι τίποτα άλλο από τους   finish time - start time. Και πάλι, αυτή η λύση δεν είναι σωστή. Κοιτάξτε την ακόλουθη περίπτωση.

Πρώτο μικρότερο διάστημα

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

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

Πρώτα το ελάχιστο διάστημα σύγκρουσης

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

Πρώτα ο πρώτος χρόνος ολοκλήρωσης . Αυτή είναι η προσέγγιση που μας δίνει πάντα την βέλτιστη λύση σε αυτό το πρόβλημα. Λάβαμε πολλές γνώσεις από προηγούμενες προσεγγίσεις και τελικά καταλήξαμε σε αυτήν την προσέγγιση. Ταξινομούμε τα διαστήματα ανάλογα με την αυξανόμενη σειρά των χρόνων λήξης τους και στη συνέχεια αρχίζουμε να επιλέγουμε διαστήματα από την αρχή. Κοιτάξτε τον παρακάτω ψευδο κώδικα για περισσότερη σαφήνεια.

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

Πότε χρησιμοποιούμε τους άπληστους αλγόριθμους

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

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

Πρόβλημα συντομότερης διαδρομής:

Ελάχιστο πρόβλημα έκτασης δέντρου σε ένα γράφημα

Πρόβλημα κωδικοποίησης Huffman

Πρόβλημα Κ Κέντρων