15- mavzu: “Dag’al kuch usuli bilan tartiblash” Reja

Mavzu: Xasislik algoritmlari
Reja:

1. 
   xasis algoritmlar.
   
2. 
   xasis tanlov xususiyatlari.
   
3. 
   Algoritm to’griligi.
   
4. 
   Algoritmni qo’llashga misol.
   
5. 
   Xoffman kodi
   

Ko'pgina optimallashtirish muammolari uchun dinamik dasturlashdan ko'ra sodda va tezkor algoritmlar mavjud. Ushbu ma'ruzada xasis algoritmlar yordamida hal qilinishi mumkin bo'lgan muammolarni ko’rib chiqamiz. Bunday algoritm natijaviy yechim ham optimal bo'lishiga umid qilgan holda har bir qadamda optimal yechimni tanlaydi. Bu har doim ham bunday natija bermaydi, lekin ko'pgina vazifalar uchun bunday algoritmlar haqiqatan ham eng maqbulligini ta'minlaydi. Bizning birinchi misolimiz - bu oddiy, ammo yetarlicha ahamiyatga ega bo’lgan arizalarni tanlash masalasi. Keyingi o’rinda, xasis algoritmlar qaysi vazifalarni yechishda qo’l kelishini muhokama qilamiz. Xasis algoritm sizga bir qator tanlovlarni amalga oshirish orqali muammoning maqbul yechimini topishga imkon beradi. Algoritmdagi har bir qaror qabul qilish nuqtasida joriy paytda eng yaxshi hisoblangan tanlov amalga oshiriladi. Ushbu evristik strategiya har doim ham eng maqbul yechimni ta'minlamaydi, ammo baribir yechim eng maqbul bo'lishi ehtimolligi mavjud.
Xasis algoritmlarni ishlab chiqish jarayonini quyida keltirilgan bosqichlarning ketma-ketligi sifatida qarash mumkin.
1. Optimallashtirish masalasini shunday ko’rinishga keltirish kerakki, bunda tanlov amalga oshirilgandan so'ng faqat bitta qism masalani hal qilish lozim bo’lsin.
2. Qo’yilgan masalaning optimal yechimini mavjudligini, bu yechimni xasis tanlov yo’li orqali olish mumkinligini va bunday tanlov har doim haqiqiy ekanligini isbotlash kerak.
3. Xasis tanlov amalga oshirilgandan so'ng qism masala qolsin, ushbu qism masalaning optimal yechimini qilingan xasis tanlov bilan birlashtirganda qo’yilgan masalaning optimal yechimiga olib kelishini ko'rsating. Yuqorida tavsiflangan jarayon keyingi vazifalarda qo'llaniladi.
Eslatma. Har qanday xasis algoritmning markazida deyarli har doim dinamik dasturlash uslubidagi yanada murakkab yechim bo'ladi.
Yuqorida aytib o'tilgan xasis algoritmning asosiy tarkibiy qismlaridan birinchisi xasis tanlov xususiyatidir: global maqbul yechimni lokal maqbul (xasis) tanlov orqali olish mumkin. Boshqacha qilib aytganda, qaysi tanlovni tanlash lozimligini muhokama qilib, biz joriy vazifada eng yaxshi hisoblanadigan tanlovni qilamiz; vujudga kelgan qism masalalarning natijalari hisobga olinmaydi. Xasis algoritmlarning va dinamik dasturlashdan farqini ko'rib chiqamiz. Dinamik dasturlashda har bir bosqichda tanlov qilinadi, lekin odatda bu tanlov qismmasalalarning yechimlariga bog'liq bo’ladi. Shuning uchun, dinamik dasturlash usulida odatda masalalar yuqoriga yo'naltirib yechiladi, ya'ni avval sodda qism masalalar, so'ngra murakkabroq masalalar qayta ishlanadi. Bitta auditoriyada dars o'tkazish uchun n ariza berilsin. Ikki xil fan bir vaqtda ustma-ust tusholmaydi. Har bir arizada darsning boshlanish va tugash vaqtlari ko'rsatilgan (i-chi ariza uchun s_i va f_i). Turli xil arizalar ustma-ust tushishi mumkin va bunda ulardan faqat bittasini qondirish mumkin. Biz har bir arizani [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 raqamli arizalar mos keladi (compatible) deyiladi, agar (s_i, f_i) va (s_j, f_j) intervallar kesishmasa (yoki boshqacha aytganda f_l £ s_j yoki f_j £ s_i). Arizalarni tanlash vazifasi (activity-selection problem) bir-biriga qo'shilib ketadigan maksimal sonidagi arizalarni to'plashdan iborat.
Xasis algoritm quyidagi tartibda ishlaydi. Faraz qilaylik, arizalar tugash vaqtining o’sishi tartibida saralangan bo’lsin:

• 
  f_l £ f ₂ £ ... £ f_n (1)
  

Xasis algoritmda joriy vaqtda eng yaxshi hisoblangan tanlov amalga oshiriladi, shundan so'ng ushbu tanlov natijasida yuzaga kelgan qism masala hal qilinadi. Xasis algoritmda qilingan tanlov oldingi tanlovlarga bog'liq bo'lishi mumkin, ammo u keyingi qism masalalarning biron bir tanlovi yoki yechimiga bog'liq bo'lolmaydi. Shunday qilib, qism masalalar o’sish tartibida yechiladigan dinamik dasturlashdan farqli o'laroq, xasis strategiya odatda kamayish tartibida amalga oshiriladi, bunda xasis tanlov birma-bir amalga oshirilganda, joriy masalaning har bir nusxasi soddalashtirilgan holatga keltiriladi.