Ryukzak masalasi
![Kirish
Bugungi kunda ishlatilgan barcha narsalar mamlakat loyiha boshqaruvi
usullari va modellari ijrochilar darajasiga mo'ljallangan: loyiha menejerlari,
boshqaruv jamoasi, barcha zarur resurslar bilan jihozlangan mutaxassislar. Yuqori
darajalar uchun iqtisodiyotni boshqarish-tarmoqlar, davlat korporatsiyalari,
xoldinglar darajasi-loyiha boshqaruvining tegishli modellari va usullari ishlab
chiqilmagan. Biroq, bu strategik qarorlar qabul qilish darajasi, 50 haqida unga
bog'liq% loyiha faoliyatining muvaffaqiyati, barcha resurslar unga qaratilgan va
eng muhim qarorlar qabul qilinadi. [1, p. 3] bu miqdor qayd etiladi muvaffaqiyatli
loyihalar uchun muvaffaqiyatsiz loyihalar mamlakatimizda turli hisob-kitoblarga
ko'ra, 40 dan 60% gacha. Shuning uchun, loyiha boshqarish qobiliyatsiz asosiy
sabablaridan biri hisoblanadi,yuqori boshqaruv darajalari kam ishtirok etadi ushbu
faoliyatda va zamonaviy metodologiya va loyihani boshqarish texnologiyasi
hisobga olinmaydi ularning manfaatlari etarli darajada.Xorijda loyiha ehtiyoj
ilmiy-tadqiqot va rivojlantirish boshqarish, va, xususan, uning yuqori darajasi uzoq
vaqt davomida amalga oshirilgan. Bu yaratilganidan dalolat beradi va PATTERN
[2]kabi tizimlarning ishlashi, QUEST [3], TORQUE [4], PPB [5], PROFILE [6],
60-yillarning oxirida AQShda yaratilgan. Ushbu tizimlarning barchasi
rejalashtirish ob'ektining "maqsad-vazifalar" daraxti shaklida turli parametrlar,
qiymatlar bilan tavsiflanadi ular ekspert baholarini qayta ishlash yo'li bilan
belgilanadi. O'ziga xos xususiyati ushbu kompleks rejalashtirish sxemalari bir
model sifatida ishlatiladi raqamli qiymatlar (masalan, yillik xarajatlar mavzu
bo'yicha) va miqdoriy ko'rsatkichlarning ekspert baholashlari. Biroq, bu holat emas
texnikadan keng foydalanishga to'sqinlik qiladi ma'lumotlarni tayyorlash uchun
belgilangan sinf investitsiya siyosatini amalga oshirish va yirik innovatsiyalarni
moliyalashtirish bo'yicha yuqori darajadagi boshqaruv qarorlarini qabul qilish
loyihalar.
1978da mamlakatimizda bunday maqsadlar uchun analitik vosita sifatida
taklif qilindi dastur-maqsadli ierarxik sxemalar usuli ilmiy-tadqiqot va](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_2.png)
![rivojlantirish rejalashtirish [7]. Ushbu usulning afzalligi ekspert baholarini qo'llash
uchun yaxshi mo'ljallangan qurilma, qaror qabul qiluvchi shaxs (LPR) rejani
belgilaydi, mezonlarni mustaqil ravishda ko'rsatadi va ularga subyektiv bo'lmagan
hisob-kitoblarni beradi qabul qilingan rejani ham tuzatadi. Ushbu texnikada
baholash mezonlarining ikkilik tabiati va hal qiluvchi qoidalarning oddiy tuzilishi
LPRNI belgilangan maqsadlarga muvofiq cheklangan resurslarni taqsimlash
vositasini taqdim etadi dastlabki investitsiya siyosatini interaktiv tarzda o'zgartirish
uchun. Biroq, bu sodir bo'ladi tavsiya etilgan yechim olib keladigan holatlar ba'zi
past-ustuvor loyihalarni moliyalashtirish voz va o'zgartirish kerak tashkil etilgan
tashkiliy tuzilma. Shunday qilib, samarali model va algoritmlarni ishlab chiqish
zarurati paydo bo'ladi kichik tizim bo'lishi kerak bo'lgan bunday loyiha boshqaruv
tizimining yuqori darajasi uchun qurilma amalga oshiriladigan loyihalar portfelini
tanlash va boshqarish. Ushbu maqolada loyihalar portfelining maqbul tanlovi va
taqsimoti ko'rib chiqildi uni amalga oshirish uchun resurslar alohida vazifa
shaklida optimallashtirish-ryukzak haqida ko'p o'lchovli vazifa.](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_3.png)
![Ryukzak muammosi
Hozirgi vaqtda texnologik va ilmiy taraqqiyotga qaramasdan, NP-to'liq qarorida
orqa ryukzak vazifalari, haqiqiy hayotdan olingan bunday o'lchamlarning
aksariyatini hal qilish muammo bo'lib qolmoqda. [8 va 9] asosiy usullarini
ta'riflaydi, turli vazifa variantlari uchun ishlatiladi
Ryukzak muammosi
1-rasm ryukzak muammosi.
Bir o'lchovli ( cheklovli ) ryukzak muammosining misoli: umumiy og'irlikni
15 kg gacha yoki unga teng ushlab turganda pul miqdorini maksimal darajada
oshirish uchun qaysi qutilarni tanlash kerak? A bir nechta cheklangan muammo
qutilarning vaznini ham, hajmini ham ko'rib chiqishi mumkin. (Qaror: agar har bir
qutining biron bir raqami mavjud bo'lsa, unda uchta sariq quti va uchta kulrang
quti; agar ko'rsatilgan qutilar mavjud bo'lsa, unda yashil qutidan tashqari barchasi.)
Keling, KS () funktsiyasi bilan amalga oshiriladigan algoritmga va orqa
ryukzak uchun ob'ektlarning ketma-ketligini shakllantirish dinamikasiga qisqacha
to'xtalamiz. Rekursiya j - tartib raqami (noldan va undan keyin) bilan tartibga
solinadi (rasmga qarang).8). J chuqurligining har bir chaqiruvida i-element (i, j = 0,
1, ..., m-1) hisobiga qisman yechimni kengaytirishga urinish amalga oshiriladi. Shu
bilan birga, i parametri noldan va undan keyin birlikka teng bo'lgan qadam bilan
o'zgaradi, qisman yechimni kengaytirish uchun ruxsat etilgan ob'ektning eng](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_4.png)
![bo'lgan uchinchi o'rinni egallaganligi ko'rsatildi. qo ' shimchali daraxtlar va ryukzak
muammosi .
Ryukzakdagi muammolar turli sohalarda real hayotda qaror qabul qilish
jarayonida paydo bo ' ladi , masalan , xomashyoni kesishning eng kam
isrofgarchiligini topish , [4]
tanlash investitsiyalar va portfellar , [5]
uchun aktivlarni
tanlash aktivlar bilan ta ' minlangan qimmatli qog ' ozlar , [6]
va tugmachalarini yaratish
Merkle - Hellman [7]
va boshqalar ryukzak kriptotizimlari . Ruxsat etilgan
algoritmlarning dastlabki qo'llanilishlaridan biri testlarni tuzishda va skorlashda
bo'lib, unda test topshiruvchilar qaysi savollarga javob berishlarini tanlashi
mumkin. Kichik misollar uchun test topshiruvchilarga bunday tanlovni taqdim
etish juda oddiy jarayon. Masalan, agar imtihonda har biri 10 balldan iborat 12 ta
savol bo'lsa, test topshiruvchisi mumkin bo'lgan maksimal 100 ballga erishish
uchun faqat 10 ta savolga javob berishi kerak. Biroq, nuqta qiymatlarining
heterojen taqsimlanishiga ega bo'lgan testlarda tanlovni ta'minlash qiyinroq.
Feyerman va Vayss talabalarga jami 125 mumkin bo'lgan ball bilan heterojen test
beradigan tizimni taklif qildilar. Talabalardan barcha savollarga o'zlarining
qobiliyatlari bo'yicha javob berishlari so'raladi. Umumiy bal qiymati 100 ga teng
bo'lgan muammolarning mumkin bo'lgan kichik to'plamlari ichida ryukzak
algoritmi qaysi to'plam har bir o'quvchiga mumkin bo'lgan eng yuqori ballni
berishini aniqlaydi. [8]
Ta'rif: Hal qilinadigan eng keng tarqalgan muammo bu 0-1 ryukzak muammosi , bu
raqamni cheklaydi har bir turdagi nusxalarning nolga yoki bittaga nusxalari .
To ' plami berilgan 0 dan 1 gacha raqamlangan buyumlar , har biri og ' irlik bilan va
qiymat , maksimal og ' irlik hajmi bilan birga , maksimal darajaga ko ' tarish uchun
mavzu va . bu yerda buyum misollari sonini ifodalaydi ryukzakchaga qo ' shmoq .
Norasmiy ravishda , muammo ryukzaklar summasi ryukzakchaning sig ' imidan
kichik yoki unga teng bo ' lishi uchun ryukzaklardagi buyumlar qiymatlari
yig ' indisini maksimal darajada oshirishdan iborat .
Ryukzak muammosi ( BKP ) har bir elementdan bittasi bo ' lishi haqidagi
cheklovni olib tashlaydi , ammo raqamni cheklaydi har qanday turdagi](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_6.png)
![NP bilan to'ldirilgan ko'pgina muammolarga kelsak, ular maqbul bo'lmasa
ham, ularni echish mumkin. Biroq, tarjixon, yaqinlashuv topilgan eritma qiymati
va optimal eritmaning qiymati o'rtasidagi farq kafolati bilan birga keladi.Ko'p
foydali, ammo hisoblashda murakkab algoritmlarda bo'lgani kabi, yechimni taxmin
qiladigan algoritmlarni yaratish va tahlil qilish bo'yicha jiddiy tadqiqotlar
o'tkazildi. NP-Hard bo'lsa-da, ryukzak muammosi hali ham har qanday belgilangan
darajaga yaqinlashtirilishi mumkin bo'lgan algoritmlar to'plamidan biridir. Bu
shuni anglatadiki, masalaning polinom vaqtni taxminiy sxemasi mavjud. Aniqroq
aytganda, ryukzak muammosi to'liq polinomiyali vaqtni taxminiy sxemasiga
(FPTAS) ega.
Vaqtni to'liq polinomga yaqinlashtirish sxemasi
To'liq polinom vaqtni taxminiy sxemasi (FPTAS) ryukzak muammosi uchun
muammoning ma'lum vaqt polinom yechimlari yo'qligi sababi, ob'ektlar bilan
bog'liq foyda cheklanmaganligidadir. Agar foyda qiymatlarining bir nechta
ahamiyatsiz raqamlarini yaxlitlasa, u holda ular polinom bilan chegaralanadi va 1 /
ε bu erda ε yechimning to'g'riligiga bog'liqdir. Keyinchalik, bu cheklash algoritm
polinom vaqtida optimal yechimning (1- ε ) faktori ichida to'g'ri yechimni topishi
mumkinligini anglatadi. A lgoritm FPTAS bu kiritish: ε ∈ (0,1] qiymatlari bilan
ko'rsatilgan n elementlarning A ro'yxati, va og'irliklar chiqish: S 'FPTAS yechimi
P: = max // elementning eng yuqori qiymati K: = ε uchun men dan 1 ga n qil :=
uchun tugatish qaytish yordamida S 'eritmasi yuqorida ko'rsatilgan dinamik
dasturdagi qiymatlar.
Teorema: To'plam yuqoridagi algoritm bilan hisoblangan, qayerda eng maqbul
yechimdir.
Hukmdorlik munosabatlari
Hech qachon kerak bo'lmagan narsalarni tashlab, cheksiz ryukzak
muammosini echish osonroq bo'ladi. Berilgan element uchun, biz narsalar
to'plamini topdik deylik shundayki ularning umumiy vazni og'irligidan kam, va
ularning umumiy qiymati ning qiymatidan katta. Keyin optimal yechimda](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_8.png)
![ko'rinmaydi, chunki har qanday potentsial yechimni har doim yaxshilay olamiz
almashtirish bilan to'plam bilan. Shuning uchun biz umuman olganda. Bunday
hollarda, deyiladi hukmronlik qilish . (Shuni yodda tutingki, bu cheklangan
ryukzak muammolariga taalluqli emas, chunki biz allaqachon elementlarni ishlatib
yuborganmiz).Dominantlik munosabatlarini topish qidiruv maydonining hajmini
sezilarli darajada kamaytirishga imkon beradi. Bir necha xil turlari mavjud ustunlik
munosabatlari , [11]
barchasi shaklning tengsizligini qondiradi va kimdir uchun
qayerdava. Vektor har bir a'zoning nusxalari sonini bildiradi.
Modul ustunligi
Ruxsat bering bo'lishi eng yaxshi buyum , ya'ni Barcha uchun . Bu qiymatning eng
katta zichligi bo'lgan element. - uchinchi element modulli hukmronlik qilmoqda
bitta element bilan sifatida yozilgan , agar ustunlik qiladi ortiqcha bir nechta
nusxalari . Rasmiy ravishda, bo’ldi.
Ko'p ob'ektivli ryukzak muammosi
Ushbu xilma-xillik ryukzakchani to'ldirayotgan shaxsning maqsadini
o'zgartiradi. Pul foydasini ko'paytirish kabi bitta maqsad o'rniga, maqsad bir necha
o'lchovlarga ega bo'lishi mumkin. Masalan, ekologik yoki ijtimoiy muammolar,
shuningdek iqtisodiy maqsadlar bo'lishi mumkin. Portfolio va transport
logistikasini optimallashtirishni tez-tez hal qilinadigan muammolar. Misol
tariqasida siz kruiz kemasini boshqargansiz. Siz qancha taniqli komediyachilarni
yollash kerakligini hal qilishingiz kerak. Ushbu qayiq bir tonnadan ortiq
yo'lovchini qabul qila olmaydi va ko'ngilocharlarning vazni 1000 funtdan kam
bo'lishi kerak. Har bir komediyachining vazni bor, mashhurligi asosida biznes olib
boradi va aniq maosh so'raydi. Ushbu misolda siz bir nechta maqsadlarga egasiz.
Siz, albatta, sizning maoshingizni minimallashtirish bilan birga, ko'ngil
ochuvchilarning mashhurligini maksimal darajada oshirishni xohlaysiz. Bundan
tashqari, siz iloji boricha ko'proq ko'ngilocharlarga ega bo'lishni xohlaysiz.](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_9.png)
![Aytaylik, birinchi element, ikkinchi element esa,. Shartni ikkita bir o'lchovli
yoki bitta ikki o'lchovli massivda ko'rib chiqqandan so'ng (siz xohlaganingizcha).
Keling, bir o'lchovli massiv yarataylik, uning o'lchami teng bo'ladi va birinchi
element 0 ga teng bo'ladi, qolganlari esa minus cheksizlikka teng bo'ladi yoki
bizning holatimizda (kodda) -1 ga teng bo'ladi. (1-rasm). Va keyin, (2-rasm)
ko'rsatilgandek, buyumning vazn raqamiga ega elementdan boshlab, biz kodda
ko'rsatilgandek, biz uning narxini oldingisining narxiga qo'shamiz s [j] = s [j -
WeiCos [i ] [0]] + WeiCos [i] [1]; agar o'tmish minus cheksizlik bo'lmasa. Va
ikkinchi element bilan, ular birinchisi bilan kesishganda, biz ularni solishtiramiz va
ularni kattaroq massivga joylashtiramiz. Va eng oxirida, biz yana massivdan
o'tamiz va qaerda bo'lishidan qat'i nazar, eng katta elementni tanlaymiz (3-rasm).
Va shunday qilib, vaznga teng bo'lgan oxirgi pozitsiyalarda, hujayralardagi eng
qimmat elementlarning qayd etilishi tufayli eng qimmat kombinatsiyalar yoziladi.
Ko'p o'lchovli ryukzak muammosi
Ushbu xilma-xillikda ryukzak buyumining og'irligi D o'lchovli vektor bilan
berilgan va ryukzak D o'lchovli sig'im vektoriga ega . Maqsad - ryukzakchadagi
narsalar qiymatlari yig'indisini maksimal darajada oshirish, shunda har bir
o'lchovdagi og'irliklar yig'indisi oshmaydi.
Ko'p o'lchovli ryukzak, ryukzakchaga qaraganda hisoblash qiyinroq; uchun ham,
muammo yo'q EPTAS agar P NP. [23]
Biroq, algoritm [24]
siyrak misollarni samarali
echish uchun ko'rsatilgan. Agar to'plam mavjud bo'lsa, ko'p o'lchovli
ryukzakchaning misoli juda kam uchun Shunday qilib, har bir ryukzak uchun ,shu
kabi va . Bunday holatlar, masalan, o'rni tugunlari bo'lgan simsiz tarmoqdagi
paketlarni rejalashtirishda yuz beradi. [24]
Dan algoritm [24]
shuningdek, ko'p variantli
variantning siyrak holatlarini, ko'p tanlovli ko'p o'lchovli ryukzakchani hal qiladi.
IHS (Balandlikning ko'tarilishi) algoritmi 2 o'lchovli ryukzak (kvadratlarni ikki
o'lchovli o'lchov birligi kvadratiga o’tkazish) uchun eng maqbuldir: optimal
o’tkazishda ko'pi bilan besh kvadrat mavjud bo'lganda. [25]](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_10.png)
![Bir nechta ryukzak muammosi
Ushbu o'zgaruvchanlik o'xshash Chiqindilarni o’tkazish muammosi . Bu qutilarni
o’tkazish muammosidan farqi shundaki, buyumlar to'plamini tanlash mumkin,
ammo qutilarni o'rash muammosida barcha narsalar ma'lum qutilarga
joylashtirilishi kerak. Kontseptsiya shundaki, bir nechta knopkalar mavjud. Bu
ahamiyatsiz o'zgarish bo'lib tuyulishi mumkin, ammo bu dastlabki ryukzakchaning
imkoniyatlarini qo'shishga teng emas. Ushbu o'zgarish Operations Research-dagi
ko'plab yuklash va rejalashtirish muammolarida qo'llaniladi va a Polinom-vaqtni
taxminiy sxemasi . [26]
Kvadratik biriktirish muammosi
Kvadratik knopka masalasi ikkilik va chiziqli sig'im cheklovlariga bo'ysunadigan
kvadratik funktsiyani maksimal darajaga ko'taradi. [27]
Muammoni Gallo, Hammer
va Simeone 1980 yilda kiritgan, [28]
ammo muammoni birinchi davolash 1975 yilda
Vitzgallga tegishli. [29]
Jami summa muammosi
Pastki yig'indisi muammosi bu qarorning maxsus holati va har qanday
buyumning vazni qiymatga teng bo'lgan 0-1 muammolari: . Sohasida kriptografiya ,
atama ryukzak muammosi ko'pincha subset sum muammosiga maxsus murojaat
qilish uchun ishlatiladi va odatda biri sifatida tanilgan Karpning 21 ta NP-ning
to'liq muammolari . [30]
Jami summa masalasini umumlashtirish bir nechta sig'imlar bir xil imkoniyatga
ega bo'lgan bir nechta yig'indilar yig'indisi muammosi deb ataladi.
Umumlashtirishda FPTAS yo'qligi ko'rsatildi. [31]
Orqa ryukzak vazifasi ( shuningdek , naqsh vazifasi )- NP kombinatorni
optimallashtirishning to ' liq vazifasidir . Uning nomi yakuniy maqsaddan olingan :
ryukzak hajmi cheklangan bo ' lsa , ryukzak ichida imkon qadar ko ' p qimmatbaho
narsalarni qo ' yish . Ryukzak vazifasining turli xil variantlari bilan iqtisodiyot ,
amaliy matematika , kriptografiya va logistika sohalarida duch kelish mumkin .](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_11.png)
![Umuman olganda , vazifa quyidagicha ifodalanishi mumkin : " qiymat " va
" og ' irlik " xususiyatlariga ega bo ' lgan ko ' plab ob ' ektlardan maksimal to ' liq qiymat
bilan pastki qismni tanlash kerak , bu esa umumiy vaznga cheklovni kuzatadi .
Tarkib
1 klassik muammo bayonoti
Har birining ikkita parametri — massa va qiymati bo'lgan bir qator narsalar
bo'lsin. Bundan tashqari, ma'lum bir yuk hajmi bir ryukzak bor. Muammo
shundaki, ryukzakning umumiy massaga cheklanishiga rioya qilib, ichidagi
narsalarning maksimal qiymati bilan ryukzak yig'ishdir.
kattaroq qilish va
Orqa ryukzaki haqida vazifalar
Asosiy maqola: ryukzak haqida vazifalar ro'yxati
Muammoni shakllantirish, ryukzak, narsalar yoki ularning tanloviga
qo'yiladigan shartlarga qarab, juda ko'p umumlashmalarga imkon beradi. Eng
mashhur navlar quyidagilardir:
Orqa xalqa 0-1 (eng. 0-1 Knapsack Problem)[2]: har bir elementning bir nechta
nusxasi.
Cheklangan ryukzak (eng. Bounded Knapsack Problem)[3]: har bir
elementning muayyan sonidan ortiq emas. Cheksiz ryukzak (ingliz tili. Unbounded
Knapsack Problem) [3]: har bir elementning tasodifiy soni. Ko'p tanlovli ryukzak
(ingliz tili. Multiple-choice Knapsack Problem) [4]: mavzular guruhlarga bo'linadi
va har bir guruhdan faqat bitta elementni tanlash kerak. Bir nechta ryukzak (ingliz
tili. Multiple Knapsack Problem)[5]: bir nechta ryukzak bor, ularning har biri
maksimal og'irligi bilan. Har bir element har qanday ryukzak ichiga qo'yilishi yoki](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_12.png)
![qoldirilishi mumkin. Ko'p o'lchovli ryukzak (ingliz tili. Multi-dimensional
knapsack problem): og'irlik o'rniga bir nechta turli resurslar (masalan, vazn, hajm
va uslublar vaqti) beriladi. Har bir mavzu har bir resursning belgilangan miqdorini
sarflaydi. Har bir resursning umumiy xarajatlari ushbu manbadan maksimal
darajada oshmasligi uchun ob'ektlarning pastki qismini tanlash kerak va ayni
paytda ob'ektlarning umumiy qiymati maksimal[4]. Orqa ryukzakning kvadrat
vazifasi (ingliz tili. Asosiy siyosiy partiyalari va kasaba uyushmalari[tahrir]
Orqa ryukzakning chiziqli vazifasi. Orqa ryukzak vazifasining eng keng tarqalgan
variantlaridan biri chiziqli emas. U quyidagicha ifodalanishi mumkin:
Vektor qilaylik rishtadagi har bir elementning
nusxalari sonini aniqlaydi. Keyin vazifa minimal funktsiyani topishdir
Vazifalar uzluksiz va differentsiatsiya qilingan deb taxmin
qilinadi vazifa to'siqqa qarab klassik ishlab chiqarishlardan biriga tushadi
- ryukzak 0-1 - cheksiz ryukzak
- cheklangan ryukzak
Vazifalarni tanlash erkinligi f (x), g(x) agar ishlab chiqarish salohiyatini
tashkil etish, shu jumladan, vazifalar kengroq sinf, hal qilish imkonini beradi
(eng.)rus., rayonlashtirilgan namunadagi sempllarning optimal taqsimlanishi yoki
orqa ryukzakda kvadrat vazifasini hal qilish[7].
Aniq hal usullari
Yuqorida aytib o'tilganidek, ryukzak vazifasi NP sinfiga tegishli-to'liq va
uning uchun o'rtacha vaqt ichida hal qiluvchi polinom algoritmi topilmadi.
Shuning uchun, ryukzak muammosini hal qilishda siz "katta" orqa ryukzaklar
uchun qo'llanilmaydigan aniq algoritmlar va tezkor ishlaydigan, ammo muammoni
optimal echishga kafolat bermaydigan taxminiy algoritmlarni tanlashingiz kerak.
To'liq qidirish](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_13.png)
![Boshqa alohida vazifalar singari, ryukzak muammosi ham barcha mumkin
bo'lgan yechimlarni to'liq bartaraf etish yo'li bilan hal qilinishi mumkin.
Muammoning holatiga ko'ra, bir ryukzak ichiga joylashtirilishi mumkin
bo'lgan narsalarning n mavjud va og'irligi W dan oshmagan yukning maksimal
qiymatini aniqlash kerak.
Har bir element uchun 2 variantlari mavjud: ob'ekt bir ryukzak ichiga
qo'yiladi yoki ob'ekt orqa ryukzakchaga joylashtirilmaydi. So'ngra, barcha mumkin
bo'lgan variantlar busting u faqat ob'ektlar kichik miqdorda foydalanish imkonini
beradi O(n2), vaqtinchalik murakkabligi bor[8]. Ob'ektlar sonining ko'payishi
bilan, vazifa maqbul vaqt uchun bu usul bilan hal qilinmaydi.
Rasmda uchta ob'ekt uchun busting daraxti ko'rsatilgan. Har bir varaq
ob'ektlarning bir qismiga mos keladi. Yog'och tuzilgandan so'ng, og'irligi W[9] dan
oshmagan kishilar orasida maksimal qiymatga ega bo'lgan varaqni topish kerak.
Uchta element uchun yechim topishga mos keladigan to'liq qidiruv daraxti.
Har bir tugunda bu element bir ryukzak ichiga qo'yiladimi yoki yo'qligini
aniqlaydi. Tugundagi raqam ob'ekt raqamiga mos keladi. Qovurg'adagi raqamlar:
0-bu narsa olingan emas, degan ma'noni anglatadi, 1-bu nima edi.
Filiallar va chegaralar usuli](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_14.png)
![Filiallar va chegaralar usuli-bu butunlay qidirish usulining o'zgarishi bo'lib,
u butunlay qidirish daraxtining ataylab optimal bo'lmagan filiallari chiqarib
tashlanadi. To'liq qidirish usuli kabi, u eng yaxshi yechimni topishga imkon beradi
va shuning uchun aniq algoritmlarga ishora qiladi.Piter Kolesar tomonidan taklif
etilgan original algoritm (eng. 1967 yilda Piter Kolesar ob'ektlarni o'ziga xos
qiymatiga (og'irlik qiymatiga nisbatan) qarab tartiblashni va to'liq qidirish daraxtini
qurishni taklif qiladi. Uning yaxshilanishi shundaki, har bir tugun uchun daraxt
qurish jarayonida yechim qiymatining yuqori chegarasi baholanadi va daraxtni
faqat maksimal qiymatga ega bo'lgan tugun uchun qurish davom etadi[10].
Maksimal yuqori chegara daraxt bargida bo'lsa, algoritm o'z ishini tugatadi.
Filiallar va chegara usullarining busting variantlari sonini kamaytirish
qobiliyati kirish ma'lumotlariga asoslanadi. Bu ob'ektlar o'ziga xos qadriyatlar
sezilarli darajada farq bo'lsa, faqat foydalanish tavsiya etiladi[11].
0-1 ryukzak vazifasi
0-1 orqa ryukzaksi haqidagi muammoni hal qilish oldingi muammoni hal etishga
yaqin, ammo har bir ob'ekt bitta nusxada mavjudligini hisobga olish kerak. m[i,w]
— birinchi {\displaystyle i}i dan olingan narsalarning maksimal qiymati, umumiy
og'irligi w dan oshmasin.
Qayta tiklash nisbati:
yoki
yoki
Hisoblash m[n,W] aniq bir yechim topish mumkin. Agar array m[i, w]mashina
xotirasida joylashtirilgan bo'lsa, bu algoritm, ehtimol, eng samarali[12] biri
hisoblanadi.](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_15.png)
![Dinamik dasturlash usuli bilan yechimni quyidagi tarzda ko'rsatish mumkin
x o'qi bo'ylab ikki o'lchovli tekislikda, y o'qi bo'ylab — ularning vazni.
Koordinatalar boshidan boshlab birinchi bosqichda ikkita chiziq quriladi:
gorizontal, birinchi ob'ekt olinmaganiga va birinchi mavzuga mos keladigan
moyillikka mos keladi. Ularning proektsiyalari y o'qi ob'ektning vazniga teng.
Ikkinchi bosqichda yana 2 liniyasi quriladi, gorizontal( ikkinchi ob'ekt olinmagan)
yoki eğimli (ikkinchi ob'ekt olinadi). Gorizontal yoylarning uzunligi nolga teng va
obliquely — ob'ektning qiymatini qo'ying [14].
Shunday qilib, har qanday muammoni hal qilish qurilgan daraxtda bir yo'lga
to'g'ri keladi. Vazifa maksimal uzunligi[14] yo'lini topish uchun kamayadi.
Orqa o'rindiqning hajmi bo'lsin .
Orqa ryukzakni to'ldirishni tasvirlaydigan tarmoq. Kvadrat qavslar
algoritmning ushbu bosqichida umumiy qiymatni ko'rsatadi, optimal yechim doira
bilan belgilanadi
Genetik algoritmlar
Boshqa NP-optimallashtirish qiyin vazifalar kabi, ryukzak muammoni hal
qilish uchun genetik algoritmlarni ishlatiladi. Ular polinom vaqt uchun optimal
yechim topish kafolat va optimal hal yaqinlik baholash bermaydi, lekin tezroq
boshqa ma'lum deterministik yoki Heuristic usullari ancha yaxshi yechim topish
imkonini beruvchi, yaxshi vaqt ko'rsatkichlari bor.Har bir shaxs (genotip) - biz
to'plamoqchi bo'lgan narsalarning kichik to'plami (ularning umumiy og'irligi ruxsat
etilgan yuk hajmidan oshib ketishi mumkin). Qulaylik uchun ma'lumot har bir
bitning ob'ektga[19] joylashtirilganligini aniqlaydigan ikkilik qatorlar shaklida
saqlanadi.
Moslashuvchanlik funktsiyasi eritmaning maqbulligiga yaqinligini
aniqlaydi. Misol uchun, bu umumiy og'irlik yuk tashish hajmidan oshmasa,
ob'ektlarning umumiy qiymati sifatida xizmat qilishi mumkin.Eng moslashtirilgan
shaxslar kesib va qolgan e'tiborsiz bo'lgan avlodlar smenada bir qator so'ng,
algoritm, taxmin, original yechimlar yaxshilash kerak.](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_16.png)
![Unga ruxsat bering - ushbu vektor uchun ob'ektlarning umumiy
og'irligi. Keyin qo'ying:
Orqa ryukzak vazifasi bilan shifrlash
Umumiy shakldagi rishta muammosi aniq qabul qilinadigan vaqt uchun hal
etilmasligi sababli, u kriptografik vazifalarda ishlatilishi mumkin. Buning uchun
ommaviy ravishda ma'lum bo'lgan narsalar to'plami bilan biz xabarni uzatilgan
narsalar to'plami sifatida taqdim etamiz va ularning umumiy og'irligini[28]
yuboramiz. agar muallif mualliflik ma'lumotlarni tekshirish
mumkin muallifi sekin nomi bilan yuqorida berilgan foto uchun original sahifaga
sizni olib boradi.
Ryukzak vektor ochiq kalit hisoblanadi. Ochiq matnni shifrlash uchun bit
uzunlikdagi bloklarga bo'linadi, har bir bit esa orqa ryukzakda elementning
mavjudligini aniqlaydi (masalan, ochiq matn (111100) orqa ryukzakda oltita
mumkin bo'lgan narsalarning dastlabki to'rtdan biriga mos keladi). Bu birlik
ryukzak ichida ob'ekt mavjudligini ko'rsatadi, deb ishoniladi, va uning yo'qligi
uchun nol. Shundan so'ng, bu ochiq matn uchun ryukzak ichida ob'ektlar umumiy
og'irligi hisoblab, va shifrotext sifatida uzatiladi[28].Ushbu algoritm bilan shifrlash
misoli:Bir ryukzak vektor belgilangan bo'lsin a=(3,4,6,7,10, 11) uzoq n=6 bilan
Aniqlash
Orqa ryukzak vazifasini shakllantirish
Keling, orqa ryukzaki haqidagi muammoning klassik formulasini keltiraylik
(naqsh vazifalari).Vaziyat: massa uchun cheklangan quvvatga ega ryukzak mavjud;
shuningdek, ma'lum bir og'irlik va qiymatga ega bo'lgan narsalar to'plami mavjud.](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_18.png)
![9. Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.:
Научное издательство ТВП, 2001. — С. 254. — ISBN 5-85484-
014-6 .
10. Габидулин Э. М. , Кшевецкий А. С. , Колыбельников А. И. Защита
информации : учебное пособие — М.: МФТИ , 2011. — 225 с. —
ISBN 978-5-7417-0377-9
11. Осипян В. О. О системе защиты информации на основе
пробkмы рюкзака // Известия Томского политехнического
университета [Известия ТПУ]. — 2006. — Т. 309 , № 2 . — С. 209-
212 .](/data/documents/1949ca14-b0b4-4b4f-9af1-a7ea018faef9/page_22.png)
“Ryukzak masalasi ” MUNDARIJA: 1.Kirish 2.Ryukzak muammosi 3. Hisoblashning murakkabligi 4.Oldindan algoritmni dinamik dasturlash 5.hukmdorlik munosabatlari 6.Kop ob’yektli ryukzak muammosi 6.ko’p o’lchovli ryukzak muammosi 7.Bir nechta ryukzak muammosi 8.Jami ryukzak muammosi 9.XULOSA 10.ADABIYOTLAR
Kirish Bugungi kunda ishlatilgan barcha narsalar mamlakat loyiha boshqaruvi usullari va modellari ijrochilar darajasiga mo'ljallangan: loyiha menejerlari, boshqaruv jamoasi, barcha zarur resurslar bilan jihozlangan mutaxassislar. Yuqori darajalar uchun iqtisodiyotni boshqarish-tarmoqlar, davlat korporatsiyalari, xoldinglar darajasi-loyiha boshqaruvining tegishli modellari va usullari ishlab chiqilmagan. Biroq, bu strategik qarorlar qabul qilish darajasi, 50 haqida unga bog'liq% loyiha faoliyatining muvaffaqiyati, barcha resurslar unga qaratilgan va eng muhim qarorlar qabul qilinadi. [1, p. 3] bu miqdor qayd etiladi muvaffaqiyatli loyihalar uchun muvaffaqiyatsiz loyihalar mamlakatimizda turli hisob-kitoblarga ko'ra, 40 dan 60% gacha. Shuning uchun, loyiha boshqarish qobiliyatsiz asosiy sabablaridan biri hisoblanadi,yuqori boshqaruv darajalari kam ishtirok etadi ushbu faoliyatda va zamonaviy metodologiya va loyihani boshqarish texnologiyasi hisobga olinmaydi ularning manfaatlari etarli darajada.Xorijda loyiha ehtiyoj ilmiy-tadqiqot va rivojlantirish boshqarish, va, xususan, uning yuqori darajasi uzoq vaqt davomida amalga oshirilgan. Bu yaratilganidan dalolat beradi va PATTERN [2]kabi tizimlarning ishlashi, QUEST [3], TORQUE [4], PPB [5], PROFILE [6], 60-yillarning oxirida AQShda yaratilgan. Ushbu tizimlarning barchasi rejalashtirish ob'ektining "maqsad-vazifalar" daraxti shaklida turli parametrlar, qiymatlar bilan tavsiflanadi ular ekspert baholarini qayta ishlash yo'li bilan belgilanadi. O'ziga xos xususiyati ushbu kompleks rejalashtirish sxemalari bir model sifatida ishlatiladi raqamli qiymatlar (masalan, yillik xarajatlar mavzu bo'yicha) va miqdoriy ko'rsatkichlarning ekspert baholashlari. Biroq, bu holat emas texnikadan keng foydalanishga to'sqinlik qiladi ma'lumotlarni tayyorlash uchun belgilangan sinf investitsiya siyosatini amalga oshirish va yirik innovatsiyalarni moliyalashtirish bo'yicha yuqori darajadagi boshqaruv qarorlarini qabul qilish loyihalar. 1978da mamlakatimizda bunday maqsadlar uchun analitik vosita sifatida taklif qilindi dastur-maqsadli ierarxik sxemalar usuli ilmiy-tadqiqot va
rivojlantirish rejalashtirish [7]. Ushbu usulning afzalligi ekspert baholarini qo'llash uchun yaxshi mo'ljallangan qurilma, qaror qabul qiluvchi shaxs (LPR) rejani belgilaydi, mezonlarni mustaqil ravishda ko'rsatadi va ularga subyektiv bo'lmagan hisob-kitoblarni beradi qabul qilingan rejani ham tuzatadi. Ushbu texnikada baholash mezonlarining ikkilik tabiati va hal qiluvchi qoidalarning oddiy tuzilishi LPRNI belgilangan maqsadlarga muvofiq cheklangan resurslarni taqsimlash vositasini taqdim etadi dastlabki investitsiya siyosatini interaktiv tarzda o'zgartirish uchun. Biroq, bu sodir bo'ladi tavsiya etilgan yechim olib keladigan holatlar ba'zi past-ustuvor loyihalarni moliyalashtirish voz va o'zgartirish kerak tashkil etilgan tashkiliy tuzilma. Shunday qilib, samarali model va algoritmlarni ishlab chiqish zarurati paydo bo'ladi kichik tizim bo'lishi kerak bo'lgan bunday loyiha boshqaruv tizimining yuqori darajasi uchun qurilma amalga oshiriladigan loyihalar portfelini tanlash va boshqarish. Ushbu maqolada loyihalar portfelining maqbul tanlovi va taqsimoti ko'rib chiqildi uni amalga oshirish uchun resurslar alohida vazifa shaklida optimallashtirish-ryukzak haqida ko'p o'lchovli vazifa.
Ryukzak muammosi Hozirgi vaqtda texnologik va ilmiy taraqqiyotga qaramasdan, NP-to'liq qarorida orqa ryukzak vazifalari, haqiqiy hayotdan olingan bunday o'lchamlarning aksariyatini hal qilish muammo bo'lib qolmoqda. [8 va 9] asosiy usullarini ta'riflaydi, turli vazifa variantlari uchun ishlatiladi Ryukzak muammosi 1-rasm ryukzak muammosi. Bir o'lchovli ( cheklovli ) ryukzak muammosining misoli: umumiy og'irlikni 15 kg gacha yoki unga teng ushlab turganda pul miqdorini maksimal darajada oshirish uchun qaysi qutilarni tanlash kerak? A bir nechta cheklangan muammo qutilarning vaznini ham, hajmini ham ko'rib chiqishi mumkin. (Qaror: agar har bir qutining biron bir raqami mavjud bo'lsa, unda uchta sariq quti va uchta kulrang quti; agar ko'rsatilgan qutilar mavjud bo'lsa, unda yashil qutidan tashqari barchasi.) Keling, KS () funktsiyasi bilan amalga oshiriladigan algoritmga va orqa ryukzak uchun ob'ektlarning ketma-ketligini shakllantirish dinamikasiga qisqacha to'xtalamiz. Rekursiya j - tartib raqami (noldan va undan keyin) bilan tartibga solinadi (rasmga qarang).8). J chuqurligining har bir chaqiruvida i-element (i, j = 0, 1, ..., m-1) hisobiga qisman yechimni kengaytirishga urinish amalga oshiriladi. Shu bilan birga, i parametri noldan va undan keyin birlikka teng bo'lgan qadam bilan o'zgaradi, qisman yechimni kengaytirish uchun ruxsat etilgan ob'ektning eng
kichik sonining qiymatini olishga harakat qiladi. Har qanday oldingi recursive chaqiruviga o'tishda i parametri joriy darajadagi qiymatdan birlikka teng qadam bilan o'zgarishni davom ettiradi, shuningdek qisman yechimni kengaytirish uchun ruxsat etilgan ob'ektning eng kichik raqamini olishga harakat qiladi. Agar hozirgi rekursiv chaqiruvda qurilgan qisman qaror endi o'zgartirilmasa, avvalgi chaqiruvga qaytish bo'ladi. J=0 darajasidan qaytib kelganda, hisob-kitoblar to'xtatiladi, ammo bu vaqtga kelib, muammoni hal qilish allaqachon olingan va ot vektorida joylashgan. KS() funktsiyasini qo'shimcha parametri bilan ta'minlasangiz va uni takroriy chaqiruvlarda quyidagi tarzda ishlatsangiz, hisob-kitoblarning sezilarli tezlashishiga erishish mumkin. Ks ga dastlabki murojaat qilinganda () = 0 ni hisoblang. Bundan tashqari, agar qisman yechimga ba'zi rekursiv chaqiruvlar i mavzusiga kiritilgan bo'lsa, keyingi recursiv darajaga o'tishda sizni qo'yishingiz kerak. Bu qisman yechimni yanada kengaytirishga harakat qilganda, bu qiymat (nol emas) va ob'ektning boshlang'ich raqami sifatida ishlatiladi. Shuni esda tutingki, bu holda pos belgilarining vektori mutlaqo keraksiz bo'lib qoladi, unda ob'ektlarning qisman yechimiga ulangan raqamlar ilgari qayd etilgan. Ryukzak muammosi kombinatorial optimallashtirish : Har birining vazni va qiymati bo'lgan buyumlar to'plamini hisobga olgan holda, jami og'irlik berilgan chegaradan kichik yoki unga teng bo'lgan va umumiy qiymati iloji boricha katta bo'lishi uchun to'plamga kiritiladigan har bir narsaning sonini aniqlang. Bu o'z nomini belgilangan o'lcham bilan cheklangan kishi duch keladigan muammodan kelib chiqadi ryukzak va uni eng qimmatbaho buyumlar bilan to'ldirishi kerak. Muammo ko'pincha paydo bo'ladi resurslarni taqsimlash bu erda qaror qabul qiluvchilar ajratilgan byudjet yoki vaqt cheklovi bo'yicha bo'linmaydigan loyihalar yoki vazifalar to'plamini tanlashlari kerak. 1999 yil Stoni Bruk universiteti algoritmi omborini o'rganish natijasida 75 ta algoritmik masaladan ryukzak muammosi eng ommabop 19-o'rin va eng zarur