Με την εμφάνιση του γραμμικού προγραμματισμού, αυτές οι μέθοδοι εφαρμόστηκαν σε προβλήματα όπως η ανάθεση, η μέγιστη ροή και η μεταφορά. Στη σύγχρονη εποχή, η συνδυαστική βελτιστοποίηση είναι χρήσιμη για τη μελέτη αλγορίθμων, με ιδιαίτερη συνάφεια με την τεχνητή νοημοσύνη, τη μηχανική μάθηση και την επιχειρησιακή έρευνα.
Γιατί χρησιμοποιείται η συνδυαστική βελτιστοποίηση;
Συνδυαστική βελτιστοποίηση είναι η διαδικασία αναζήτησης μεγίστων (ή ελάχιστων) μιας αντικειμενικής συνάρτησης F της οποίας ο τομέας είναι ένας διακριτός αλλά μεγάλος χώρος διαμόρφωσης (σε αντίθεση με έναν Ν-διάστατο συνεχόμενο διάστημα).
Γιατί είναι δύσκολη η συνδυαστική βελτιστοποίηση;
Η δυσκολία προκύπτει από το γεγονός ότι σε αντίθεση με τον γραμμικό προγραμματισμό, η εφικτή περιοχή του συνδυαστικού προβλήματος δεν είναι ένα κυρτό σύνολο. Επομένως, πρέπει, αντ' αυτού, να αναζητήσουμε ένα πλέγμα εφικτών σημείων ή στην περίπτωση του μικτού ακέραιου αριθμού, ένα σύνολο ασύνδετων ημιευθειών ή γραμμικών τμημάτων για να βρούμε μια βέλτιστη λύση.
Ποιο είναι το πρόβλημα συνδυαστικής βελτιστοποίησης;
Η συνδυαστική βελτιστοποίηση είναι ένα θέμα που συνίσταται από την εύρεση ενός βέλτιστου αντικειμένου από ένα πεπερασμένο σύνολο αντικειμένων … Λειτουργεί στον τομέα εκείνων των προβλημάτων βελτιστοποίησης στα οποία το σύνολο των εφικτών λύσεων είναι διακριτή ή μπορεί να αναχθεί σε διακριτή και στην οποία ο στόχος είναι να βρεθεί η καλύτερη λύση.
Είναι η συνδυαστική βελτιστοποίηση NP-σκληρή;
Όταν μια έκδοση απόφασης ενός προβλήματος συνδυαστικής βελτιστοποίησης αποδεικνύεται ότι ανήκει στην κατηγορία των NP-πλήρης προβλημάτων, τότε η έκδοση βελτιστοποίησης είναι NP-hard … Το πρόβλημα βελτιστοποίησης, δηλ., η εύρεση του ελάχιστου αριθμού (τουλάχιστον k) πολυγώνων σε σχήμα αστεριού των οποίων η ένωση είναι ίση με ένα δεδομένο απλό πολύγωνο, είναι NP-σκληρό.
