Գծային ծրագրավորման գալուստով այս մեթոդները կիրառվեցին խնդիրների վրա, ներառյալ հանձնարարությունը, առավելագույն հոսքը և փոխադրումը: Ժամանակակից դարաշրջանում կոմբինատոր օպտիմիզացումը օգտակար է ալգորիթմների ուսումնասիրության համար՝ հատուկ առնչություն ունենալով արհեստական ինտելեկտի, մեքենայական ուսուցման և գործառնությունների հետազոտության հետ:
Ինչի՞ համար է օգտագործվում կոմբինատոր օպտիմալացումը:
Կոմբինատոր օպտիմիզացիան գործընթաց է որոնման F օբյեկտի առավելագույն (կամ նվազագույն) ֆունկցիայի, որի տիրույթը դիսկրետ, բայց մեծ կոնֆիգուրացիայի տարածություն է (ի տարբերություն N-չափի: շարունակական տարածություն).
Ինչու է կոմբինատորական օպտիմալացումը դժվար:
Դժվարությունը ծագում է այն փաստից, որ ի տարբերություն գծային ծրագրավորման-ի, կոմբինատորային խնդրի իրագործելի շրջանը ուռուցիկ բազմություն չէ:Այսպիսով, մենք պետք է, փոխարենը, որոնենք իրագործելի կետերի վանդակ, կամ խառը ամբողջ թվի դեպքում՝ մի շարք անջատ կիսատողերի կամ ուղիղ հատվածների՝ օպտիմալ լուծում գտնելու համար։
Ի՞նչ է կոմբինատոր օպտիմալացման խնդիրը:
Կոմբինատոր օպտիմիզացիան մի թեմա է, որը բաղկացած է օբյեկտների վերջավոր հավաքածուից օպտիմալ օբյեկտ գտնելուց… Այն գործում է այն օպտիմալացման խնդիրների տիրույթում, որոնցում հնարավոր լուծումների ամբողջությունը դիսկրետ է կամ կարող է վերածվել դիսկրետի, և որի նպատակն է գտնել լավագույն լուծումը:
Արդյո՞ք կոմբինատորային օպտիմալացումը NP-դժվար է:
Երբ ապացուցվում է, որ կոմբինատոր օպտիմալացման խնդրի որոշման տարբերակը պատկանում է NP-ամբողջական խնդիրների դասին, ապա օպտիմալացման տարբերակը NP-դժվար… Օպտիմիզացման խնդիրը, Այսինքն՝ գտնելով աստղակերպ բազմանկյունների նվազագույն թիվը (նվազագույն k), որոնց միությունը հավասար է տրված պարզ բազմանկյունի, NP-կոշտ է։
