Ωστόσο, μεταξύ των ενημερωμένων και των μη ενημερωμένων τεχνικών αναζήτησης, η ενημερωμένη αναζήτηση είναι πιο αποτελεσματική και οικονομικά αποδοτική.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Ενημερωμένη αναζήτηση | Άγνωστη αναζήτηση |
|---|---|---|
| Βασικός | Χρησιμοποιεί τη γνώση για να βρει τα βήματα προς τη λύση. | Καμία χρήση της γνώσης |
| Αποδοτικότητα | Εξαιρετικά αποτελεσματική καθώς καταναλώνει λιγότερο χρόνο και κόστος. | Η αποτελεσματικότητα είναι μεσολαβητική |
| Κόστος | Χαμηλός | Συγκριτικά υψηλό |
| Εκτέλεση | Βρίσκει λύση πιο γρήγορα | Η ταχύτητα είναι πιο αργή από την ενημερωμένη αναζήτηση |
| Αλγόριθμοι | Αναζήτηση βάθους κατά βάθος, αναζήτηση πρώτης διάστασης και αναζήτηση πρώτης ανάγκης με το χαμηλότερο κόστος | Εευρησιακό βάθος πρώτης και ευρείας αναζήτησης, και αναζήτηση Α * |
Ορισμός ενημερωμένης αναζήτησης
Η τεκμηριωμένη τεχνική αναζήτησης χρησιμοποιεί τη συγκεκριμένη γνώση του προβλήματος προκειμένου να δώσει μια ένδειξη για τη λύση του προβλήματος. Αυτός ο τύπος στρατηγικής αναζήτησης εμποδίζει τους αλγόριθμους να παρεμποδίσουν το στόχο και την κατεύθυνση προς τη λύση. Η ενημερωμένη αναζήτηση μπορεί να είναι συμφέρουσα από την άποψη του κόστους όπου επιτυγχάνεται η βέλτιστη λύση με χαμηλότερο κόστος αναζήτησης.
Για να αναζητήσουμε ένα βέλτιστο κόστος διαδρομής σε ένα γράφημα με την εφαρμογή στρατηγικής ενημερωμένης αναζήτησης, οι πιο ελπιδοφόροι κόμβοι n εισάγονται στην ευρετική συνάρτηση h (n). Στη συνέχεια, η συνάρτηση επιστρέφει έναν μη αρνητικό πραγματικό αριθμό που είναι ένα κόστος διαδρομής κατά προσέγγιση που υπολογίζεται από τον κόμβο n στον κόμβο στόχου.
Εδώ το πιο σημαντικό μέρος της ενημερωμένης τεχνικής είναι η ευρετική συνάρτηση που διευκολύνει να μεταδώσει την πρόσθετη γνώση του προβλήματος στον αλγόριθμο. Ως αποτέλεσμα, βοηθά στην εύρεση του δρόμου προς το στόχο μέσω των διαφόρων γειτονικών κόμβων. Υπάρχουν διάφοροι αλγόριθμοι που βασίζονται στην ενημερωμένη αναζήτηση, όπως η ευρετική αναζήτηση βάθους-πρώτης αναζήτησης, η ευρετική εύρος-πρώτη αναζήτηση, η αναζήτηση Α * κ.λπ. Ας καταλάβουμε τώρα την ευρετική αναζήτηση βάθους.
Εευρησιακό Βάθος Πρώτη αναζήτηση
Παρόμοια με τη μέθοδο αναζήτησης βάθους πρώτου βάθους που δίνεται παρακάτω, η ευρετική αναζήτηση βάθους αρχικής αναζήτησης επιλέγει μια διαδρομή αλλά διασχίζει όλες τις διαδρομές από την επιλεγμένη διαδρομή πριν επιλέξει άλλη διαδρομή. Ωστόσο, επιλέγει την καλύτερη διαδρομή τοπικά. Σε περιπτώσεις όπου η μικρότερη ευρετική τιμή είναι η προτεραιότητα για τα σύνορα, τότε είναι γνωστή ως καλύτερη πρώτη αναζήτηση.
Ένας άλλος ενημερωμένος αλγόριθμος αναζήτησης είναι η αναζήτηση A *, η οποία συνδυάζει την έννοια του χαμηλότερου κόστους πρώτα και τις καλύτερες πρώτες αναζητήσεις. Αυτή η μέθοδος λαμβάνει υπόψη τόσο το κόστος της διαδρομής όσο και τις ευρετικές πληροφορίες κατά τη διαδικασία αναζήτησης και επιλογής της διαδρομής προς επέκταση. Υπολογισμένο συνολικό κόστος διαδρομής που χρησιμοποιείται για κάθε διαδρομή που διαμένει στα σύνορα από την αρχή μέχρι τον κόμβο-στόχο. Επομένως, χρησιμοποιεί δύο λειτουργίες ταυτόχρονα - το κόστος (p) είναι το κόστος της ανακαλυφθείσας διαδρομής και το h (p) είναι η εκτιμώμενη τιμή του κόστους διαδρομής από τον κόμβο εκκίνησης ως τον κόμβο του στόχου.
Ορισμός της μη ενημερωμένης αναζήτησης
Η μη ενημερωμένη αναζήτηση διαφέρει από την ενημερωμένη αναζήτηση με τον τρόπο που παρέχει μόνο τον ορισμό του προβλήματος, αλλά δεν κάνει περαιτέρω βήματα για την εξεύρεση λύσης στο πρόβλημα. Ο πρωταρχικός στόχος της απροειδοποίητης αναζήτησης είναι η διαφοροποίηση μεταξύ της στοχευόμενης και της μη στοχευόμενης κατάστασης και αγνοεί εντελώς τον προορισμό που κατευθύνεται προς την κατεύθυνση μέχρι να ανακαλύψει τον στόχο και να αναφέρει τον διάδοχο. Αυτή η στρατηγική είναι επίσης γνωστή ως τυφλή αναζήτηση.
Υπάρχουν διάφοροι αλγόριθμοι αναζήτησης κάτω από αυτήν την κατηγορία, όπως αναζήτηση βάθους-πρώτης αναζήτησης, ομοιόμορφη αναζήτηση κόστους, ευρεία αναζήτηση πρώτης ύλης και ούτω καθεξής. Ας καταλάβουμε τώρα την έννοια πίσω από την άτυπη αναζήτηση με τη βοήθεια αναζήτησης βάθους.
Βάθος πρώτη αναζήτηση
Σε πρώτη αναζήτηση σε βάθος, χρησιμοποιείται μια στοίβα Last in first out για την προσθήκη και την αφαίρεση των κόμβων. Μόλις ένας κόμβος προστίθεται ή αφαιρείται κάθε φορά και το πρώτο στοιχείο που αφαιρείται από τα σύνορα της στοίβας θα είναι το τελευταίο στοιχείο που προστέθηκε στη στοίβα. Χρησιμοποιώντας τη στοίβα στα σύνορα, η αναζήτηση των διαδρομών προχώρησε σε βάθος με τον πρώτο τρόπο. Όταν αναζητείται μια συντομότερη και βέλτιστη διαδρομή χρησιμοποιώντας αναζήτηση με βάση το βάθος, η διαδρομή που δημιουργείται από τους γειτονικούς κόμβους ολοκληρώνεται πρώτα, ακόμη και αν δεν είναι η επιθυμητή. Στη συνέχεια, αναζητείται η εναλλακτική διαδρομή μέσω της εκτροπής.
Με άλλα λόγια, ο αλγόριθμος επιλέγει την πρώτη εναλλακτική λύση σε κάθε κόμβο και έπειτα επιστρέφει σε μια άλλη εναλλακτική λύση μέχρι να διασχίσει όλες τις διαδρομές από την πρώτη επιλογή. Αυτό δημιουργεί επίσης ένα πρόβλημα όπου η αναζήτηση μπορεί να σταματήσει να σταματά λόγω των άπειρων βρόχων (κύκλων) που υπάρχουν στο γράφημα.
Βασικές διαφορές μεταξύ ενημερωμένης και μη ενημερωμένης αναζήτησης
- Η πρώην ενημερωμένη τεχνική αναζήτησης χρησιμοποιεί γνώσεις για να βρει τη λύση. Από την άλλη πλευρά, η τελευταία μη ενημερωμένη τεχνική αναζήτησης δεν χρησιμοποιεί τη γνώση. Με απλούστερους όρους δεν παρέχονται περαιτέρω πληροφορίες σχετικά με τη λύση.
- Η αποτελεσματικότητα της ενημερωμένης αναζήτησης είναι καλύτερη από την άτυπη αναζήτηση.
- Η μη ενημερωμένη αναζήτηση καταναλώνει περισσότερο χρόνο και κόστος, καθώς δεν έχει ιδέα για τη λύση σε σύγκριση με την ενημερωμένη αναζήτηση.
- Η αναζήτηση βάθους κατά βάθος, η αναζήτηση πρώτης διάστασης και η πρώτη αναζήτηση με το χαμηλότερο κόστος είναι οι αλγόριθμοι που εμπίπτουν στην κατηγορία της άτυπης αναζήτησης. Αντιθέτως, η ενημερωμένη αναζήτηση καλύπτει τους αλγορίθμους, όπως το ευρετικό βάθος-πρώτο, το ευρετικό πλάτος-πρώτη αναζήτηση και η αναζήτηση Α *.
συμπέρασμα
Η ενημερωμένη αναζήτηση παρέχει την κατεύθυνση όσον αφορά τη λύση, ενώ σε απροειδοποίητη αναζήτηση δεν δίνεται καμία πρόταση σχετικά με τη λύση. Αυτό καθιστά τη μη ενημερωμένη αναζήτηση πιο μακρά όταν υλοποιείται ο αλγόριθμος.
