Reja: Jarayonni tanlashning vazifalari

Mavzu 13. Ochko'z algoritmlar
Reja:
1. Jarayonni tanlashning vazifalari.
2. Murakkablik strategiyasining elementlari

Xayrli kun, Xabr! Bugun men ochko'z algoritmlar haqida gaplashmoqchiman.

Muayyan muammolarni hal qilishning ko'plab usullari mavjud: dinamik dasturlash, ro'yxatlash. Eshitilmagan algoritmlar kam mashhur va keng tarqalgan.

Menimcha, har bir dasturchi hayotida hech bo'lmaganda bir marta ochko'zlik bilan yozgan, ehtimol bu haqda o'ylamasdan ham. Bu nima? Mushukga xush kelibsiz.

Ochko'zlik yomonlik emas

Shunday qilib, ochko'z algoritm har bir qadamda mahalliy echimni eng maqbul variantni tanlashga imkon beradigan algoritmdir.
Masalan, Dijkstraning grafikdagi eng qisqa yo'lni topish algoritmi juda ochko'z, chunki har qadamda biz ilgari bo'lmagan og'irligi past bo'lgan cho'qqini qidiramiz va keyin boshqa uchliklarning qiymatlarini yangilaymiz. Bundan tashqari, cho'qqilarda joylashgan eng qisqa yo'llar maqbul ekanligi isbotlanishi mumkin.
Aytgancha, Floydning algoritmi, u grafikdagi eng qisqa yo'llarni ham qidiradi (garchi barcha uchlar orasidagi bo'lsa ham), ochko'z algoritmning namunasi emas. Floyd yana bir usul - dinamik dasturlash usulini namoyish etadi.
Ochko'z algoritmdan foydalanish juda oddiy. Buni quyidagi vazifaga misol sifatida ko'rib chiqing:

Jadval bo'yicha topshiriq

Vasiliy Pupkinga mustaqil dasturchi topshirig'ini bering. Har bir vazifaning o'z muddati, shuningdek uning narxi bor (ya'ni, agar u bu vazifani bajarmasa, u shunchalik ko'p pul yo'qotadi). Vasya shunchalik ajoyibki, u bitta vazifani bir kunda bajara oladi. Siz vazifani 0-dan boshlashingiz mumkin. Siz daromadni ko'paytirishingiz kerak.

Ochko'zlikdan foydalanishning klassik namunasi: Vasya eng "qimmat vazifalarni" bajarish foydalidir, ammo eng arzonini bajarib bo'lmaydi - shunda foyda ko'payadi. Savol tug'iladi: vazifalarni qanday taqsimlash kerak? Biz vazifalarni xarajatlarning pasayishi tartibida ajratamiz va jadvalni quyidagicha to'ldiramiz: agar buyurtma muddati tugashidan oldin jadvalda kamida bitta bo'sh joy mavjud bo'lsa, biz uni bunday joylarning eng oxiriga qo'yamiz, aks holda biz uni o'z vaqtida yakunlay olmaymiz, keyin bo'sh o'rindiqlarning oxiriga qo'ying.

U quyidagi kodni chiqaradi:

// vazifalar - vazifalar to'plami

Arrays.sort (vazifalar); // tushadigan qiymat bo'yicha tartiblash
TreeSet vaqt = yangi TreeSet ();
for (int i = 1; i <= n; ++ i) {
  vaqt.add (i);
}
int ans = 0;
uchun (int i = 0; i   Tmp = vaqt.floor (vazifalar [i] .time);
  if (tmp == null) {// agar jadvalda bo'sh joy bo'lmasa, oxirigacha
  time.remove (time.last ());
  } else {// aks holda vazifani bajarishingiz mumkin, jadvalga qo'shishingiz mumkin
    vaqt.remove (tmp);
    ans + = vazifalar [i] .cost;
  }
}

Qachon ochko'z bo'lishingiz mumkin?

Har doim, ba'zida iloji boricha ochko'zlikni ishlatish vasvasasi paydo bo'lishi mumkin, ammo ba'zi bir ishlarda bunga yo'l qo'yib bo'lmaydi. Masalan, sumkaning vazifasi: o'g'ri omborxonaga yo'l oldi, u erda uchta narsa saqlanadigan 10 kg, 20 kg va 30 kg va mos ravishda 60, 100 va 120 ta yog'ochdan yasalgan doimiy nanoborblonlar saqlanadi. O'g'ri maksimal 50 kilogrammni ko'tarishi mumkin. O'g'rining daromadini maksimal darajada oshirish kerak. Agar siz ochko'zlik bilan harakat qilsangiz va eng qimmatli narsani tanlasangiz (ya'ni, birinchi qismning har biriga 6 nanobarra, ikkinchi kilogramm uchun 5 nanorubble va uchdan bir kilogramm uchun 4 nanorubble), unda o'g'ri birinchi narsani har qanday usulda olishi kerak, keyin ikkinchi narsa uchun joy bo'ladi, ammo, maqbul echim ikkinchi va uchinchi narsa.
Xulosa: agar siz biron narsani o'g'irlamoqchi bo'lsangiz, u holda o'zingizga yuk mashinasini olib boring. ochko'z algoritmlarni qo'llash sohasi mavjud. Bu erda umumiy retseptlar mavjud emas, ammo juda kuchli vosita mavjud, ular yordamida ko'pchilik ochko'zlarning maqbul echimini topishingiz mumkin. Bu matroid deyiladi.

