Επίλυση προβλημάτων (τεχνητή νοημοσύνη): Διαφορά μεταξύ των αναθεωρήσεων

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

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

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