Επίλυση προβλημάτων (τεχνητή νοημοσύνη)

Η επίλυση προβλημάτων είναι κλάδος της τεχνητής νοημοσύνης (ΤΝ) ο οποίος αφορά τον σχεδιασμό κατάλληλων ενεργειών με στόχο την άφιξη ενός ελέγξιμου συστήματος σε μία αποδεκτή τελική κατάσταση, εκκινώντας από κάποια προκαθορισμένη αρχική κατάσταση. Συνήθως αυτό γίνεται μέσω ενός αλγορίθμου ο οποίος λαμβάνει ως είσοδο το δοθέν πρόβλημα και επιστρέφει ως έξοδο μία λύση σε αυτό, αφού αξιολογήσει πρώτα μία ομάδα υποψηφίων λύσεων. Πρόκειται για ένα θεμελιώδες γνωστικό πεδίο της τεχνητής νοημοσύνης το οποίο γνώρισε μεγάλη ανάπτυξη ήδη από τη δεκαετία του 1950. Αποτέλεσε μία προσπάθεια αλγοριθμικής εξομοίωσης της διαδικασίας της σκέψης, ενώ με τον καιρό ενσωμάτωσε μεθοδολογίες από τη θεωρία βελτιστοποίησης και τη θεωρία γράφων.

Προβλήματα

Ένα πρόβλημα είναι ένα σύνολο αντικειμένων, ιδιοτήτων και σχέσεων το οποίο ορίζεται από μία αρχική κατάσταση, μία επιθυμητή τελική κατάσταση και τις επιτρεπτές ενέργειες στα αντικείμενα του προβλήματος. Στόχος είναι, ξεκινώντας από την αρχική κατάσταση, να γίνει μία κατάλληλη ακολουθία ενεργειών η οποία να καταλήγει στην τελική κατάσταση. Αυτή η διαδικασία ονομάζεται επίλυση του προβλήματος (π.χ. η διεξαγωγή μίας παρτίδας σκάκι) και αποτέλεσε στόχο της ΤΝ από τη δεκαετία του '50. Η επίλυση προβλημάτων έχει προφανώς σπουδαίες εφαρμογές στην απόδειξη θεωρημάτων, στο χρονοπρογραμματισμό ενεργειών, στη διεξαγωγή παιγνίων κλπ, ενώ θεωρείται κεντρικό χαρακτηριστικό της ευφυΐας. Βασικό στοιχείο στην επίλυση προβλημάτων είναι η αναπαράσταση τους και γι' αυτό το σκοπό υπάρχουν δύο μεθοδολογίες: η αναπαράσταση με χώρο καταστάσεων και η αναπαράσταση με αναγωγή. Στη μέθοδο της αναγωγής δομική μονάδα περιγραφής του προβλήματος είναι η ίδια η περιγραφή αναλυόμενη σε πολλαπλές, απλούστερες εκδοχές. Αυτή η ανάλυση συμβαίνει διαδοχικά ώσπου να καταλήξει σε αρχέγονα προβλήματα επιλυόμενα με προφανή τρόπο. Προγραμματιστικά η αναγωγή υλοποιείται με αναδρομή και κεντρική έννοια σε αυτήν αποτελούν οι τελεστές αναγωγής, διαδικασίες οι οποίες ανάγουν ένα πρόβλημα σε υποπροβλήματα.

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

Ο πιο κατάλληλος τρόπος γραφικής αναπαράστασης του προβλήματος είναι ένας δενδρικός γράφος με ρίζα την αρχική κατάσταση, φύλλα τις τελικές καταστάσεις και τα αδιέξοδα, κόμβους τις ενδιάμεσες καταστάσεις και κλαδιά τους τελεστές μετάβασης. Επέκταση ενός κόμβου ονομάζεται η εύρεση όλων των παιδιών του στο δένδρο μέσω της εφαρμογής σε αυτόν όλων των πιθανών τελεστών. Οι λύσεις του προβλήματος είναι μονοπάτια από τη ρίζα σε κάποιο φύλλο του δένδρου που αντιστοιχεί σε τελική κατάσταση. Σε πραγματικά προβλήματα το μέγεθος αυτού του δένδρου γίνεται εξαιρετικά μεγάλο μετά την επέκταση λίγων μόλις κόμβων και επομένως η αναζήτηση λύσεων σε ένα τέτοιο δένδρο καθίσταται εξαιρετικά χρονοβόρα. Αυτό το ζήτημα στη βιβλιογραφία της ΤΝ αναφέρεται ως συνδυαστική έκρηξη.

Αλγόριθμοι αναζήτησης

Υπάρχει μία πλειάδα πραγματικών ή συνθετικών, απλών ή πολύπλοκων προβλημάτων που μπορούν να αναπαρασταθούν με χώρο καταστάσεων. Όλα τα προηγούμενα βρίσκουν εφαρμογή και το μόνο που αλλάζει σε κάθε πρόβλημα είναι οι λεπτομέρειες (οι ιδιότητες των αντικειμένων, οι επιτρεπτοί τελεστές κλπ). Προκειμένου ένα πρόγραμμα να επιλύσει ένα τέτοιο πρόβλημα πρέπει να αναπαραστήσει κατάλληλα και να κατασκευάσει το δένδρο των καταστάσεων, ξεκινώντας από τη ρίζα και επεκτείνοντας τους κόμβους μέχρι να φτάσει σε κάποια τελική κατάσταση. Αν το ζητούμενο είναι να βρεθεί μία οποιαδήποτε λύση τότε το πρόγραμμα μπορεί τότε να τερματίσει επιστρέφοντας το μονοπάτι που οδηγεί στο τρέχον φύλλο, διαφορετικά (εξαντλητική αναζήτηση) μπορεί να αποθηκεύσει έναν δείκτη προς αυτό το φύλλο και να συνεχίσει την κατασκευή του δένδρου μέχρι να ανακαλύψει όλες τις πιθανές καταστάσεις που είναι προσβάσιμες από την αρχική, με τους διαθέσιμους τελεστές μετάβασης, και όλες τις πιθανές λύσεις.

Υπάρχει ένας γενικός αλγόριθμος αναζήτησης που εκτελεί αυτήν τη διερεύνηση και οι πραγματικοί αλγόριθμοι που χρησιμοποιούνται είναι παραλλαγές του που διαφέρουν στα βήματα 7 και 8. Στον αλγόριθμο αυτό Μέτωπο Αναζήτησης (Μ.Α.) είναι το σύνολο των καταστάσεων που έχουμε επισκεφθεί αλλά δεν έχουμε επεκτείνει και Κλειστό Σύνολο (Κ.Σ.) το σύνολο των καταστάσεων που και έχουμε επισκεφθεί και έχουμε επεκτείνει. Το Κ.Σ. είναι απαραίτητο μόνο αν υπάρχει κίνδυνος παγίδευσης του αλγορίθμου σε ατέρμονα βρόχο λόγω απείρου μήκους κλαδιών στο δένδρο.

  1:   Μ.Α = NULL; Κ.Σ. = NULL;
  2:	Εισαγωγή της ρίζας στο Μ.Α.
  3:	Όσο (Κ=Κεφαλή(Μ.Α.)) != NULL
  4:	{	Αν Κ περιέχεται στο Κ.Σ. τότε goto 3
  5:		Αν Κ είναι τελική κατάσταση τότε {return Κ(μη εξαντλητική αναζήτηση) ή                     
                  insertToSolutions(Κ)(εξαντλητική αναζήτηση);goto 3}
  6:		Επέκταση του Κ, Εισαγωγή των παιδιών του στο Μ.Α., Εισαγωγή του Κ στο Κ.Σ.
  7:		Αφαίρεση κάποιων καταστάσεων από το Μ.Α. με κάποιο κριτήριο («κλάδεμα» του δένδρου,
                  γίνεται για εξοικονόμηση χρόνου όταν θεωρείται απίθανο το υποδένδρο που ξεκινά από
                  κάποια κατάσταση να οδηγεί σε λύση)
  8:		Αναδιοργάνωση του Μ.Α. με κάποιο κριτήριο
  9:  	}

Οι διάφορες πραγματικές παραλλαγές αυτού του αλγορίθμου διακρίνονται σε αλγορίθμους τυφλής αναζήτησης, που διατάσσουν το Μ.Α. αποκλειστικά με βάση το χρόνο δημιουργίας κάθε κόμβου κατά την κατασκευή του δένδρου, και σε αλγορίθμους ευρετικής αναζήτησης (heuristic search), όπου τα βήματα 7 και 8 εξαρτώνται από μία επιπλέον πληροφορία που υπολογίζεται σε πραγματικό χρόνο και που στις περισσότερες περιπτώσεις, αλλά όχι πάντα, είναι σχετικά ακριβής και αξιολογεί προσεγγιστικά τις καταστάσεις σε «καλές» και «κακές». Ένα παράδειγμα ευρετικής πληροφορίας που μπορεί να αντιστοιχιστεί σε κάθε ενδιάμεση κατάσταση είναι η εκτιμώμενη «απόστασή» της (με βάση ένα μέτρο που εξαρτάται από το πρόβλημα και την υλοποίηση) από την τελική. Έτσι μπορούμε, φερ' ειπείν, να κλαδεύουμε τα υποδένδρα με ρίζα «κακή» κατάσταση, αφαιρώντας τη ρίζα τους από το Μ.Α. προτού την επεκτείνουμε (βήμα 7). Προφανώς αυτή η τακτική συμβάλλει στην αντιμετώπιση του φαινομένου της συνδυαστικής έκρηξης.

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

Τυφλή αναζήτηση

Οι σπουδαιότεροι αλγόριθμοι τυφλής αναζήτησης είναι ο 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, αφού αν υπήρχε καλύτερη λύση θα βρισκόταν σε προηγούμενη επανάληψη).

Οποιοσδήποτε από αυτούς τους αλγορίθμους μπορεί να χρησιμοποιηθεί με τη μέθοδο BiS (Bidirectional Search ή αμφίδρομη αναζήτηση), η οποία μπορεί να εφαρμοστεί σε υπολογιστικό σύστημα με δύο επεξεργαστές όταν η τελική κατάσταση είναι πλήρως γνωστή και οι τελεστές μετάβασης είναι αντιστρέψιμοι: ο ένας επεξεργαστής εκτελεί αναζήτηση από την αρχική προς την τελική κατάσταση και ο άλλος από την τελική προς την αρχική. Όταν βρεθεί μία κοινή κατάσταση το πρόγραμμα ενώνει τα δύο μονοπάτια και επιστρέφει την τελική λύση· ιδανικά στο 1/2 του χρόνου που θα απαιτούσε μία μονόδρομη αναζήτηση.

Σε προβλήματα βελτιστοποίησης με τελεστές διαφορετικού (αλλά πάντα θετικού) κόστους μπορεί να εφαρμοστεί ο αλγόριθμος τυφλής αναζήτησης B&B (Branch and Bound ή επέκταση και οριοθέτηση), ο οποίος μπορεί να βασιστεί είτε στον DFS είτε στον BFS προσφέροντας όμως επιπλέον κλάδεμα των καταστάσεων -και των αντίστοιχων υποδένδρων που θα προέκυπταν από την επέκταση τους- που αποκλείεται να οδηγούν σε λύση καλύτερη από την τρέχουσα. Για να το πετύχει αυτό κρατά σε μία μεταβλητή Β το ολικό κόστος του μονοπατιού της βέλτιστης λύσης που έχει βρεθεί ως τώρα και, αν το μονοπάτι του τρέχοντος ενδιάμεσου κόμβου έχει κόστος μεγαλύτερο του Β, δεν τον αναπτύσσει και τον αφαιρεί από το Μέτωπο Αναζήτησης. Στη χειρότερη περίπτωση δε θα γίνει κανένα κλάδεμα, αφού είναι θέμα τύχης η σειρά με την οποία θα ανακαλυφθούν οι λύσεις, και ο B&B λειτουργεί όπως ο DFS ή ο BFS.

Ευρετική αναζήτηση

Προκειμένου να μειωθεί ο, γιγάντιος για ρεαλιστικά προβλήματα, χώρος αναζήτησης και ο απαιτούμενος για την εύρεση της λύσης χρόνος, μπορούν να χρησιμοποιηθούν αλγόριθμοι που εκμεταλλεύονται ευρετικούς μηχανισμούς, δηλαδή στρατηγικές (συνήθως συναρτήσεις που εξαρτώνται από το εκάστοτε πρόβλημα) οι οποίες αξιολογούν προσεγγιστικά τις ενδιάμεσες καταστάσεις ως προς την εκτιμώμενη απόσταση τους από μία τελική κατάσταση, επεκτείνουν πρώτα αυτές με τη βέλτιστη ευρετική τιμή (οι οποίες αναμένεται να οδηγήσουν συντομότερα σε λύση) ή/και κλαδεύουν τις υπόλοιπες. Οι ευρετικοί μηχανισμοί δεν είναι αντικειμενικοί και, παρόλο που κωδικοποιούνται αλγοριθμικά υπό τη μορφή της ευρετικής συνάρτησης, δεν μπορούν να θεωρηθούν αλγόριθμοι. Αυτό γιατί, προκειμένου να μειώσουν το χώρο αναζήτησης ή να επιταχύνουν την εύρεση της λύσης, λειτουργούν προσεγγιστικά και «διαισθητικά» (περίπου όπως οι άνθρωποι), ενώ οι αλγόριθμοι είναι ακριβείς και λειτουργούν πάντα ορθά. Στην πλειονότητα των περιπτώσεων πάντως οι ευρετικές στρατηγικές οδηγούν σε πολύ καλά αποτελέσματα (αναλόγως βέβαια του προβλήματος), ωστόσο απέχουν πολύ από το να προσομοιώνουν τους μηχανισμούς της ανθρώπινης σκέψης: η τελευταία χρησιμοποιεί επίσης ευρετικές μεθόδους οι οποίες όμως είναι ποιοτικές, όχι ποσοτικές / αριθμητικές όπως η ευρετική συνάρτηση, και φαίνεται να αποδίδουν καλύτερα.

