background image

37 

 

σταθερές [58]. Γνωστά  προβλήματα κλάσης  P είναι: ο γραμμικός προγραμματισμός [59], ο 

έλεγχος πρώτων αριθμός [60], η σύγκριση συμβολοσειρών, το ελάχιστο επικαλύπτων δένδρο. 

 

2.4.3 Κλάση NP-Complete 

Τα  προβλήματα  NP-Complete  είναι  ένα  υποσύνολο  προβλημάτων  στα  οποία  μπορεί  να 

αναχθεί σε πολυωνυμικό χρόνο καθένα από τα προβλήματα της  NP και η λύση των οποίων 

μπορεί να επαληθευτεί σε επίσης πολυωνυμικό χρόνο [61]. Ως αποτέλεσμα του ορισμού, αν 

υπήρχε ένας αλγόριθμος πολυωνυμικού χρόνου για τη λύση NP-Complete προβλημάτων θα 

μπορούσε  να  λυθεί  κάθε  πρόβλημα  της  NP  σε  ανάλογο  χρόνο.  Το  θεώρημα  Cook-Levin 

δείχνει  με  τη  μέθοδο  απόδειξης  δια  αναγωγής  πως  τα  Προβλήματα  Ικανοποίησης  Boolean 

ανήκουν στην κλάση NP-Complete [62]. 

 

Εκατοντάδες  προβλήματα  έχουν  διατυπωθεί  και  εισαχθεί  στην  εκτενή  λίστα  της 

κλάσης  NP-Complete.  Σε  τομείς  όπως  οι  γράφοι,  ο  μαθηματικός  προγραμματισμός,  η 

ανάλυση κειμένου και συμβολοσειρών αλλά και στα παιχνίδια συναντώνται και εκφράζονται 

τέτοια προβλήματα. Μερικά γνωστά παραδείγματα αποτελούν: το πρόβλημα σακιδίου [63], ο 

προγραμματισμός ακεραίων, ο ισομορφισμός γράφων [54], ο χρωματισμός γράφων [64], το 

πρόβλημα μονοπατιού Hamilton [65] και η δρομολόγηση οχημάτων. 

 

2.5 Μοντέλα Προβλημάτων 

 

Κάνοντας  αναγωγή  του  προβλήματος  σε  κυκλωματικό  SAT  ο  Kaye  απέδειξε  πως  ο 

Ναρκαλιευτής ανήκει στα προβλήματα NP-Complete [10]. Ορισμένες σύνθετες καταστάσεις 

του  Ναρκαλιευτή  μπορούν  να  διατυπωθούν  ως  μοντέλα  CSP  και  να  κωδικοποιηθούν  σε 

μορφή  Boolean.  Αυτό  επιτρέπει  να  λυθούν  με  εργαλεία  που  κάνουν  συνδυασμό  SAT  και 

προγραμματισμού περιορισμών. Είναι κρίσιμο να αναλυθούν τα δύο μοντέλα προβλημάτων 

ώστε να μπορεί να περιγραφεί η διαδικασία. 

 

2.5.1 CSP 

Ως  Προβλήματα  Ικανοποίησης Περιορισμών (CSP) ορίζονται τα προβλήματα που η 

επίλυση  τους  περιλαμβάνει  την  ανάθεση  κατάλληλων  τιμών  στις  μεταβλητές  τους  ώστε  να 

ικανοποιούν  ορισμένους  περιορισμούς  ή  κανόνες  [66].  Συνήθως  είναι  απαραίτητη  η  χρήση 

ευριστικών  μεθόδων  και  αλγόριθμων  συνδυαστικής  αναζήτησης  για  την  επίλυσή  τους  σε