Επίλυση προβλημάτων (τεχνητή νοημοσύνη): Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Robot-assisted disambiguation: Μέσος όρος - Changed link(s) to Μέσος όρος αριθμών |
μ Robot-assisted disambiguation: Μεταβλητή - Changed link(s) to Μεταβλητή (Πληροφορική) |
||
Γραμμή 42:
Οποιοσδήποτε από αυτούς τους αλγορίθμους μπορεί να χρησιμοποιηθεί με τη μέθοδο BiS (''Bidirectional Search'' ή ''αμφίδρομη αναζήτηση''), η οποία μπορεί να εφαρμοστεί σε υπολογιστικό σύστημα με [[παράλληλη επεξεργασία|δύο επεξεργαστές]] όταν η τελική κατάσταση είναι πλήρως γνωστή και οι τελεστές μετάβασης είναι αντιστρέψιμοι: ο ένας επεξεργαστής εκτελεί αναζήτηση από την αρχική προς την τελική κατάσταση και ο άλλος από την τελική προς την αρχική. Όταν βρεθεί μία κοινή κατάσταση το πρόγραμμα ενώνει τα δύο μονοπάτια και επιστρέφει την τελική λύση· ιδανικά στο 1/2 του χρόνου που θα απαιτούσε μία μονόδρομη αναζήτηση.
Σε προβλήματα βελτιστοποίησης με τελεστές διαφορετικού (αλλά πάντα θετικού) κόστους μπορεί να εφαρμοστεί ο αλγόριθμος τυφλής αναζήτησης B&B (''Branch and Bound'' ή ''επέκταση και οριοθέτηση''), ο οποίος μπορεί να βασιστεί είτε στον DFS είτε στον BFS προσφέροντας όμως επιπλέον κλάδεμα των καταστάσεων -και των αντίστοιχων υποδένδρων που θα προέκυπταν από την επέκταση τους- που αποκλείεται να οδηγούν σε λύση καλύτερη από την τρέχουσα. Για να το πετύχει αυτό κρατά σε μία [[Μεταβλητή (Πληροφορική)|μεταβλητή]] Β το ολικό κόστος του μονοπατιού της βέλτιστης λύσης που έχει βρεθεί ως τώρα και, αν το μονοπάτι του τρέχοντος ενδιάμεσου κόμβου έχει κόστος μεγαλύτερο του Β, δεν τον αναπτύσσει και τον αφαιρεί από το Μέτωπο Αναζήτησης. Στη χειρότερη περίπτωση δε θα γίνει κανένα κλάδεμα, αφού είναι θέμα τύχης η σειρά με την οποία θα ανακαλυφθούν οι λύσεις, και ο B&B λειτουργεί όπως ο DFS ή ο BFS.
=== Ευρετική αναζήτηση ===
| |||