Lineaarisen ohjelmoinnin myötä näitä menetelmiä sovellettiin ongelmiin, mukaan lukien osoitus, maksimaalinen virtaus ja kuljetus. Nykyaikana kombinatorinen optimointi on hyödyllinen algoritmien tutkimiseen, ja sillä on erityistä merkitystä tekoälylle, koneoppimiselle ja operaatioiden tutkimukselle.
Mihin kombinatorista optimointia käytetään?
Kombinatorinen optimointi on prosessi, jossa etsitään maksimia (tai minimiä) tavoitefunktiolle F, jonka toimialue on erillinen mutta suuri konfiguraatioavaruus (toisin kuin N-ulotteinen jatkuva tila).
Miksi kombinatorinen optimointi on vaikeaa?
Vaikeus johtuu siitä tosiasiasta, että toisin kuin lineaarisessa ohjelmoinnissa, kombinatorisen ongelman toteuttamiskelpoinen alue ei ole konveksi joukko. Siksi meidän on sen sijaan etsittävä toteutettavissa olevien pisteiden hila tai sekakokonaislukutapauksessa joukko disjunktoituja puoliviivoja tai viivanosia löytääksemme optimaalisen ratkaisun.
Mikä on kombinatorinen optimointiongelma?
Kombinatorinen optimointi on aihe, joka koostuu optimaalisen objektin löytämisestä äärellisestä objektijoukosta … Se toimii niiden optimointiongelmien alueella, jossa on joukko toteutettavissa olevia ratkaisuja on diskreetti tai se voidaan pelkistää diskreetiksi ja jossa tavoitteena on löytää paras ratkaisu.
Onko kombinatorinen optimointi NP vaikeaa?
Kun kombinatorisen optimointitehtävän päätösversion osoitetaan kuuluvan NP-täydellisten tehtävien luokkaan, niin optimointiversio on NP-hard … Optimointiongelma, eli vähimmäismäärän (vähintään k) löytäminen tähtimuotoisista monikulmioista, joiden liitto on yhtä suuri kuin annettu yksinkertainen monikulmio, on NP-kovaa.
