Αναζήτηση κατά βάθος

Διάταξη με την οποία επισκέπτονται οι κόμβοι

Ο αλγόριθμος Αναζήτησης Κατά Βάθος (DFS - Depth-first search) επιτυγχάνει διάσχιση ή αναζήτηση σε δέντρο ή γράφημα. Η διάσχιση ξεκινά από τη ρίζα και εξερευνά όσο το δυνατόν περισσότερο κατά μήκος κάθε κλαδί του δέντρου μέχρι να φτάσει σε αδιέξοδο.

Μια έκδοση της αναζήτησης κατά βάθος ερευνήθηκε κατά τον 19ο αιώνα από τον Γάλλο μαθηματικό Charles Pierre Trémaux ως μια στρατηγική για την επίλυση λαβυρίνθων. Ένας λαβύρινθος μπορεί να αναπαρασταθεί ως γράφος θεωρώντας κάθε διασταύρωση του λαβύρινθου ως κόμβος και κάθε εσωτερική διαδρομή ως ακμή .

Περιγραφή

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

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

Ιδιότητες

Ο χρόνος και ο χώρος που απαιτεί ο DFS διαφέρει ανάλογα με τον τομέα εφαρμογής του. Στην επιστήμη των υπολογιστών, χρησιμοποιείται συνήθως για να διασχίσει ένα ολόκληρο γράφημα και χρειάζεται χρόνο $O(|E|)$ που είναι γραμμική συνάρτηση του μεγέθους του γραφήματος. Σε αυτές τις εφαρμογές επίσης χρησιμοποιεί χώρο $O(|V|)$ στην χειρότερη περίπτωση, για να αποθηκεύσει τη στοίβα με τις κορυφές για το τρέχων μονοπάτι αναζήτησης όπως επίσης και το σύνολο των ήδη εξερευνημένων κορυφών. Συνεπώς, σε αυτή την περίπτωση, ο χρόνος και ο χώρος που απαιτούνται είναι ίδιος και με τον αλγόριθμο Αναζήτησης Κατά Πλάτος (BFS) και το κριτήριο για την επιλογή του κατάλληλου αλγορίθμου εξαρτάται λιγότερο στην πολυπλοκότητα τους και περισσότερο στην διαφορετική διάταξη των κορυφών που δημιουργούν οι δύο αλγόριθμοι.

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

Ο αλγόριθμος DFS μπορεί επίσης να χρησιμοποιηθεί για τη συλλογή ενός δείγματος των κόμβων του γραφήματος. Όμως, μια μη ολοκληρωμένη υλοποίηση του DFS, όπως και του BFS, έχει κλίση σε κόμβους υψηλού βαθμού.

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

Οι τέσσερις τύποι ακμών που ορίζονται από ένα spanning tree

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

Διατάξεις Κορυφών

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

• preordering: Οι κορυφές διατάσσονται σε μια λίστα με τη σειρά που τις επισκέφτηκε αρχικά ο αλγόριθμος DFS. Αυτός είναι ένας απλός τρόπος να περιγραφεί η διαδικασία της αναζήτησης, όπως περιγράφηκε και παραπάνω. Ένα δέντρο έκφρασης διατεταγμένο με preordering είναι η έκφραση σε Πολωνική γραφή (Polish notation).

• postordering: Οι κορυφές διατάσσονται σε μια λίστα με τη σειρά που έγινε η τελευταία επίσκεψη από τον αλγόριθμο DFS. Ένα δέντρο έκφρασης διατεταγμένο με postordering είναι η έκφραση σε ανάστροφη Πολωνική γραφή (reverse Polish notation).

• reverse postordering: Είναι η αντίστροφή διαδικασία του postordering, δηλαδή μια λίστα με τις κορυφές με την αντίστροφη σειρά από την τελευταία επίσκεψη τους. Το reverse postordering δεν είναι το ίδιο με το preordering. Για παράδειγμα, κατά την αναζήτηση του κατευθυνόμενου γραφήματος

ξεκινώντας από τον κόμβο Α, επισκέπτεται τους κόμβους με τη σειρά και δημιουργεί τη λίστα A B D B A C A ή την A C D C A B A (ανάλογα με το εάν ο αλγόριθμος επιλέγει να επισκεφθεί Β ή Γ πρώτα). Σε αυτή τη διαδικασία, περιλαμβάνονται οι επαναλαμβανόμενες επισκέψεις σε έναν κόμβο για να ελεγχθεί αν έχει ανεξερεύνητους γειτονικούς κόμβους (ακόμα και αν διαπιστωθεί ότι δεν έχει κανέναν). Έτσι, οι πιθανές preordering διατάξεις είναι η ABDC και η ACDB. Η reverse postordering παράγει μια τοπολογική διάταξη σε οποιονδήποτε ακυκλικό γράφο. Αυτή η διάταξη είναι επίσης χρήσιμη στην ανάλυση ελέγχου ροής, καθώς συχνά αντιπροσωπεύει μια γραμμικοποιήση του ελέγχου ροής. Το παραπάνω γράφημα μπορεί να αντιπροσωπεύει τον έλεγχο ροής σε ένα κομμάτι κώδικα, όπως

if (A) then {

       B
     } else {
       C
     }
     D

και είναι λογικό να εκτελεστεί με τη σειρά A B C D ή A C B D, και όχι με τη σειρά A B D C ή A C D B.

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

Για το παρακάτω γράφημα:

η αναζήτηση κατά βάθος ξεκινάει από τον κόμβο 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 όταν όλοι οι γείτονες του έχουν διασχιστεί.

Εφαρμογές

Παρόμοιος Αλγόριθμος του DFS που χρησιμοποιείται για τη δημιουργία λαβυρίνθου.

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

• Εύρεση συνεκτικών συνιστώσων.
• Τοπολογική ταξινόμηση.
• Εύρεση 2-(ακμών ή κόμβων)-συνεκτικών συνιστώσων.
• Finding 3-(ακμών ή κόμβων)-συνεκτικών συνιστώσων.
• Εύρεση γεφύρων ενός γραφήματος.
• Εύρεση ισχυρών συνεκτικών συνιστώσων.
• Επίλυση παζλ με μόνο μία λύση, για παράδειγμα λαβύρινθος.
• Η δημιουργία λαβύρινθου μπορεί να υλοποιηθεί με αναζήτηση κατά βάθος.

Πηγές

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.3: Depth-first search, pp. 540–549.
• Knuth, Donald E. (1997), The Art Of Computer Programming Vol 1. 3rd ed, Boston: Addison-Wesley, ISBN 0-201-89683-4, OCLC 155842391, http://www-cs-faculty.stanford.edu/~knuth/taocp.html, ανακτήθηκε στις 2013-06-08 
• Goodrich, Michael T. (2001), Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley, ISBN 0-471-38365-1 
• Βλαχάβας Ιωάννης, Κεφάλας Πέτρος, Βασιλειάδης Νικόλαος, Κόκκορας Φώτης, Σακελλαρίου Ηλίας. Τεχνητή Νοημοσύνη, Γ' Έκδοση. Εκδόσεις Πανεπιστημίου Μακεδονίας, 2006. ISBN 978-960-8396-64-7. Μέρος Α, Κεφάλαιο 3.1: Αναζήτηση Πρώτα σε Βάθος, σελ. 39–40.