Τα
προβλήματα αυτά ανήκουν σε μια κατηγορία προβλημάτων για τα οποία δεν υπάρχει αλγόριθμος ο οποίος να τα
επιλύει σε πολυωνυμικό χρόνο.
Για
παράδειγμα, στο μοντέλο p-διάμεσος
οι πιθανές λύσεις, αν εξετάζονται ένα εκατομμύριο συνδυασμοί το δευτερόλεπτο, είναι:
—n = 50, p = 10
> 3 ώρες υπολογισμών, και
—n = 100,
p = 15
> 8 χιλιετίες υπολογισμών
Επομένως
εξετάζονται μέσω μη
καθορισμένων πολυωνυμικά ολοκληρωμένων προσεγγίσεων
Τα οποία
δεν εγγυώνται την ανεύρεση μιας συνολικά βέλτιστης λύσης, αλλά αντίθετα, κάποιου τοπικού βέλτιστου της αντικειμενικής συνάρτησης.
Οι μέθοδοι
επίλυσης μπορούν να διαφοροποιηθούν σε δύο βασικές κατηγορίες: σε κατά προσέγγιση ευριστικούς αλγόριθμους και σε ακριβείς τεχνικές επίλυσης.
ΕΠΙΛΥΣΗ ΠΡΟΒΛΗΜΑΤΩΝ Χ- Κ
