Sa 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, sa posebnim značajem za umjetnu inteligenciju, mašinsko učenje i istraživanje operacija.
Za šta 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, izvodljiva oblast kombinatornog problema nije konveksan skup. Stoga, umjesto toga, moramo pretraživati mrežu izvodljivih tačaka, ili u slučaju mješovitog cijelog broja, skup disjunktnih poluprava ili segmenata da bismo pronašli optimalno rješenje.
Šta je problem kombinatorne optimizacije?
Kombinatorna optimizacija je tema koja se sastoji od pronalaženja optimalnog objekta iz konačnog skupa objekata… Ona radi u domenu onih optimizacijskih problema u kojima je skup izvodljivih rješenja je diskretna ili se može svesti na diskretnu, a u kojoj je cilj pronaći najbolje rješenje.
Da li je 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 datom jednostavnom poligonu je NP-teško.