Hayot matris emas, hayot - bu cheklangan avtomat!

Vikipediyada aytilishicha, matroid bu juft (X, I) juftlikdir, bu erda X - matroidning tashuvchisi deb ataladigan cheklangan to'plam, men esa X to'plamlari mustaqil to'plam deb atalgan. Quyidagi shartlar bajarilishi kerak:

1.
Men to'plamga bo'ysunmayman. Agar asl X bo'sh bo'lsa ham - X = Ø, unda men bitta elementdan iborat bo'laman - bo'sh bo'lgan to'plam. Men = {{Ø}}

2.
Men to'plamning har qanday elementining har qanday to'plami ham ushbu to'plamning elementi bo'ladi.
3.
Agar A va B to'plamlari I to'plamga tegishli bo'lsa, shuningdek, A ning kattaligi B dan kamligi ma'lum bo'lsa, u holda B dan x gacha bo'lgan element mavjud bo'lib, u A ga tegishli emas, x va A birlashmasi I to'plamga tegishli bo'ladi, chunki bu xususiyat umuman ahamiyatsiz emas. lekin ko'pincha boshqa barcha narsalardan eng muhimi.

Agar X to'plamida w qo'shadigan og'irlik funktsiyasi mavjud bo'lsa, matroid deyiladi. Setning og'irligi uning elementlarining og'irliklari yig'indisi sifatida aniqlanadi.

Keling, vazifalar bilan mustaqil dasturchi sifatida qo'chqorlarimizga qaytaylik. Bu erda siz quyidagi matroidni ko'rishingiz mumkin: tashuvchiga ko'p vazifalar bo'lsin va mustaqil to'plamlar - muvaffaqiyatli bajarilgan vazifalar. Har bir ilovaning og'irligi uning narxiga to'g'ri keladi. Ma'lumotlar mavjudligini tekshiring

Men bir nechta matroidsman:

1. Birinchi mulk shubhasiz qoniqadi. Bo'sh bajarilgan vazifalar to'plami bizning to'plamimizga kiritilgan. Xo'sh, Vasya pul ishlashni xohlamasligi haqida qayg'urmang.
2. Ikkinchi to'plam ham mamnun. Nima uchun shunday bo'ldi: keling, tugallangan vazifalarni belgilangan muddatlarni ko'paytirish tartibida tartiblaylik. Bu tartibda ular hali ham muvaffaqiyatli bajariladi. Ushbu tartibda, muvaffaqiyatli bajarilgan vazifalarning har qanday to'plami muvaffaqiyatli bajarilishi aniq.
3. uchinchi mulk, garchi aniq bo'lmasa ham, bajariladi. Aytaylik, bizda A va B vazifalari muvaffaqiyatli bajarildi va A | B ma'lum <| B |. Odatiy bo'lib, biz vazifalarni ikkala to'plamda muddati oshib boradigan tartibda tartiblaymiz. Biz A dan bo'lmagan B topshiriqni olamiz va uni A to'plamga qo'shishga harakat qilamiz, chunki biz muvaffaqiyatga erishamiz, chunki agar Ada bo'sh joy bo'lmasa, unda bu vazifani bajarish kerak edi.

Nega men? Matroidlarning butun jozibasi Rado-Edmonds teoremasida yotadi: agar siz ob'ekt matroid ekanligini isbotlasangiz, unda ochko'z algoritm to'g'ri ishlaydi va to'g'ri natijani beradi.

Ochko'z algoritmning o'zi quyidagicha amalga oshiriladi:

  // vazn bo'yicha saralash

  Birinchidan, javob bo'sh to'plam
uchun
   agar bo'lsa // agar zarur bo'lsa
        // keyin to'plamga qo'shing
https://habr.com/en/post/120343/

8.1-misol: Yo'lovchi asansörü W kg dan ortiq ko'tarolmaydi. H odamlar liftga kirishga harakat qilishadi va ularning har biri uchun uning vazni ma'lum: W1, W2 ... WH. Bir vaqtning o'zida liftdan qancha odam chiqib ketishi mumkinligini aniqlang.

