Ternary Search
Η Ternary Search (τριαδική αναζήτηση), όπως και η δυαδική αναζήτηση, χρησιμεύει πολλές φορές για να αναζητήσουμε λύσεις στον χώρο των πιθανών λύσεων ενός προβλήματος. Ο αλγόριθμος είναι πολύ εύκολος στη κατανόηση και απαραίτητος για την επίλυση αρκετών προβλημάτων διαγωνισμών (κυρίως στο ICPC). Συνήθως το δύσκολο κομμάτι είναι να καταλάβει κανείς πότε μπορεί να τη χρησιμοποιήσει. Ενώ η binary search εφαρμόζεται σε συναρτήσεις μονότονες, η ternary search χρησιμεύει για να βρίσκουμε το μέγιστο ή το ελάχιστο σε συναρτήσεις που είναι unimodal ή μονότροπες (δηλαδή για ένα διάστημα στην αρχή είναι γνησίως φθίνουσες, μετά μπορεί να είναι σταθερές και μετά γνησίως αύξουσες) όπως, για παράδειγμα, οι παραβολές.
Περιγραφή αλγορίθμου
Ο αλγόριθμος, αν και μπορεί να υλοποιηθεί με τον ίδιο τρόπο και στην περίπτωση διακριτών συναρτήσεων (δηλαδή με πεδίο ορισμού κάποιο υποσύνολο των ακεραίων, όπως πχ οι ακολουθίες) και στη περίπτωση των συνεχών συναρτήσεων (δηλαδή αυτές που ορίζονται σε κάποιο διάστημα πραγματικών αριθμών και το πεδίο ορισμού τους περιλαμβάνει κάθε πραγματικό αριθμό σε αυτό το διάστημα), στη πρώτη περίπτωση υπάρχει μια έκδοσή του η οποία είναι πιο γρήγορη και πιο εύκολη στη κατανόηση και την υλοποίηση, οπότε θα αρχίσουμε από αυτή.
Αναζήτηση σε διακριτές συναρτήσεις
Ας πούμε ότι θέλουμε να αναζητήσουμε τη θέση ενός ελαχίστου στη συνάρτηση που παρουσιάζεται παρακάτω (Παρατηρήστε ότι αυτή η συνάρτηση είναι unimodal).
Ας θεωρήσουμε τη συνάρτηση η οποία δηλώνει τη κλίση (ή αλλιώς, τη παράγωγο) σε κάθε σημείο της . Τότε, παρατηρούμε ότι για το πρώτο σημαντικό διάστημα της η είναι αρνητική, στο δεύτερο ισούται με 0 και στο τρίτο είναι θετική.
Τώρα παρατηρούμε ότι στο σημείο ελαχίστου η κλίση της ευθείας θα είναι 0 ή (επειδή η συνάρτηση είναι διακριτή) θα ισχύει ότι αυτό το σημείο είναι το τελευταίο για το οποίο (οπότε θα είναι ). Έτσι ορίζουμε μια συνάρτηση predicate ως η οποία είναι μονότονη. Άρα, μπορούμε να εφαρμόσουμε binary search με αυτή τη συνάρτηση predicate, το οποίο υλοποιείται ως εξής εάν θέλουμε να ψάξουμε στο διάστημα :
int ternary_search(int lo, int hi) {
while (lo < hi) {
int mid = (lo + hi) / 2;
if (f(mid + 1) - f(mid) <= 0)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
Παρατηρήστε ότι αποκλείεται ποτέ το mid + 1 να βγει εκτός των ορίων lo, hi γιατί το mid το βρίσκουμε πάντα με στρογγυλοποίηση του μέσου όρου προς τα κάτω και, συνεπώς η μόνη πιθανότητα να βγούμε εκτός θα ήταν τα δύο άκρα να ισούνται, κάτι που δεν μπορεί να ισχύει γιατί τότε δεν θα έτρεχε το while loop. Προσέξτε επίσης ότι ακολουθούμε πάντα τη κατεύθυνση που μειώνει τη τιμή της συνάρτησης, κάτι που είναι λογικό γιατί αν είμαστε σε ένα από τα μονότονα κομμάτια αποκλείεται να είναι ποτέ βέλτιστο να κατευθυνθούμε προς μια μεγαλύτερη τιμή γιατί έτσι απομακρυνόμαστε από το σημείο ελαχίστου. Η πολυπλοκότητα είναι ίδια με αυτή της binary search, δηλαδή .
Αναζήτηση σε συνεχείς συναρτήσεις
Αν τώρα έχουμε μια συνάρτηση που ορίζεται σε ένα διάστημα πραγματικών αριθμών και είναι συνεχής τότε μπορούμε να βρούμε το σημείο ελαχίστου με μια ελαφρώς διαφορετική διαδικασία. Αντί για δύο μισά, χωρίζουμε το διάστημα σε 3 κομμάτια, το καθένα μεγέθους του αρχικού.
Ας πούμε ότι για να χωρίσουμε τη συνάρτηση στα τρία κομμάτια την κόβουμε στα σημεία και . Στόχος μας είναι να απορρίψουμε ένα από τα δύο ακριανά κομμάτια, στο οποίο ξέρουμε σίγουρα ότι δεν μπορεί να βρίσκεται η απάντηση. Αν λοιπόν ισχύει ότι συμπεραίνουμε ότι το βρίσκεται στο δεξιό μέρος μονοτονίας της και συνεπώς η απάντηση βρίσκεται αναγκαστικά αριστερά αυτού του σημείου. Άρα μπορούμε σωστά να αγνοήσουμε το δεξί ακριανό κομμάτι και να συνεχίσουμε την αναζήτηση στο διάστημα . Όμοια για την περίπτωση , πετάμε το αριστερό ακριανό κομμάτι. Τώρα αν ισχύει ότι σημαίνει ότι το και το βρίσκονται εκατέρωθεν του σημείου ελαχίστου, άρα μπορούμε οποιοδήποτε ακριανό κομμάτι χωρίς σφάλμα (ή ακόμα και τα δύο).
Ως προς την υλοποίηση, λόγω των μεγάλων σφαλμάτων που μπορεί να υπάρξουν με τη χρήση δεκαδικών αριθμών στον υπολογιστή είναι προτιμότερο να τρέχουμε τον αλγόριθμο για έναν σταθερό αριθμό βημάτων που ισούται περίπου με το οποίο παρατηρούμε ότι είναι και λίγο πιο αργό από τον αντίστοιχο αριθμό βημάτων που χρειαζόμαστε για τον αλγόριθμο σε ακεραίους. Επίσης, στο τέλος επιστρέφουμε την τιμή (lo + hi) / 2.0 για να προσεγγίσουμε καλύτερα το σημείο ελαχίστου.
const int STEPS = 100;
double ternary_search(double lo, double hi) {
for (int i = 0; i < STEPS; i++) {
double lmid = lo + (hi - lo) / 3.0;
double rmid = hi - (hi - lo) / 3.0;
if (f(lmid) < f(rmid))
hi = rmid;
else
lo = lmid;
}
return (lo + hi) / 2.0;
}
Παράδειγμα
Θα λύσουμε το πρόβλημα BICYCLE από το ΠΔΠ camp του 2016. Ακολουθεί η εκφώνηση:
Υπάρχει ένας ποδηλατόδρομος κατά μήκος ενός ποταμού και ψάχνουμε ποια είναι η βέλτιστη θέση για να τοποθετήσουμε έναν χώρο πάρκινγκ. Αν το πάρκινγκ τοποθετηθεί στη θέση (οποιοσδήποτε πραγματικός αριθμός) τότε η δυσκολία του κάθε ποδηλάτη ισούται με την απόστασή του από το επί μια σταθερά , αν βρίσκεται αριστερά του , ή μια σταθερά αν είναι δεξιά του . Η συνολική δυσκολία είναι ίση με το άθροισμα των δυσκολιών όλων των ποδηλατών. Δίνονται ερωτήματα:
1 x: Εισάγουμε έναν νέο ποδηλάτη στη θέση κατά μήκος του ποταμού.
2 x: Αφαιρούμε έναν ποδηλάτη από τη θέση (θα υπάρχει τουλάχιστον ένας).
3 a b: Ζητείται να τυπώσουμε την ελάχιστη συνολική δυσκολία αν μας δίνονται οι σταθερές που αναφέρθηκαν στην εκφώνηση (δηλαδή αν τοποθετήσουμε τη θέση του πάρκινγκ βέλτιστα).
Οι περιορισμοί είναι και .
Δοκιμάστε πρώτα να σκεφτείτε μόνοι σας μια λύση για να εξοικειωθείτε με το πρόβλημα.
Αρχικά θα αποδείξουμε μια πολύ χρήσιμη ιδιότητα.
Λήμμα 1: Είναι πάντα βέλτιστο να τοποθετούμε τη θέση του πάρκινγκ σε ακέραιες συντεταγμένες και μάλιστα σε συντεταγμένες ποδηλατών.
Απόδειξη: Έστω ότι τοποθετούμε το πάρκινγκ μεταξύ δύο διαδοχικών ποδηλατών και όπως φαίνεται στο παρακάτω σχήμα. Τα συμβολίζουν το πλήθος των ποδηλατών αριστερά και δεξιά των διαδοχικών αυτών ποδηλατών και αντίστοιχα οι αποστάσεις από τη θέση του πάρκινγκ . Θα διαχωρίσουμε δύο περιπτώσεις: την . Αυτή η τελευταία ποσότητα είναι αυτό που θα προστεθεί στην τωρινή απάντηση αν μετακινήσουμε τη θέση του πάρκινγκ στον ποδηλάτη . Αφού η ποσότητα είναι μη θετική σημαίνει ότι η νέα απάντηση θα είναι τουλάχιστον όσο καλή όσο η προηγούμενη (μπορεί και καλύτερη) άρα μπορούμε άνετα να κάνουμε τη μετακίνηση. Στην άλλη περίπτωση τότε θα μπορούμε να μετακινήσουμε αντίστοιχα τη θέση του πάρκινγκ στον δεξιό ποδηλάτη και να έχουμε διαφορά στη λύση ίση με άρα πάλι η λύση που λαμβάνουμε είναι καλύτερη από το να τοποθετήσουμε το πάρκινγκ ενδιάμεσα στους ποδηλάτες.
Άρα μια εύκολη λύση σε (αν θεωρήσουμε ότι έχουμε ποδηλάτες) είναι να περνάμε γραμμικά όλους τους ποδηλάτες μετά από κάθε αλλαγή και να υπολογίζουμε σε ποια θα ήταν η λύση αν βάζαμε το πάρκινγκ σε αυτούς. Για να απαντήσουμε στα ερωτήματα σε χρόνο καλύτερο από γραμμικό (ενώ τις αναβαθμίσεις εξακολουθούμε να τις κάνουμε γραμμικά) θα προσπαθήσουμε να ελέγξουμε αν μπορούμε να εφαρμόσουμε ternary search. Πράγματι, παρατηρούμε ότι για κάθε ποδηλάτη η συνάρτηση κόστους του μεταβάλλεται σύμφωνα με τη θέση του πάρκινγκ σαν τη συνάρτηση της απόλυτης τιμής και επειδή δουλεύουμε σε ακέραιες συντεταγμένες μπορούμε να θεωρήσουμε ότι αυτή είναι η κυρτή. Κυρτή είναι μια συνάρτηση όταν η κλίση της μπορεί μόνο να αυξηθεί όσο αυξάνεται το , δηλαδή η παράγωγός της είναι αύξουσα ή, για διακριτές συναρτήσεις: (αντίστοιχα είναι κοίλη όταν η παράγωγος είναι φθίνουσα). Αποδεικνύεται επίσης εύκολα ότι το άθροισμα κυρτών συναρτήσεων είναι κι αυτό κυρτή συνάρτηση. Επειδή λοιπόν το συνολικό κόστος για μια δοσμένη θέση είναι το άθροισμα του κόστους κάθε ποδηλάτη συμπεραίνουμε ότι η συνάρτηση πάνω στην οποία ψάχνουμε (αν περιοριστούμε μόνο σε ακέραιες συντεταγμένες) είναι κυρτή άρα και unimodal και συνεπώς μπορούμε να αναζητήσουμε τη λύση με ternary search. Μπορούμε να τρέξουμε την ternary search πάνω σε ακέραιες συντεταγμένες και χρησιμοποιώντας τα μερικά αθροίσματα που έχουμε υπολογίσει να βρούμε τη λύση συνολικά σε .
Μία σημαντική παρατήρηση είναι ότι θα μπορούσαμε να κάνουμε ternary search και μόνο αν περιοριστούμε στις θέσεις των ποδηλατών, γιατί ακόμα κι έτσι η συνάρτηση θα είναι κυρτή. Αν όμως απλά ταξινομήσουμε τους ποδηλάτες και κάνουμε αναζήτηση πάνω στις θέσεις τους μπορεί η λύση να μην είναι σωστή. Αυτό συμβαίνει διότι αν υπάρχουν δύο ποδηλάτες με ίσα τότε μπορεί να υπάρξουν δύο διαδοχικά σημεία με ίδια τιμή σε ένα από τα διαστήματα μονοτονίας και αυτό σημαίνει ότι η συνάρτηση δεν θα είναι unimodal! Το σωστό είναι αφού ταξινομήσουμε τους ποδηλάτες με βάση τη θέση τους, να κρατήσουμε από μια φορά τη κάθε θέση (δηλαδή όλα τα στοιχεία να είναι διαφορετικά).
Το μόνο που μένει να κάνουμε είναι να υλοποιήσουμε τα ερωτήματα αλλαγών γρήγορα. Αυτό μπορεί να γίνει είτε χρησιμοποιώντας ένα Binary Indexed Tree είτε ένα Treap για παράδειγμα. Έτσι η πολυπλοκότητα πέφτει σε η οποία είναι αρκετή για να λύσει το πρόβλημα πλήρως. Μπορούμε μάλιστα να την βελτιώσουμε κι άλλο σε κάνοντας την τριαδική αναζήτηση παράλληλα με την εύρεση των μερικών αθροισμάτων πάνω στη δομή δεδομένων που επιλέξαμε.