- Boshqacha qilib aytganda, xasislik algoritmlari yordamida yechiladigan masalalar qism masala uchun optimallik xususiyatiga (have optimal substructure) ega : to’liq masalaning optimal yechimi o’zida qism masalalarning optimal yechimini mujassamlashtiradi. (Bu xususiyat haqida dinamik dasturlash haqida gaplashganda tanishib chiqdik.) Masalan, teorema 1 ni isbotlash mobaynida biz agar A – 1 raqamli arizani o’zida mujassamlashtirgan arizalarning optimal to’plami bo’ladigan bo’lsa, u holda A’=A\{1} – esa S’ (si ³ f1 shartni qanoatlantiruvchi arizalardan tashkil topgan) arizalarning minimal to’plami uchun optimal arizalar to’plami hisoblanadi.
Algoritmni qo’llashga misol - Dars jadvali tuzish masalasi
- Aytaylik, sizga imkon qadar ko'proq darslar o'tkazish kerak bo'lgan sinf xonasi mavjud. Siz quyidagi dars jadvaliga egasiz.
- Bundan barcha darslarni bitta xonada olib borib bo’lmasligini ko’ramiz. Chunki ularning vaqti bir-biriga mos kelmaydi.
Algoritmni qo’llashga misol - Sinfda eng birinchi tugaydigan darsni tanlang. Bu siz ushbu sinfda o'tkazadigan birinchi dars.
- Endi siz birinchi darsdan keyin boshlanadigan darsni tanlashingiz kerak. Keyin, yana eng tez tugaydigan darsni tanlang. U sizning ikkinchi darsingiz bo'ladi.
Xuddi shu prinsipga amal qilishni davom eting - va siz to’g’ri javobni olasiz! Keling urinib ko’ramiz. Barcha darslardan oldin rasm chizish tugaydi (soat 10:00), shuning uchun biz uni tanlaymiz. Endi sizga ertalab soat 10 dan keyin boshlanadigan va tezroq tugaydigan keyingi dars kerak. Inglish tili darsining o’tilish vaqti art darsi bilan to’g’ri kelmagani uchun u o’tilmaydi. Ammo matematika darsi o’tiladi. Oxirida cs ning o’tish vaqti matematika bilan mos kelmaydi, lekin musiqa darsi mos kelgani uchun u o’tiladi. Algoritmni qo’llashga misol - Shunday qilib, bu siz ushbu sinfda o'tkazadigan uchta dars.
- Xasislik algoritmi oddiy: har bir qadamda u eng yaxshi variantni tanlaydi. Bizning misolimizda, dars tanlashda, boshqalardan oldin bajarilgan dars tanlanadi.
- Albatta, xasislik algoritmlar har doim ham ish bermaydi. Ammo ularni amalga oshirish juda oson! Boshqa misolni ko'rib chiqaylik.
Do'stlaringiz bilan baham: |
