S pojavom linearnog programiranja, ove metode su primijenjene na probleme uključujući dodjelu, maksimalni protok i transport. U modernoj eri, kombinatorna optimizacija je korisna za proučavanje algoritama, s posebnim značajem za umjetnu inteligenciju, strojno učenje i istraživanje operacija.
Za što se koristi kombinatorna optimizacija?
Kombinatorna optimizacija je proces traženja maksimuma (ili minimuma) ciljne funkcije F čija je domena diskretni, ali veliki konfiguracijski prostor (za razliku od N-dimenzionalnog kontinuirani prostor).
Zašto je kombinatorna optimizacija teška?
Poteškoća proizlazi iz činjenice da za razliku od linearnog programiranja, izvedivo područje kombinatornog problema nije konveksan skup. Stoga, umjesto toga, moramo pretražiti rešetku izvedivih točaka, ili u slučaju mješovitog cijelog broja, skup disjunktnih poluprava ili segmenata kako bismo pronašli optimalno rješenje.
Što je problem kombinatorne optimizacije?
Kombinatorna optimizacija je tema koja se sastoji od pronalaženja optimalnog objekta iz konačnog skupa objekata … Djeluje u domeni onih optimizacijskih problema u kojima je skup izvedivih rješenja je diskretno ili se može svesti na diskretno, a u kojem je cilj pronaći najbolje rješenje.
Je li kombinatorna optimizacija NP-teška?
Kada se dokaže da verzija odluke kombinatornog optimizacijskog problema pripada klasi NP-potpunih problema, tada je verzija optimizacije NP-tvrda … Problem optimizacije, tj. pronalaženje minimalnog broja (najmanje k) poligona u obliku zvijezde čija je unija jednaka danom jednostavnom poligonu je NP-teško.
