Αναζήτηση Κατά Βάθος

Ο αλγόριθμος Αναζήτησης Κατά Βάθος (DFS - Depth-first search) επιτυγχάνει διάσχιση ή αναζήτηση σε δέντρο ή γράφημα. Η διάσχιση ξεκινά από τη ρίζα και εξερευνά όσο το δυνατόν περισσότερο κατά μήκος κάθε κλαδί του δέντρου μέχρι να φτάσει σε αδιέξοδο.
Μια έκδοση της αναζήτησης κατά βάθος ερευνήθηκε κατά τον 19ο αιώνα από τον Γάλλο μαθηματικό Charles Pierre Trémaux  ως μια στρατηγική για την επίλυση λαβυρίνθων. Ένας λαβύρινθος μπορεί να αναπαρασταθεί ως γράφος θεωρώντας κάθε διασταύρωση του λαβύρινθου ως κόμβος και κάθε εσωτερική διαδρομή ως ακμή .

Ορισμός

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

Περιγραφή

Η περιγραφή του αλγορίθμου DFS είναι η ακόλουθη:

1  Βάλε την αρχική κατάσταση στο μέτωπο της αναζήτησης.
2  Αν το μέτωπο αναζήτησης είναι κενό τότε σταμάτησε.
3  Βγάλε την πρώτη κατάσταση από το μέτωπο της αναζήτησης.
4  Αν είναι η κατάσταση μέλος του κλειστού συνόλου τότε πήγαινε στο βήμα 2.
5  Αν η κατάσταση είναι μια από τις τελικές, τότε ανέφερε τη λύση.
6  Αν θέλεις κι άλλες λύσεις πήγαινε στο βήμα 2. Αλλιώς σταμάτησε.
7  Εφάρμοσε τους τελεστές μετάβασης για να βρεις τις καταστάσεις-παιδιά.
8  Βάλε τις καταστάσεις-παιδιά στην αρχή του μετώπου της αναζήτησης.
9  Βάλε την κατάσταση-γονέα στο κλειστό σύνολο.
10 Πήγαινε στο βήμα 2.

Ιδιότητες

Ο χρόνος και ο χώρος που απαιτεί ο DFS διαφέρει ανάλογα με τον τομέα εφαρμογής του. Στην επιστήμη των υπολογιστών, χρησιμοποιείται συνήθως για να διασχίσει ένα ολόκληρο γράφημα και χρειάζεται χρόνο  που είναι γραμμική συνάρτηση του μεγέθους του γραφήματος. Σε αυτές τις εφαρμογές επίσης χρησιμοποιεί χώρο  στην χειρότερη περίπτωση, για να αποθηκεύσει τη στοίβα με τις κορυφές για το τρέχων μονοπάτι αναζήτησης όπως επίσης και το σύνολο των ήδη εξερευνημένων κορυφών. Συνεπώς, σε αυτή την περίπτωση, ο χρόνος και ο χώρος που απαιτούνται είναι ίδιος και με τον αλγόριθμο Αναζήτησης Κατά Πλάτος (BFS) και το κριτήριο για την επιλογή του κατάλληλου αλγορίθμου εξαρτάται λιγότερο στην πολυπλοκότητα τους και περισσότερο στην διαφορετική διάταξη των κορυφών που δημιουργούν οι δύο αλγόριθμοι.
Κατά την εφαρμογή του DFS σε προβλήματα αναζήτησης στον τομέα της Τεχνητής Νοημοσύνης, το γράφημα προς αναζήτηση είναι συχνά υπερβολικά μεγάλο ή άπειρο ώστε να διασχιστεί ολόκληρο, και ο DFS μπορεί να έχει πρόβλημα μη-τερματισμού όταν το μήκος της διαδρομής στο δέντρο αναζήτησης είναι άπειρο. Συνεπώς, η αναζήτηση γίνεται μόνο σε περιορισμένο βάθος, και λόγω της περιορισμένης διαθεσιμότητας μνήμης, συνήθως δεν χρησιμοποιούνται δομές δεδομένων που να αποθηκεύουν τους κόμβους που έχουν εξερευνηθεί ήδη. Σε αυτή την περίπτωση, ο χρόνος είναι επίσης γραμμική συνάρτηση των διασχισμένων ακμών και κορυφών (αν και αυτός ο αριθμός δεν είναι ίδιος με το μέγεθος ολόκληρου του γραφήματος διότι ορισμένες κορυφές μπορεί να εξερευνηθούν περισσότερες από μια φορές και άλλες καθόλου), αλλά η πολυπλοκότητα του χώρου αυτής της παραλλαγής του DFS, είναι μόνο ανάλογη προς το όριο βάθους,και συγχρόνως πολύ μικρότερη από τον χώρο που απαιτείται για αναζήτηση στο ίδιο βάθος χρησιμοποιώντας αναζήτηση κατά πλάτος (BFS). Για τέτοιες εφαρμογές, o DFS προσαρμόζεται καλύτερα σε ευριστικές μεθόδους που επιλέγουν ένα πιθανό κλαδί. Όταν ένα κατάλληλο όριο βάθους δεν είναι γνωστό από την αρχή, εφαρμόζεται επαναληπτική εμβάθυνση που υλοποιεί τον DFS επανειλημμένα με μια συνεχή αύξηση του ορίου. Στις εφαρμογές τεχνητής νοημοσύνης, με έναν παράγοντα διακλάδωσης μεγαλύτερο από ένα, η χρήση της επαναληπτικής εμβάθυνσης αυξάνει τον χρόνο του αλγορίθμου μόνο κατά ένα σταθερό συντελεστή παραπάνω από την περίπτωση που το σωστό όριο βάθους είναι γνωστό λόγω της γεωμετρικής αύξησης του αριθμού των κόμβων ανά επίπεδο.
Ο αλγόριθμος DFS μπορεί επίσης να χρησιμοποιηθεί για τη συλλογή ενός δείγματος των κόμβων του γραφήματος. Όμως, μια μη ολοκληρωμένη υλοποίηση του DFS, όπως και του BFS, έχει κλίση σε κόμβους υψηλού βαθμού.

