Algoritmlarni loyihalash. Maruzachi o’qituvchi: katta o’qituvchiGanihodjayeva Dilfuza Ziyavutdinovna

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

Ushbualgoritmningishlashi 1-rasmda ko'rsatilgan. F to'plamitanlangandasturlarningraqamlaridaniborat, j - ularningoxirgilariningsoni; vaqt

• Fj = max {fk: k Î A}, (17.2)

chunkidasturlartugashvaqtiniko'paytirishorqalisaralanadi. Birinchidan, A dasturningraqamini 1 va j = 1 ni (2-3 qatorlar) o'zichigaoladi. Keyingi (4-7-qatorlardagi tsikl), ilovatugashidanoldinroqboshlanadigandasturqidiriladi. Agar topilsa, u Φ to'plamgakiritiladiva j o'zgaruvchisigauningraqamiberiladi (6-7 qatorlar).

Greedy-Activity-Selector algoritmifaqat q (n) bosqichnitalabqiladi (oldindansaralashdantashqari).Hasisalgoritmgamuvofiq, harbirqadamda u bo'shvaqtnimaksimaldarajadaoshirishuchuntanlovqiladi.