Ένας βασικός ευρετικός αλγόριθμος είναι ο HC (Hill Climbing ή αναρρίχηση λόφων), ο οποίος μοιάζει με τον DFS αλλά σε κάθε επανάληψη κλαδεύει όλες τις καταστάσεις που προκύπτουν από μία επέκταση εκτός από την ευρετικά βέλτιστη (δηλαδή κάθε στιγμή το Μ.Α. έχει μία κατάσταση) και μεταβαίνει στην τελευταία μόνο αν έχει καλύτερη ευρετική τιμή από το γονέα της· διαφορετικά τερματίζει έχοντας βρει μία τοπικά βέλτιστη λύση. Προφανώς ο HC δεν είναι πλήρης αλλά είναι πολύ γρήγορος και καθόλου μνημοβόρος. Υπάρχουν διάφορες παραλλαγές του που θυσιάζουν λίγη από την ταχύτητα του προκειμένου να αυξήσουν την πιθανότητα του να βρει λύση. Μία παραλλαγή είναι ο EHC (Enforced Hill Climbing ή εξαναγκασμένη αναρρίχηση λόφων), στον οποίον διατηρούνται στο Μ.Α. τα αδέρφια του τρέχοντος κόμβου και, αν η επέκταση του τελευταίου δεν οδηγήσει σε μετάβαση, αντί ο αλγόριθμος να τερματίσει εκτελεί μία αναζήτηση κατά πλάτος στα αδέρφια του μέχρι να βρεθεί μία καλύτερη κατάσταση οπότε και συνεχίζεται η αναρρίχηση από εκεί. Επίσης δημοφιλής είναι και ο SA (Simulated Annealing ή προσομοιωμένη ανόπτηση), ο οποίος δίνει μία πιθανότητα μετάβασης σε χειρότερες καταστάσεις (p), αφήνοντας έτσι περιθώριο στην αναζήτηση να ξεφύγει από τοπικά βέλτιστα. Αν η πιθανότητα p τείνει στο 0 ο SA λειτουργεί όπως ο HC. Επίσης υπάρχει ο TS (Taboo Search ή αναζήτηση με απαγορεύσεις), όπου σε κάθε επέκταση γίνεται πάντα μετάβαση στο καλύτερο παιδί, ακόμα και αν είναι χειρότερη κατάσταση από την τρέχουσα, και η αναζήτηση συμβουλεύεται μία λίστα απαγορευμένων καταστάσεων (παρόμοιας λειτουργικότητας με το Κλειστό Σύνολο αλλά σταθερού μεγέθους). Ο BS (Beam Search ή ακτινωτή αναζήτηση), όπου ένας σταθερός αριθμός εκ των καλύτερων καταστάσεων παραμένει στο Μ.Α. δίνοντας τη δυνατότητα οπισθοδρόμησης αν χρειαστεί, είναι μία ακόμα επέκταση του κεντρικού αλγορίθμου αναρρίχησης λόφων.

Όλοι αυτοί οι ευρετικοί αλγόριθμοι κατάγονται από τη θεωρία μαθηματικής βελτιστοποίησης, όπου αναπτύχθηκαν για να εντοπίζουν το ελάχιστο ή το μέγιστο μίας πραγματικής συνάρτησης διακριτής μεταβλητής. Στην επίλυση προβλημάτων τον ρόλο της τελευταίας προφανώς τον παίζει η ευρετική συνάρτηση και ο χώρος των λύσεων οπτικοποιείται ως ένα γεωγραφικό «τοπίο»: όσο περισσότερο δύο λύσεις διαφέρουν τόσο απέχουν μεταξύ τους σε αυτό το τοπίο, ενώ όσο καλύτερη ευρετική τιμή έχει μία λύση τόσο υψηλότερα από το επίπεδο του «εδάφους» τοποθετείται σε αυτό το τοπίο. Το τελευταίο, καθώς οι υποψήφιες καταστάσεις είναι διακριτές μεταξύ τους, ουσιαστικά είναι ένας γράφος με κορυφές τις καταστάσεις και ακμές τους τελεστές μετάβασης. Η παραλλαγή της αναρρίχησης λόφων σε συνεχή χώρο, με στόχο την εύρεση ακρότατου μιας συνάρτησης συνεχούς μεταβλητής, ονομάζεται άνοδος κλίσης (gradient ascent, αν η συνάρτηση εκφράζει βελτιστότητα και αναζητείται το μέγιστό της) ή κάθοδος κλίσης (gradient descent, αν η συνάρτηση εκφράζει σφάλμα / απόκλιση από το βέλτιστο και αναζητείται το ελάχιστό της) και υλοποιείται με μεθόδους του απειροστικού λογισμού.

