Επίλυση προβλημάτων (τεχνητή νοημοσύνη): Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ πρότυπο: έλλειψη παραπομπών |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 34:
Οι σπουδαιότεροι αλγόριθμοι τυφλής αναζήτησης είναι ο DFS (''Depth-First Search'' ή ''[[αναζήτηση κατά βάθος]]'') και ο BFS (''Breadth-First Search'' ή ''[[αναζήτηση κατά πλάτος]]''), οι οποίοι κατασκευάζουν το δένδρο ξεκινώντας από τη ρίζα και παράγοντας κόμβους, ο μεν DFS κατά βάθος (ακολουθεί ένα κλαδί μέχρι να φτάσει σε φύλλο και μετά επεκτείνει έναν κόμβο προηγούμενου επιπέδου· αυτή η μέθοδος ονομάζεται «οπισθοδρόμηση»), ο δε BFS κατά πλάτος (επεκτείνει πρώτα όλους τους κόμβους ενός επιπέδου, οι οποίοι έχουν το ίδιο βάθος, και μετά προχωρά στους κόμβους του επόμενου επιπέδου). Προγραμματιστικά είναι σχεδόν ίδιοι μεταξύ τους, αλλά και με το γενικό αλγόριθμο που περιγράφηκε προηγουμένως, μόνο που διαφέρουν στο βήμα 8 (το βήμα 7 δεν υπάρχει αφού δε γίνεται κλάδεμα): ο DFS τοποθετεί τους νέους κόμβους που προστίθενται στο Μ.Α. στην αρχή της [[συνδεδεμένη λίστα|λίστας]] ([[LIFO]] [[στοίβα (υπολογιστές)|στοίβα]]), ώστε στην επόμενη επανάληψη του βρόχου να επεκταθεί ένας από αυτούς, ενώ ο BFS τους τοποθετεί στο τέλος της λίστας ([[FIFO]] [[ουρά (υπολογιστές)|ουρά]]), ώστε στην επόμενη επανάληψη του βρόχου να επεκταθεί ένας «αδελφός» του γονέα τους αν υπάρχει.
Ο BFS εγγυάται ότι θα βρει πρώτα τη λύση με την ελάχιστη απόσταση από τη ρίζα (οπότε είναι ιδανικός και για προβλήματα βελτιστοποίησης όπου όλοι οι τελεστές έχουν ίσο κόστος) και είναι [[Πλήρης Αλγόριθμος|πλήρης]], το Μ.Α. όμως μπορεί να γιγαντωθεί για μεγάλους χώρους αναζήτησης και άρα έχει μεγάλες απαιτήσεις σε [[Μνήμη υπολογιστή|μνήμη]]. Από την άλλη ο DFS είναι τυχαίο το ποια λύση θα βρει πρώτα και δεν είναι πλήρης, καθώς αν δε χρησιμοποιείται Κλειστό Σύνολο μπορεί να παγιδευτεί σε κλαδιά απείρου μήκους (αφού ακολουθεί ένα κλαδί μέχρι να καταλήξει σε φύλλο). Από την άλλη έχει μικρές απαιτήσεις σε μνήμη διατηρώντας πάντα μικρό το Μ.Α.
Συμβιβασμό μεταξύ αυτών των δύο αποτελεί ο αλγόριθμος ID (''Iterative Deepening'' ή ''επαναληπτική εκβάθυνση''), ο οποίος είναι κατά βάση DFS αλλά προχωρά μέχρι ένα προκαθορισμένο βάθος, ενώ στη συνέχεια το επιτρεπτό βάθος αυξάνεται και ο αλγόριθμος ξεκινά από την αρχή χωρίς να διατηρεί δεδομένα από την προηγούμενη αναζήτηση. Το δένδρο δηλαδή κατασκευάζεται διαρκώς από τη ρίζα, ξανά και ξανά, αλλά σε όλο και μεγαλύτερο βάθος. Παρ' όλο που ο ID εκτελεί πολλή περιττή εργασία αυτό δεν παίζει ρόλο σε μεγάλους χώρους αναζήτησης όσον αφορά την [[αλγοριθμική πολυπλοκότητα]]. Ο αλγόριθμος είναι πλήρης γιατί δεν μπορεί να παγιδευτεί σε άπειρα κλαδιά, αφού το βάθος αναζήτησης είναι προκαθορισμένο, έχει τις μικρές απαιτήσεις μνήμης του DFS, ενώ αν το επιτρεπτό βάθος σε κάθε επανάληψη αυξάνεται κατά 1 εγγυάται ότι θα βρει πρώτα τη λύση με την ελάχιστη απόσταση από τη ρίζα (όπως ο BFS, αφού αν υπήρχε καλύτερη λύση θα βρισκόταν σε προηγούμενη επανάληψη).
| |||