A lineáris programozás megjelenésével ezeket a módszereket alkalmazták olyan problémákra, mint a hozzárendelés, a maximális áramlás és a szállítás. A modern korban a kombinatorikus optimalizálás hasznos az algoritmusok tanulmányozásában, különös tekintettel a mesterséges intelligencia, a gépi tanulás és az operációkutatásra.
Mire használják a kombinatorikus optimalizálást?
A kombinatorikus optimalizálás egy olyan F célfüggvény maximumának (vagy minimumának) keresésének folyamata, amelynek tartománya egy diszkrét, de nagy konfigurációs tér (szemben az N-dimenzióssal folytonos tér).
Miért nehéz a kombinatorikus optimalizálás?
A nehézség abból adódik, hogy a lineáris programozással ellentétben a kombinatorikus probléma megvalósítható tartománya nem konvex halmaz. Így ehelyett a megvalósítható pontok rácsában kell keresnünk, vagy vegyes egész eset esetén diszjunkt félegyenesek vagy szakaszok halmazában, hogy optimális megoldást találjunk.
Mi a kombinatorikus optimalizálási probléma?
A kombinatorikus optimalizálás egy olyan témakör, amely objektumok véges halmazából optimális objektum megtalálásából áll … Azon optimalizálási problémák tartományán működik, amelyekben a megvalósítható megoldások halmaza diszkrét vagy diszkrétre redukálható, és amelyben a cél a legjobb megoldás megtalálása.
Nehéz a kombinatorikus optimalizálás NP?
Ha bebizonyosodik, hogy egy kombinatorikus optimalizálási probléma döntési változata az NP-teljes feladatok osztályába tartozik, akkor az optimalizálási verzió NP-hard … Az optimalizálási probléma, azaz a minimális számú (legkevesebb k) csillag alakú sokszög megtalálása, amelyek uniója egyenlő egy adott egyszerű sokszöggel, NP-nehéz.