Qaror. Shubhasiz, elementar kichik vazifa - bitta kishini liftga joylashtirish. Liftga joylashtirish uchun bir nechta nomzod bo'lsa, unda eng kam vaznga ega bo'lgan odam eng yaxshi tanlov bo'ladi, chunki Shu bilan birga, tashish qobiliyatining eng katta zaxirasi saqlanib qolmoqda. Shuning uchun, muammoni hal qilish uchun, biz odamlarni o'z vazniga qarab ajratamiz va eng engilidan boshlab ularni liftga qo'yamiz, bu hali ham mumkin.
8.2 misol. Ilovalarni tanlash vazifasi.
Muayyan auditoriyada mashg'ulotlar o'tkazish uchun berilgan n ta arizalar. Har bir dastur darsning boshlanishi va tugashini ko'rsatadi (i-chi dastur uchun si va fi). Ikki xil sinf o'z vaqtida bir-biriga zid bo'lolmaydi. I va j raqamlari bilan bo'lgan da'volar, agar [si, fi) va [sj, fj) kesishmasa (mos ravishda, fi sj yoki fj ≤ si) o'zaro mos keladi. Ilovalarni tanlashning vazifasi bir-biri bilan qo'shilib ketadigan ilovalarning maksimal sonini to'plashdir.
Masalan, tugash vaqtining ko'tarilish tartibida tartiblangan quyida tavsiflangan S jarayonlarini ko'rib chiqing:
 
Qaror. Biz ushbu muammoni hal qiladigan ochko'z algoritmni taqdim etamiz. Shu bilan birga, biz ishonamizki, ilovalar tugash vaqtining ketma-ketligi bilan buyurtma qilinadi.
Faoliyat-tanlagich (lar, f)
1 n ← uzunlik [s]
2 A ← {1}
3 j ← 1
4 uchun i ← 2 dan n gacha
Agar si ≥ fj bo'lsa, 5 ni bajaring
6 keyin A ← A {i}
7 j ← i
8 qaytish A
Algoritmning ishlash usuli sek. 8.1
Protsedura quyidagicha ishlaydi. O'zgaruvchini A to'plamiga oxirgi qo'shimchani indekslaydi, bu rekursiv versiyada ai jarayoniga to'g'ri keladi.
2–3 satrlarda a1 jarayoni tanlanadi, faqat shu jarayonni o'z ichiga olgan A to'plami ishga tushiriladi va bu jarayon indeks i o'zgaruvchiga tayinlanadi. 4-7 qatorlarda Si, n + 1 muammolari boshqalardan ko'ra oldinroq tugallanadi. Ushbu tsiklda har bir jarayon o'z navbatida ko'rib chiqiladi, agar u oldindan tanlangan barcha jarayonlar bilan mos bo'lsa, A to'plamiga qo'shiladi; bu jarayon Si, n + 1 muammosidagi boshqalarga qaraganda ancha oldinroq tugaydi. Aj jarayoni A to'plamida mavjud bo'lgan jarayonlar bilan mos keladimi yoki yo'qligini bilish uchun (5-qator) uning boshlang'ich sj to'plami A to'plamiga qo'shilgan jarayonlarning oxiri oxirgi momentining boshlanishidan oldin sodir bo'lishini tekshirish kifoya. Agar jarayon yuqoridagi shartlarga javob bersa, 6-7 qatorlarda u A to'plamga qo'shiladi va j qiymati i o'zgaruvchisiga beriladi.
Algoritm O (nlog2n + n), ya'ni saralash va ortiqcha tanlov uchun ishlaydi. Har bir qadamda eng yaxshi echim tanlanadi. Biz natijada optimal natijaga erishganimizni ko'rsatamiz.
Teorem 8.1 Faoliyat tanlovchi (s, f) algoritmi mumkin bo'lgan eng ko'p sonli qo'shma dasturlarning to'plamini beradi.
Isbot. E'tibor bering, barcha dasturlar tugash vaqtini ko'paytirish orqali saralanadi. 1-sonli ilova, shubhasiz, eng maqbulga kiritilgan (agar yo'q bo'lsa, unda biz eng yaxshi ilova dasturni eng yaxshisi bilan almashtiramiz, bu uni yomonlashtirmaydi). Birinchisiga mos kelmaydigan barcha dasturlarni tashlab, biz asl vazifani kamroq dasturlar bilan olamiz. Induktsiya asosida mulohaza qilib, biz ham xuddi shunday maqbul echimga kelamiz.
 
Shakl 8.1 Operation-Selector (s, f) algoritmining ishlashi
https://studfiles.net/preview/3276187/
https://www.youtube.com/watch?v=yXYR_JuojdY
https://www.youtube.com/watch?v=ccbj9NCGTDk
https://www.youtube.com/watch?v=h2Bskvf5M-4
https://www.youtube.com/watch?v=mKQUcDg5MtQ 1-ma'ruza: Ochko'z algoritm