Ilovalarni tanlash vazifasi
Bitta auditoriyada dars o'tkazish uchun n ariza berilsin. Ikki xil sinf o'z vaqtida bir-biriga zid bo'lolmaydi. Har bir ilovada darsning boshi va otlari ko'rsatilgan (i-chi dastur uchun si va fi). Turli xil ilovalar bir-birining ustiga chiqishi mumkin va keyin ulardan faqat bittasini qondirish mumkin. Biz har bir dasturni [si, fi) oralig'i bilan aniqlaymiz, shunda bitta darsning oxiri boshqa darsning boshiga to'g'ri kelishi mumkin va bu kesishma deb hisoblanmaydi. Rasmiy ravishda aytganda, i va j raqamlari bo'lgan dasturlar mos keladi (mos keladi), agar intervallar kesishmasa (si, fi) va (sj, fj)
• fl £ sj yoki fj £ si). Ilovalarni tanlash vazifasi (faoliyatni tanlash muammosi) bir-biri bilan qo'shilib ketadigan ilovalarning maksimal sonini to'plashdir.
Hasis algoritm quyidagicha ishlaydi. Taxmin qilamizki, buyurtmalar tugash vaqtiga tobora ko'payib boradi:
• fl £ f 2 £ ... £ fn (1)
Agar bunday bo'lmasa, siz ularni vaqt ichida tartiblashingiz mumkin O (n log n); bir xil tugash vaqti bo'lgan buyurtmalar tasodifiy tartibda joylashtirilgan. Keyin algoritm quyidagicha ko'rinadi (f va s massiv):
Greedy-Activity- Selector (s, f)
1 n ¬ length [s]
2 A ¬ {1}
3 j ¬ 1
4 for i ¬ 2 to n
do if si ³ fj
then A ¬ A È{i}
j ¬ i
return A
Ushbu algoritmning ishlashi 1-rasmda ko'rsatilgan. F to'plami tanlangan dasturlarning raqamlaridan iborat, j - ularning oxirgilarining soni; vaqt
• Fj = max {fk: k Î A}, (17.2)
chunki dasturlar tugash vaqtini ko'paytirish orqali saralanadi. Birinchidan, A dasturning raqamini 1 va j = 1 ni (2-3 qatorlar) o'z ichiga oladi. Keyingi (4-7-qatorlardagi tsikl), ilova tugashidan oldinroq boshlanadigan dastur qidiriladi. Agar topilsa, u Φ to'plamga kiritiladi va j o'zgaruvchisiga uning raqami beriladi (6-7 qatorlar).
Greedy-Activity-Selector algoritmi faqat q (n) bosqichni talab qiladi (oldindan saralashdan tashqari). Hasis algoritmga muvofiq, har bir qadamda u bo'sh vaqtni maksimal darajada oshirish uchun tanlov qiladi.
Dostları ilə paylaş: |