Category Archives: Έρευνα – Εκπαίδευση

Σειριακή και Δυαδική Αναζήτηση

Εισαγωγή

Το πρόβλημα της αναζήτησης το συναντάμε πολλές φορές στην καθημερινότητά μας. Για παράδειγμα, για την αγορά ενός προϊόντος θα πρέπει να αναζητήσουμε σε μία λίστα από προϊόντα του καταστήματος για να βρούμε αυτό που ψάχνουμε. Επίσης, κατά την αναζήτηση μίας επαφής στο κινητό μας χρειάζεται να σκρολάρουμε πολλές φορές για να βρούμε την επαφή που ψάχνουμε ή να γράψουμε το όνομα του αποστολέα στην “μηχανή αναζήτησης” του κινητού και να κάνει αυτό την δουλειά για εμάς. Καταμετρώντας τον αριθμό παραδειγμάτων που συναντάμε το πρόβλημα της αναζήτησης διαπιστώνουμε εύκολα ότι ακόμα και για την πιο μικρή εργασία μας πρέπει να κάνουμε αναζήτηση.

Σε αντιστοιχία με τον πραγματικό κόσμο, η αναζήτηση είναι ένα σημαντικό πρόβλημα και στον εικονικό. Για παράδειγμα η αναζήτηση όλων των φίλων ενός ατόμου σε έναν 2D πίνακα όπου οι σειρές και οι στήλες αναπαριστούν άτομα και κάθε κελί παίρνει τιμές 0 ή 1 αν δύο άτομα είναι φίλοι. Μία τέτοια εργασία  ενδέχεται να κάνει μία ιστοσελίδα κοινωνικής δικτύωσης.

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

Σειριακή αναζήτηση

Η σειριακή αναζήτηση είναι ένας αλγόριθμος ο οποίος σαρώνει έναν πίνακα μέχρι να βρει την πρώτη εμφάνιση ενός στοιχείου που αναζητείται. Το στοιχείο αυτό αναφέρετε ως κλειδί (key). Ένας απλός αλγόριθμος σε μορφή ψευδοκώδικα για αναζήτηση σε μονοδιάστατο πίνακα είναι ο παρακάτω

     Είσοδος: Ένας μονοδιάστατος πίνακας Α[Ν], ένα κλειδί Χ 
     Έξοδος:  Η θέση του πίνακα που βρέθηκε το κλειδί αλλιώς -1 
     i = 0 
     βρέθηκε = ψευδής 
     θέση = 0
     Όσο i < N και βρέθηκε == αληθής επανάλαβε
          Άν X == A[i] τότε
               βρέθηκε = αληθής
               θέση = i
          Τέλος_αν
          i = i + 1
      Τέλος_όσο
      Αν βρέθηκε == αληθής τότε
            Τύπωσε θέση
      Αλλιώς
            Τύπωσε -1
       Τέλος_αν

Δίνοντας ως είσοδο έναν μονοδιάστατο πίνακα μεγέθους Ν και ένα κλειδί Χ ο αλγόριθμος τυπώνει την θέση του πίνακα που βρέθηκε το κλειδί. Για να το πετύχει αυτό σαρώνει επαναληπτικά τον πίνακα μέχρις ότου ένας μετρητής να φτάσει το μέγεθος του πίνακα ή μέχρι να βρεθεί το κλειδί αν υπάρχει στον πίνακα. (Στις περισσότερες γλώσσες προγραμματισμού οι πίνακες ξεκινούν την αρίθμηση τους από την μηδενική θέση - έτσι και εδώ ακολουθήθηκε αυτή η σύμβαση). Έπειτα, ανάλογα με το αν βρέθηκε ή όχι το κλειδί "τυπώνετε στην οθόνη" είτε η θέση είτε η τιμή -1.

Το πρόβλημα της αναζήτησης

Ο αλγόριθμος αυτός είναι απλός και ικανοποιεί τις ανάγκες μας για αναζήτηση παρόλα αυτά όταν η είσοδος είναι πολύ μεγάλη (δλδ. το μέγεθος του πίνακα) τότε αυτή η διαδικασία είναι πολύ χρονοβόρα. Φανταστείτε ότι έχετε έναν τηλεφωνικό κατάλογο με 10 ονόματα. Αναζητώντας όλα τα άτομα 1 προς 1 σύντομα θα βρείτε αυτό που ψάχνετε. Αν όμως είχατε 5000 ονόματα; Η αναζήτηση θα κρατούσε πολύ περισσότερη ώρα.

Διαισθητικά είδαμε ότι το μέγεθος του πίνακα είναι αυτό που επηρεάζει την απόδοση, όμως, δεν είναι μόνο αυτό. Ένας ακόμη παράγοντας που επηρεάζει την απόδοση σε αντιστοιχία με το μέγεθος του πίνακα είναι ο αριθμός συγκρίσεων. Για να γίνουμε πιο κατανοητοί θα μελετήσουμε δύο περιπτώσεις. Στη πρώτη περίπτωση (στη καλύτερη) το στοιχείο που αναζητούμε βρίσκετε στην πρώτη θέση του πίνακα. Οπότε απαιτείται μία μόνο σύγκριση. Αυτό το σενάριο είναι το καλύτερο και ο αλγόριθμος είναι πολύ αποδοτικός. Αντίθετα στην δεύτερη περίπτωση (στην χειρότερη) ο αλγόριθμος δεν βρίσκει το στοιχείο στον πίνακα είτε το βρίσκει στην τελευταία θέση. Για να το γνωρίζει όμως αυτό θα πρέπει να ψάξει ολόκληρο το πίνακα άρα θα πρέπει να κάνει τόσες συγκρίσεις όσες το μέγεθος του πίνακα. Άρα αν ο πίνακας είναι μεγέθους Ν απαιτούνται Ν συγκρίσεις. Άρα λέμε ότι ο χρόνος εκτέλεσης της αναζήτησης στην χειρότερη περίπτωση είναι γραμμικός. Ενώ ο χρόνος εκτέλεσης στην καλύτερη περίπτωση είναι σταθερός.

Είναι όμως αυτός ο αλγόριθμος ο καλύτερος ή μπορούμε να έχουμε αλγορίθμους με μικρότερο χρόνο εκτέλεσης;

Δυαδική Αναζήτηση

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

Ας πούμε ότι αναζητούμε τον όρο "φάσμα". Ανοίγουμε το λεξικό στη μέση και πέφτουμε στο γράμμα "κ". Γνωρίζουμε ότι η λέξη που ψάχνουμε βρίσκεται στο δεξί τμήμα του λεξικού οπότε αγνοούμε τις λέξεις στο διάστημα α-κ. Εφαρμόζουμε την ίδια τεχνική στο διάστημα κ-ω και πέφτουμε στο γράμμα "τ". Πάλι, γνωρίζουμε ότι στο διάστημα κ-τ δεν υπάρχει η λέξη άρα ψάχνουμε με τον ίδιο τρόπο στο διάστημα τ-ω. Επαναλαμβάνουμε αυτήν την διαδικασία μέχρις ότου βρούμε την σελίδα που περιέχει το γράμμα "φ". Όπως διαπιστώνουμε, αυτή η προσέγγιση είναι καλύτερη και πιο αποδοτική από την σειριακή αναζήτηση. Αυτός ο τρόπος αναζήτησης ονομάζεται δυαδική αναζήτηση και είναι ιδιαίτερα δημοφιλής. Παρακάτω παρουσιάζουμε ένα ψευδοκώδικα

     Είσοδος: Ένας ταξινομημένος μονοδιάστατος πίνακας Α[Ν], λέξη κλειδί Χ
     Έξοδος:  Η θέση του πίνακα που βρέθηκε το κλειδί αλλιώς -1 
     θέση = [Ν/2]
     βρέθηκε = ψευδής
     Όσο θέση >= 0 και θέση < Ν και βρέθηκε == ψευδής επανάλαβε Αν Α[θέση] == Χ τότε βρέθηκε = αληθής Αλλιώς Αν Χ > Α[θέση] τότε 
                 θέση = θέση + [θέση/2]
              Αλλιώς
                 θέση = θέση - [θέση/2]
           Τέλος_αν
         Τέλος_αν
     Τέλος_όσο 
     Αν βρέθηκε == αληθής τότε
        Τύπωσε θέση
     Αλλιώς 
         Τύπωσε -1 
    Τέλος_αν

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

Παράδειγμα εκτέλεσης αλγορίθμου

Ένα παράδειγμα εκτέλεσης παρουσιάζεται παρακάτω:

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

Δυαδικό δένδρο

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

Στην χειρότερη περίπτωση, το κλειδί που αναζητούμε βρίσκεται στα φύλλα. Επομένως, ο αριθμός των συγκρίσεων που πρέπει να κάνουμε ισούται με το ύψος του δυαδικού δένδρου. Για να υπολογίσουμε το συνολικό αριθμό των στοιχείων ανά επίπεδο εργαζόμαστε ως εξής: στο πρώτο επίπεδο έχουμε ένα στοιχείο, στο δεύτερο 2 στοιχεία, στο τρίτο 4 κοκ. Παρατηρούμε ότι καθώς αυξάνεται ο αριθμός των επιπέδων τα στοιχεία αυξάνονται εκθετικά. Οπότε, αν ορίσουμε το τελευταίο επίπεδο ως k . Θα πρέπει \( 2^k +1 = N \). Λογαριθμίζοντας, προκύπτει \( k = log_2(N-1) \).

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

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

Κάποιες χρήσιμες πηγές

1. Δυαδική Αναζήτηση - python
2. Δυαδική Αναζήτηση - παράδειγμα προγράμματος στην c