Έξοδος του Αλγορίθμου DFS

Μια απλή περιγραφή της αναζήτησης κατά βάθος σε ένα γράφημα, είναι το συνεκτικό δέντρο (spanning tree) των κορυφών που δημιουργήθηκε κατά την αναζήτηση. Με βάση το συνεκτικό δέντρο, οι ακμές του αρχικού γραφήματος μπορούν να χωριστούν σε τρεις κλάσεις: forward edges, οι οποίες δείχνουν από έναν κόμβο του δέντρου σε έναν από τους απογόνους του, back edges,οι οποίες δείχνουν από έναν κόμβο σε έναν από τους προγόνους του, και cross edges, οι οποίες δεν δείχνουν σε κανένα από τα δυο. Μερικές φορές οι ακμές του συνεκτικού δέντρου (tree edges), κατηγοριοποιούνται ξεχωριστά από τις forward edges. Αν το αρχικό γράφημα είναι μη κατευθυνόμενο, τότε όλες οι ακμές του είναι tree edges ή back edges.

Παράδειγμα Εκτέλεσης

Για το παρακάτω γράφημα:
η αναζήτηση κατά βάθος ξεκινάει από τον κόμβο A, θεωρώντας ότι οι κόμβοι που είναι αριστερά στο γράφημα επιλέγονται πριν από αυτούς που βρίσκονται στα δεξιά, όπως επίσης ότι ο αλγόριθμος θυμάται τους κόμβους που έχει επισκεφτεί ήδη και δεν θα τους επαναλάβει (αφού πρόκειται για μικρό γράφημα), έτσι η διάσχιση του γραφήματος θα γίνει με την εξής σειρά: A, B, D, F, E, C, G.
Υλοποιώντας την ίδια αναζήτηση χωρίς να σημειώνονται οι κόμβοι που έχουν επισκεφτεί ήδη, η διάσχιση των κόμβων θα έχει την εξής σειρά: A, B, D, F, E, A, B, D, F, E, κτλ. συνέχεια, κάνοντας πάντα τον κύκλο A, B, D, F, E και χωρίς ποτέ να διασχίσει τους κόμβους C ή G.
Η Επαναληπτική Εμβάθυνση είναι μια τεχνική για την αποφυγή αυτού του ατέρμονος βρόχου και για να επιτύχει την διάσχιση όλων των κόμβων.

Ψευδοκώδικας

Είσοδος: Ένα γράφημα G και μια κορυφή v του G
Έξοδος: Ο χαρακτηρισμός των ακμών στο συνεκτικό στοιχείο της v είτε ως discovery edges (εξερευνημένοι κόμβοι) είτε ως back edges (ανεξερεύνητοι κόμβοι)

1  procedure DFS(G,v):
2      label v as explored
3      for all edges e in G.adjacentEdges(v) do
4          if edge e is unexplored then
5              w ← G.adjacentVertex(v,e)
6              if vertex w is unexplored then
7                  label e as a discovery edge
8                  recursively call DFS(G,w)
9              else
10                 label e as a back edge
Μη-αναδρομική υλοποίηση του DFS:

1  procedure DFS-iterative(G,v):
2      label v as discovered
3      let S be a stack
4      S.push(v)
5      while S is not empty        
6            t ← S.top 
7            if t is what we're looking for: 
8                return t
9            for all edges e in G.adjacentEdges(t) do
10               if edge e is already labelled 
11                   continue with the next edge
12               w ← G.adjacentVertex(t,e)
13               if vertex w is not discovered and not explored
14                   label e as tree-edge
15                   label w as discovered
16                   S.push(w)
17                   continue at 5
18               else if vertex w is discovered
19                   label e as back-edge
20               else
21                   // vertex w is explored
22                   label e as forward- or cross-edge
23           label t as explored
24           S.pop()
Σημειώση: Ένας κόμβος χαρακτηρίζεται ως discovered όταν έχει επισκεφτεί και explored όταν όλοι οι γείτονες του έχουν διασχιστεί.