Arizalarni tanlash vazifasi
Algoritmning to'g'riligi - Xasis algoritmlar barcha masalalar uchun optimal yechim bermay, ammo bizning masalamiz uchun beradi. Bunga ishonch hosil qilamiz.
- Teorema 1. Greedy-activity-selector algoritmi eng ko’p mumkin bo’lgan miqdordagi mos tushuvchi arizalar to’plamini beradi.
- Isboti. Eslatib o’tamiz, arizalar tugash vaqtining o’sishi bo’yicha tartiblangan. Eng avvalo arizalarni tanlashda masalaning optimal yechimi mavjud ekanligini 1 raqamli ariza uchun (eng oldin tugovchi vaqt) isbotlaymiz. Aslida agar qaysidir optimal arizalar to’plamida 1 raqamli ariza mavjud bo’lmasa, u holda undagi eng avval tugash vaqtiga ega bo’lgan arizani 1 nomerli arizaga almashtirish mumkin, bu arizalarning mosligiga zarar bermaydi ( bunda 1 raqamli ariza oldingisidan oldinroq tugaydi va u hech qanaqasiga oldingisi bilan kesishmaydi) va ularning umumiy miqdorini o’zgartirmaydi. Bundan xasis tanlovdan boshlanuvchi optimal yechimni izlash mumkin.
- Oldindan kelishilganidek, faqat 1 raqamli arizalar qatnashgan to’plamni ko’rib chiqamiz, bun shartga mos kelmaydiganlarini tashlab o’tamiz va qolgan arizalar to’plamlari (1 raqamli ariza bilan mos keluvchi) ichidan optimalini tanlash masalasini ko’rib chiqamiz. Boshqacha qilib aytganda, biz masalani kam sonli arizalar masalasiga analog qilib qo’ydik. Induksiya bo’yicha ko’rib chiqish orqali, har bir qadamda xasis tanlovni amalga oshirish orqali optimal yechimga ega bo’lamiz.
Xasis algoritm qachon qo’llaniladi? - Berilgan masalaga xasis algoritmni optimal qo’llash mumkinligini qanday bilsa bo’ladi? Bu yerda umumiy yo’riqnoma mavjud emas, lekin xasis algoritm orqali yechiladigan masalalar uchun 2 ta asos mavjud. Bu xasis tanlov prinsipi va qism masalalar uchun optimallik.
- Agar lokal (xasis) tanlovlar ketma-ketligi global optimal tanlovni bersa, u holda optimizatsion masala uchun xasis tanlov prinsipini (greedy-choice property) qo’llasa bo’ladi deyiladi. Xasis algoritm va dinamik dasturlash o’rtasidagi farqni quyidagicha tavsiflash mumkin: xasis algoritm har bir qadamda “eng yog’li bo’lakni” tanlaydi va keyin qolganlari ichidan ularning qandayligidan qat’iy nazar eng maqbulini tanlashga harakat qiladi; dinamik dasturlash esa barcha variantlar uchun asoratlarni oldindan hisobga olgan holda yechim qabul qiladi.
- Xasis algoritm optimal yechim berishini qanday isbotlash mumkin? Bu har doim ham ahamiyatsiz emas, lekin odatiy holatda bunday isbot teorem 1 isbotida ishlatilgan sxemaga amal qiladiAvvalo biz birinchi qadamda xasis tanlov optimal yechimga olib boradigan yo'lni yopib qo'ymasligini isbotlaymiz: har bir yechim uchun xasis tanlovga mos keladigan va oldingisidan yomon bo'lmagan yana bir yechim bor. Keyin birinchi bosqichdagi xasis tanlovdan keyin paydo bo'ladigan qism masala boshlang'ich masalaga o'xshashligi va mulohaza induksiya bilan yakunlanishi ko'rsatiladi.
Do'stlaringiz bilan baham: |
