Συνδυασμός Α* και min-conflicts για την επίλυση προβλημάτων ικανοποίησης περιορισμών

14-10-2013

Ο Α* είναι ένας πολύ γνωστός γενικός αλγόριθμος αναζήτησης στην Τεχνητή Νοημοσύνη. Ο αλγόριθμος αυτός είναι πλήρης και βέλτιστος αλλά έχει μεγάλες απαιτήσεις σε μνήμη. Ο αλγόριθμος min-conflicts είναι ένας απλός hill-climbing αλγόριθμος για προβλήματα ικανοποίησης περιορισμών. Ξεκινάει με μια τυχαία ανάθεση τιμών στις μεταβλητές και σε κάθε βήμα αλλάζει τιμή σε μια μεταβλητή έτσι ώστε να μειωθεί ο αριθμός των περιορισμών που παραβιάζονται. Υπάρχουν διάφοροι τρόποι να συνδυαστούν οι δύο αυτές μέθοδοι.

Στόχος της διπλωματικής είναι η υλοποίηση και η πειραματική μελέτη ενός τέτοιου τρόπου. Συγκεκριμένα, η προτεινόμενη μέθοδος θα χρησιμοποιεί τη συνάρτηση αποτίμησης καταστάσεων του min-conflicts για να καθοδηγήσει μια Α* τύπου αναζήτηση στο χώρο αναθέσεων τιμών στις μεταβλητές.

Απαιτούμενες γνώσεις: Προγραμματισμός (π.χ. C ή Java), Αλγόριθμοι και Δομές Δεδομένων, Τεχνητή Νοημοσύνη (Προβλήματα Ικανοποίησης Περιορισμών).

Επιβλέπων Καθηγητής: Κώστας Στεργίου