Reja: Algoritm tushunchasi


Ilovalarni tanlash vazifasi



Download 6,66 Mb.
bet18/87
Sana31.12.2021
Hajmi6,66 Mb.
#252783
TuriПрограмма
1   ...   14   15   16   17   18   19   20   21   ...   87
Bog'liq
Algotim loyiha toliq maruza

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.


Download 6,66 Mb.

Do'stlaringiz bilan baham:
1   ...   14   15   16   17   18   19   20   21   ...   87




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish