«Ուսապարկի խնդիր»–ի խմբագրումների տարբերություն
No edit summary |
No edit summary |
||
Տող 10. | Տող 10. | ||
=== Ուսապարկի խնդրի այլ տարբերակներ === |
=== Ուսապարկի խնդրի այլ տարբերակներ === |
||
Գոյություն ունի խնդրի շատ տարբերակներ։ Տարբերվում են միայն ուսապարկի, իրերի և ընտրությունների պայմաններով։ |
Գոյություն ունի խնդրի շատ տարբերակներ։ Տարբերվում են միայն ուսապարկի, իրերի և ընտրությունների պայմաններով։ |
||
# 0-1 ուսապարկի խնդիրը ({{lang-en|0-1 Knapsack Problem}}), յուրաքանչյուրից իրից մեկից ոչ ավելի։ |
|||
# Սահմանափակված ուսապարկ ({{lang-en|Bounded Knapsack Problem}}), յուրաքանչյուրից իրից տրված քանակից ոչ ավելի։ |
|||
== Արտաքին հղումներ == |
== Արտաքին հղումներ == |
||
15:58, 20 Օգոստոսի 2016-ի տարբերակ
Ուսապարկի խնդիրը կոմբինատոր օպտիմիզացման NP-խնդիրներից է։ Խնդիրը իրենից ներկայացնում է սահմանափակ տարողությամբ ուսապարկում, որում պետք է տեղավորել մաքսիմալ թանկարժեք իրեր։ Հենց այդտեղից է ստացել անվանումը։ Ուսապարկի խնդրի տարբեր տարբերակների հետ կարելի է հանդիպել այլ բնագավառներում՝ տնտեսագիտությունում, կիրառական մաթեմատիկայում, կրիպտոգրաֆիայում, գենետիկայում և լոգիստիկայում։
Ընդհանուր առմամբ խնդիրը իր դասական տարբերակում կարելի է ձևակերպել այսպես․ տրված բազմությամբ առարկաներով,որոնք ունեն քաշ և արժեք պետք է ընտրել ամենամեծ արժեքականությամբ ենթաբազմությունը, որը չի գերազանցում ընդհանուր քաշը։
Խնդրի դասական ձևակերպումը
Ենթադրենք ունենք իրերի հավաքածու, որից յուրաքանչյուրը ունի երկու պարամետր՝ քաշ և արժեք։ Ունենք նույնպես ուսապարկ սահմանափակ տարողությամբ։ Խնդիրը կայանում է նրանում, որ պետք է ուսապարկը հավաքել մաքսիմալ արժեքավոր իրերով և հետևել քաշային սահմանափակմանը։
Մաթեմատիկորեն խնդիրը կարելի է ձևակերպել այսպես․ ունենք բեռ։ Յուրաքանչյուր i-րդ բեռի համար սահմանված է քաշ և արժեք , ։ Տրված է W տարողություն։ Պետք է ընտրել բեռերի ենթաբազմություն, որ նրանց քաշը չգերազանցի W քաշը և գումարային արժեքականությունը լինի առավելագույնը։[1]
Ուսապարկի խնդրի այլ տարբերակներ
Գոյություն ունի խնդրի շատ տարբերակներ։ Տարբերվում են միայն ուսապարկի, իրերի և ընտրությունների պայմաններով։
- 0-1 ուսապարկի խնդիրը (անգլ.՝ 0-1 Knapsack Problem), յուրաքանչյուրից իրից մեկից ոչ ավելի։
- Սահմանափակված ուսապարկ (անգլ.՝ Bounded Knapsack Problem), յուրաքանչյուրից իրից տրված քանակից ոչ ավելի։
Արտաքին հղումներ
Ծանոթագրություններ
- ↑ Silvano, 1990, էջ 1