Άλλος δημοφιλής ευρετικός αλγόριθμος είναι ο BestFS (αναζήτηση πρώτα στο καλύτερο) ο οποίος κρατά όλες τις καταστάσεις στο Μ.Α. και μοιάζει με τον BFS, μόνο που σε κάθε επέκταση εφαρμόζει τον ευρετικό μηχανισμό και στην επόμενη επανάληψη μεταβαίνει στο ευρετικά βέλτιστο παιδί. Είναι πλήρης, μνημοβόρος και δεν εγγυάται ότι θα βρει τη βέλτιστη λύση αφού εξαρτάται απόλυτα από την εγκυρότητα των εκτιμήσεων της ευρετικής συνάρτησης. Τροποποίηση του BestFS αποτελεί ο πλήρης και βέλτιστος αλγόριθμος Α*, στον οποίον η ευρετική τιμή που αντιστοιχίζεται σε κάθε νέα κατάσταση Κ για να την αξιολογήσει ο μηχανισμός δεν είναι μόνο μία εκτίμηση Α της απόστασης της από μία τελική κατάσταση, αλλά το άθροισμα Α συν την ακριβή απόσταση της Κ από τη ρίζα. Ο Α* εγγυάται ότι θα βρει τη βέλτιστη λύση αρκεί η ευρετική συνάρτηση να είναι πάντα υποεκτίμηση της πραγματικής απόστασης από τη λύση και ποτέ υπερεκτίμηση («αποδεκτή συνάρτηση»). Σε περίπτωση που είναι σπουδαιότερη η ταχύτητα παρά η βελτιστότητα δε χρειάζεται η ευρετική συνάρτηση να είναι αποδεκτή. Παραλλαγή του Α* αποτελεί ο IDA* (A* με επαναληπτική εκβάθυνση) ο οποίος αναπτύσσει το δένδρο αναζήτησης κατά βάθος σε διαδοχικές επαναλήψεις, αξιοποιώντας την ευρετική συνάρτηση του Α* για να επιλέξει την επεκτεινόμενη κάθε φορά κατάσταση, αλλά όταν η ευρετική τιμή μίας νέας κατάστασης ξεπερνά το όριο που έχει τεθεί για την τρέχουσα επανάληψη όλο το υποδένδρο το οποίο ξεκινά από αυτήν κλαδεύεται. Στην επόμενη επανάληψη, όπου όπως στον ID το δένδρο αναζήτησης κατασκευάζεται από την αρχή, το νέο ευρετικό όριο τίθεται στη μικρότερη τιμή που εμφανίστηκε στις καταστάσεις οι οποίες κλαδεύτηκαν κατά την προηγούμενη επανάληψη.

Παίγνια

Μία ειδική κατηγορία προβλημάτων ΤΝ είναι τα παίγνια δύο αντιπάλων (π.χ. σκάκι). Εδώ υπάρχουν δύο διαφορετικά σύνολα τελεστών μετάβασης που εφαρμόζονται εναλλάξ από δύο ανταγωνιστικά ενεργά συστήματα (τους παίκτες). Οι τελικές καταστάσεις δεν είναι πλήρως γνωστές, έχουν όμως συγκεκριμένα γνωστά χαρακτηριστικά και αντιστοιχούν σε ισοπαλία ή σε νίκη ενός εκ των δύο αντιπάλων / ήττα του άλλου. Στα προβλήματα αυτά ξεκινώντας από μία κατάσταση μπορούμε με συνεχείς επεκτάσεις να δημιουργήσουμε το δένδρο του παιχνιδιού, με όλα τα εναλλακτικά μονοπάτια που πηγάζουν από την τρέχουσα κατάσταση, στο οποίο οι κινήσεις δύο διαδοχικών επιπέδων (όπου κίνηση είναι ένα κλαδί του δένδρου, δηλαδή η μετάβαση από μία κατάσταση σε άλλη) αντιστοιχούν σε διαφορετικό παίκτη. Η ανάπτυξη αυτού του δένδρου μπορεί να γίνει από κάθε πράκτορα προτού προβεί σε μία κίνηση μέχρι κάποιο βάθος (όσο μεγαλύτερο είναι αυτό το βάθος τόσο καλύτερα αποδίδει ο αλγόριθμος). Σε αυτό το σημείο ο παίκτης μπορεί να αξιολογήσει ευρετικά ποια από τις εναλλακτικές κινήσεις οδηγεί στην ευνοϊκότερη γι' αυτόν εξέλιξη. Στα περισσότερα πραγματικά παίγνια το βάθος του κατασκευαζόμενου σε κάθε εκτέλεση δένδρου δεν μπορεί να είναι πολύ μεγάλο λόγω του προβλήματος της συνδυαστική έκρηξης.

