Reja: Algoritm tushunchasi

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 s_i va f_i). Turli xil ilovalar bir-birining ustiga chiqishi mumkin va keyin ulardan faqat bittasini qondirish mumkin. Biz har bir dasturni [s_i, f_i) 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 (s_i, f_i) va (s_j, f_j)

• f_l £ s_j yoki f_j £ s_i). 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:

• f_l £ f ₂ £ ... £ f_n (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 s_i ³ f_j

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.