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

Algoritmning to'g'riligi

Barcha vazifalar uchun emas, hasis algoritm eng maqbul echimni beradi, lekin biznikiga beradi. Buni tekshiramiz.

Teorem 1. Greedy-Activity-Selector algoritmi mumkin bo'lgan eng ko'p sonli qo'shma dasturlarning to'plamini beradi.

Isbot. Eslatib o'tamiz, ilovalar tugash vaqtini ko'paytirish orqali tartiblangan. Birinchidan, biz 1-ilovani o'z ichiga olgan dasturlarni tanlashning eng maqbul yechimi borligini isbotlaymiz (eng tugash vaqti bilan). Aslida, agar biron-bir maqbul dasturlar to'plamida 1-ilova bo'lmasa, u holda dasturni 1-sonli ilova bo'lmagan eng erta tugash vaqti bilan almashtirish mumkin, bu dasturlarning muvofiqligini buzmaydi (chunki 1-ilova avvalgisidan oldinroq tugaydi). va hech narsa bilan kesib o'tolmaydi) va ularning umumiy sonini o'zgartirmaydi. Shuning uchun, siz hasis tanlovdan boshlab, eng yaxshi echimni izlashingiz mumkin.

Biz faqat 1-ilovani o'z ichiga olgan to'plamlarni ko'rib chiqishga kelishib olganimizdan so'ng, unga mos bo'lmagan barcha dasturlarni tashlab yuborish mumkin va vazifa qolgan ilovalar to'plamidan eng maqbul ilovalarni tanlash vazifasini qisqartirishga imkon beradi (1-sonli ilova bilan qo'shiladi). Boshqacha qilib aytganda, biz muammoni kamroq dasturlar bilan o'xshash muammoga kamaytirdik. Induktsiya asosida mulohaza qilib, biz har qadamda hasis tanlov qilsak, eng maqbul echimga erishamiz.