Ο σπουδαιότερος αλγόριθμος για επίλυση παιγνίων είναι ο Minimax (αναζήτηση ελαχίστου-μεγίστου), ο οποίος καλείται να αποφασίσει ποια θα είναι η επόμενη κίνηση του εναντίον του αντιπάλου. Κάθε φορά που εκτελείται αναπτύσσει το δένδρο του παιχνιδιού με ρίζα την τρέχουσα κατάσταση και ως ένα προκαθορισμένο βάθος, στη συνέχεια αποδίδει στα φύλλα ευρετικές τιμές οι οποίες αξιολογούν τις αντίστοιχες καταστάσεις ως ευνοϊκές γι' αυτόν (μεγάλες τιμές) ή για τον αντίπαλο (μικρές τιμές), και αποδίδει τιμές στους ενδιάμεσους κόμβους από τα φύλλα προς τη ρίζα του δένδρου ώσπου να αποκτήσει τιμή η τελευταία, θεωρώντας ότι σε κάθε επίπεδο του δένδρου κάθε παίκτης (κατάσταση-γονέας) θα επιλέξει τη συμφερότερη γι' αυτόν κίνηση (μετάβαση) από όλες τις πιθανές (καταστάσεις-παιδιά). Έτσι η τιμή κάθε κόμβου Max (κόμβου που στο δένδρο προηγείται κίνησης του ίδιου του παίκτη) είναι η μέγιστη των τιμών των παιδιών του και η τιμή κάθε κόμβου Min (κόμβου που προηγείται κίνησης του αντιπάλου) είναι η ελάχιστη των τιμών των παιδιών του. Τελικά καλύτερη κίνηση είναι αυτή που οδηγεί στον κόμβο που έδωσε τη μεγαλύτερη τιμή για τη ρίζα.

Ο αλγόριθμος ουσιαστικά εγγυάται πάντα την πιο συμφέρουσα εξέλιξη του παιχνιδιού, υποθέτοντας ότι ο αντίπαλος επιλέγει διαρκώς τις καλύτερες για εκείνον κινήσεις και δεν κάνει λάθη. Με τον Minimax υπάρχουν πάντα δυνατές κινήσεις οι οποίες φαίνεται να συμφέρουν περισσότερο, αγνοούνται όμως όταν μπορεί να οδηγήσουν σε καταστάσεις όπου ο αντίπαλος -ΑΝ κάνει την καλύτερη επιλογή- αποκτά προβάδισμα. Ο αλγόριθμος AB (Άλφα Βήτα) είναι παραλλαγή του εξαντλητικού Minimax με κλάδεμα προκειμένου να εξοικονομηθεί χρόνος, όπου αγνοούνται καταστάσεις-παιδιά οι οποίες αποκλείεται να δώσουν την τιμή τους στον γονέα τους. Στη χειρότερη περίπτωση αποδίδει σαν τον Minimax. Το κλάδεμα γίνεται με αντικειμενικά κριτήρια (όπως στον B&B), ενώ προκειμένου να βελτιωθεί η απόδοση μπορούν να επιστρατευθούν και επιπλέον ευρετικό κλάδεμα, δυναμική συνάρτηση αξιολόγησης η οποία εξαρτάται από την εξέλιξη της παρτίδας, κρυφή μνήμη τιμών αξιολόγησης και άλλες μέθοδοι. Το σπουδαιότερο πρόβλημα όμως τόσο του Minimax όσο και του AB, πέρα από την απόδοση, είναι το «πρόβλημα του ορίζοντα», κατά το οποίο η άσχημη εξέλιξη της παρτίδας δεν μπορεί τελικώς να αποφευχθεί λόγω του περιορισμένου βάθους κατασκευής του δένδρου σε κάθε στάδιο. Ένας τρόπος να μειωθεί η επίδραση του προβλήματος του ορίζοντα είναι η χρήση ειδικών αλγορίθμων ανίχνευσης οι οποίοι εντοπίζουν χρονικά σημεία της παρτίδας κατά τα οποία η κατασκευή δένδρου με μεγαλύτερο βάθος από το συνηθισμένο ενδέχεται να βελτιώσει το τελικό αποτέλεσμα.

