.
Ο αλγόριθμος Αναζήτησης Κατά Βάθος (DFS - Depth-first search) επιτυγχάνει διάσχιση ή αναζήτηση σε δέντρο ή γράφημα. Η διάσχιση ξεκινά από τη ρίζα και εξερευνά όσο το δυνατόν περισσότερο κατά μήκος κάθε κλαδί του δέντρου μέχρι να φτάσει σε αδιέξοδο.
Μια έκδοση της αναζήτησης κατά βάθος ερευνήθηκε κατά τον 19ο αιώνα από τον Γάλλο μαθηματικό Charles Pierre Trémaux [1] ως μια στρατηγική για την επίλυση λαβυρίνθων.[2][3] Ένας λαβύρινθος μπορεί να αναπαρασταθεί ως γράφος θεωρώντας κάθε διασταύρωση του λαβύρινθου ως κόμβος και κάθε εσωτερική διαδρομή ως ακμή [4].
Ορισμός
Ο αλγόριθμος DFS πραγματοποιεί αναζήτηση ωμής βίας (brute-force) που ξεκινά με την επέκταση του πρώτου κόμβου-παιδί του δέντρου αναζήτησης που εμφανίζεται και συνεχίζει σε βάθος του δέντρου μέχρι να βρεθεί ο ζητούμενος κόμβος ή μέχρι να φτάσει σε κόμβο που δεν έχει παιδιά. Στη συνέχεια, η αναζήτηση συνεχίζεται στον πιο πρόσφατο ανεξερεύνητο κόμβο. Σε μια μη-αναδρομική υλοποίηση, όλοι οι νέοι ανεξερεύνητοι κόμβοι τοποθετούνται στην κορυφή μιας στοίβας και η αναζήτηση συνεχίζεται με έναν από αυτούς.
Περιγραφή
Η περιγραφή του αλγορίθμου DFS είναι η ακόλουθη:
1 Βάλε την αρχική κατάσταση στο μέτωπο της αναζήτησης. 2 Αν το μέτωπο αναζήτησης είναι κενό τότε σταμάτησε. 3 Βγάλε την πρώτη κατάσταση από το μέτωπο της αναζήτησης. 4 Αν είναι η κατάσταση μέλος του κλειστού συνόλου τότε πήγαινε στο βήμα 2. 5 Αν η κατάσταση είναι μια από τις τελικές, τότε ανέφερε τη λύση. 6 Αν θέλεις κι άλλες λύσεις πήγαινε στο βήμα 2. Αλλιώς σταμάτησε. 7 Εφάρμοσε τους τελεστές μετάβασης για να βρεις τις καταστάσεις-παιδιά. 8 Βάλε τις καταστάσεις-παιδιά στην αρχή του μετώπου της αναζήτησης. 9 Βάλε την κατάσταση-γονέα στο κλειστό σύνολο. 10 Πήγαινε στο βήμα 2.
Ιδιότητες
Ο χρόνος και ο χώρος που απαιτεί ο DFS διαφέρει ανάλογα με τον τομέα εφαρμογής του. Στην επιστήμη των υπολογιστών, χρησιμοποιείται συνήθως για να διασχίσει ένα ολόκληρο γράφημα και χρειάζεται χρόνο O ( | E | ) {\displaystyle O(|E|)} που είναι γραμμική συνάρτηση του μεγέθους του γραφήματος. Σε αυτές τις εφαρμογές επίσης χρησιμοποιεί χώρο O ( | V | ) {\displaystyle 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. Για παράδειγμα, κατά την αναζήτηση του κατευθυνόμενου γραφήματος
If-then-else-control-flow-graph.svg
ξεκινώντας από τον κόμβο Α, επισκέπτεται τους κόμβους με τη σειρά και δημιουργεί τη λίστα 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 όταν όλοι οι γείτονες του έχουν διασχιστεί.
Εφαρμογές
1:01
Παρόμοιος Αλγόριθμος του DFS που χρησιμοποιείται για τη δημιουργία λαβυρίνθου.
Αλγόριθμοι που έχουν ως δομικό τους στοιχείο την αναζήτηση κατά βάθος περιλαμβάνουν:
Εύρεση συνεκτικών συνιστώσων.
Τοπολογική ταξινόμηση.
Εύρεση 2-(ακμών ή κόμβων)-συνεκτικών συνιστώσων.
Finding 3-(ακμών ή κόμβων)-συνεκτικών συνιστώσων.
Εύρεση γεφύρων ενός γραφήματος.
Εύρεση ισχυρών συνεκτικών συνιστώσων.
Επίλυση παζλ με μόνο μία λύση, για παράδειγμα λαβύρινθος.
Η δημιουργία λαβύρινθου μπορεί να υλοποιηθεί με αναζήτηση κατά βάθος.
Σημειώσεις
Charles Pierre Trémaux (1859–1882) École Polytechnique of Paris (X:1876), French engineer of the telegraph
in Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ISSN: 0980-6032)
Even, Shimon (2011), Graph Algorithms (2nd έκδοση), Cambridge University Press, σελ. 46–48, ISBN 978-0-521-73653-4.
Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd έκδοση), Pearson Education, ISBN 978-0-201-36118-6.
Robert Sedgewick, Kevin Wayne (2011). Algorithms. Addison-Wesley. σελίδες 530. ISBN 978-0-321-57351-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
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.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License