Ικανοποίηση περιορισμών

Μία σημαντική κατηγορία προβλημάτων είναι τα προβλήματα ικανοποίησης περιορισμών. Και σε αυτά δεν είναι πλήρως γνωστές οι τελικές καταστάσεις, μόνο κάποιες ιδιότητες τους και οι περιορισμοί που πρέπει να ικανοποιούν, αλλά επίσης δε μας ενδιαφέρει και το μονοπάτι που οδηγεί στη λύση: το μόνο που επιθυμούμε να βρούμε είναι η πλήρης μορφή μίας τελικής κατάστασης. Στα προβλήματα αυτά κωδικοποιούμε τους περιορισμούς με τη βοήθεια μεταβλητών και ενός πεδίου τιμών (διακριτών ή συνεχών, ανάλογα με το πρόβλημα) από το οποίο αυτές λαμβάνουν τιμή. Οι περιορισμοί αφορούν τις πιθανές τιμές που μπορεί να ανατεθούν σε κάθε μεταβλητή (ή σε κάποιες από τις μεταβλητές) και κάθε λύση που τους ικανοποιεί είναι αποδεκτή. Στην ικανοποίηση περιορισμών μπορούν να χρησιμοποιηθούν παραλλαγές του HC προσαρμοσμένες στην αναζήτηση σε χώρο μεταβλητών, όπου εκκινούμε από μία τυχαία ανάθεση τιμών στις μεταβλητές και σταδιακά τη διορθώνουμε (με τη βοήθεια ευρετικής αξιολόγησης) ώστε να παραβιάζει λιγότερους περιορισμούς, πάντα με τον εγγενή στην αναρρίχηση λόφων κίνδυνο να παγιδευτούμε σε τοπικό ελάχιστο του σφάλματος (τοπικά βέλτιστη λύση). Συνήθως σε κάθε επανάληψη του αλγορίθμου είτε γίνεται αναζήτηση, σε όλες τις μεταβλητές, μίας τιμής που ελαχιστοποιεί περαιτέρω τις διενέξεις με τους περιορισμούς, είτε επιλέγεται τυχαία μία μεταβλητή και αναζητώνται μόνο δικές της τιμές που μειώνουν τις διενέξεις.

Εναλλακτικά μπορούμε να κωδικοποιήσουμε περαιτέρω τις μεταβλητές σε καταστάσεις, όπου ο μόνος πιθανός τελεστής είναι η ανάθεση τιμής σε μία μεταβλητή, και να εφαρμόσουμε τυφλή αναζήτηση στο χώρο καταστάσεων που προκύπτει. Η τελευταία μέθοδος όμως δεν αποδίδει καλά σε μεγάλους χώρους λόγω της συνδυαστικής έκρηξης, οπότε μπορεί να συνδυαστεί με αλγορίθμους συνέπειας: οι τελευταίοι ελέγχουν διαδοχικά όλους τους περιορισμούς του προβλήματος και για τον καθέναν εξετάζουν τα πεδία τιμών των μεταβλητών ώστε να αφαιρέσουν τις τιμές που τον παραβιάζουν. Κάθε αφαίρεση απαιτεί επανέλεγχο των περιορισμών αφού μπορεί να επηρεάζονται και άλλες μεταβλητές μέσω αυτών. Οι αλγόριθμοι συνέπειας τόξου (AC) αναπαριστούν τις μεταβλητές ως κόμβους ενός γράφου και τους περιορισμούς ως τόξα που συνδέουν τους κατάλληλους κόμβους.

Ο απλούστερος αλγόριθμος της κατηγορίας είναι ο AC-3, ο οποίος μπορεί να χειριστεί μόνο δυαδικούς περιορισμούς (στους οποίους συμμετέχουν το πολύ δύο μεταβλητές)· ωστόσο αποδεικνύεται ότι κάθε περιορισμός ανώτερης τάξης μπορεί να αναχθεί σε ένα σύνολο δυαδικών περιορισμών. Όταν ο αλγόριθμος ολοκληρώνεται μπορεί να έχει αφήσει μόνο λίγες δυνατές τιμές στα πεδία, μειώνοντας κατά πολύ το χώρο αναζήτησης, ωστόσο σχεδόν πάντα παραμένουν ασυνεπείς τιμές κάνοντας αναγκαία τη χρήση και ενός κλασικού αλγορίθμου αναζήτησης. Στην τελευταία περίπτωση ο αλγόριθμος συνέπειας χρησιμοποιείται για κλάδεμα κατά τη διάρκεια της αναζήτησης. Το κλάδεμα αυτό συμβαίνει σε κάθε επανάληψη του βρόχου οπότε αντί για την, ακριβή υπολογιστικά, πλήρη εφαρμογή ενός αλγορίθμου συνέπειας τόξου («έγκαιρη πλήρης εξέταση») μπορεί να εφαρμοστεί μία απλουστευμένη «έγκαιρη μερική εξέταση», κατά την οποία κάθε περιορισμός ελέγχεται μόνο μία φορά ακόμα και αν αφαιρεθεί κάποια τιμή από κάποιο πεδίο. Ακόμα πιο απλουστευμένος είναι ο «προοπτικός έλεγχος» κατά τον οποίον εξετάζονται μόνο τα πεδία τιμών των μεταβλητών που συνδέονται, μέσω περιορισμών, με τη μεταβλητή στην οποία ανατέθηκε τιμή κατά την προηγούμενη επανάληψη. Κατά την εκτέλεση του αλγορίθμου, αν το πεδίο τιμών μίας μεταβλητής γίνει κενό τότε η συγκεκριμένη κατάσταση απορρίπτεται, ενώ αν όλες οι μεταβλητές έχουν λάβει τιμή και δεν παραβιάζεται κανένας περιορισμός τότε ο αλγόριθμος έχει καταλήξει σε τελική κατάσταση.

Εξελικτικός υπολογισμός

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

Στους γενετικούς αλγορίθμους αρχικά παράγεται ένα σύνολο Ν υποψήφιων λύσεων για το εκάστοτε πρόβλημα (πληθυσμός n), το οποίο κατασκευάζεται τυχαία και επομένως τα περισσότερα μέλη του είναι άκυρα ή μη βέλτιστα ως λύσεις. Αυτοί οι υποψήφιοι αξιολογούνται με μία καθοριζόμενη από τον χειριστή (συνήθως ευρευτική) πραγματική συνάρτηση διακριτής μεταβλητής, τη συνάρτηση καταλληλότητας, η οποία επιχειρεί να βαθμολογήσει κάθε υποψήφιο ανάλογα με το πόσο κοντά βρίσκεται σε κάποια ιδανική λύση. Ακολούθως από τον αρχικό πληθυσμό σχηματίζονται Ν/2 ζεύγη υποψηφίων («γονέων»), με μεγαλύτερη προτεραιότητα στις πιο θετικά αξιολογημένες λύσεις, όπου κάθε υποψήφιος μπορεί να συμμετέχει σε περισσότερα από ένα ζεύγη. Τα μέλη κάθε ζεύγους συνδυάζονται με κάποιον τρόπο μεταξύ τους και το αποτέλεσμα είναι δύο νέες υποψήφιες λύσεις («απόγονοι»). Ο νέος πληθυσμός n+1 αποτελείται από το σύνολο αυτών των απογόνων (πλήρης ανανέωση). Εναλλακτικά οι απόγονοι μπορούν να συνυπάρχουν με μέλη του αμέσως προηγούμενου πληθυσμού n (μερική ανανέωση), σε κάθε περίπτωση όμως ο πληθάριθμος Ν παραμένει σταθερός σε κάθε «γενιά».

Το ποσοστό υποψηφίων που αντικαθίσταται από απογόνους ονομάζεται «χάσμα γενεών» και στην πλήρη ανανέωση είναι 100%, ενώ στη μερική ανανέωση η πιθανότητα αντικατάστασης μίας λύσης της γενιάς n από απόγονο της γενιάς n+1 είναι αντιστρόφως ανάλογη της καταλληλότητας της. Η διαδικασία αυτή επαναλαμβάνεται μέχρι να ικανοποιηθεί κάποιο κριτήριο τερματισμού, δηλαδή συνήθως να βρεθεί μία λύση που αξιολογείται ως βέλτιστη από τη συνάρτηση καταλληλότητας ή ο μέσος όρος των λύσεων του τρέχοντος πληθυσμού να τείνει να συγκλίνει σε μία μόνο λύση (ή μικρές παραλλαγές μίας). Αυτή η μεθοδολογία επιχειρεί να μιμηθεί τη βιολογική ιδέα της γενετικής διαφοροποίησης και της φυσικής επιλογής, των πυλώνων της εξέλιξης των ειδών, αλλά ουσιαστικώς η φυσική επιλογή αντικαθίσταται από μία τεχνητή επιλογή η οποία γίνεται μέσω της συνάρτησης καταλληλότητας. Η τελευταία αποτελεί και το υπέρτατο κριτήριο για την πραγματική απόδοση του αλγορίθμου.

Βιβλιογραφία και πηγές