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

Algoritmlarni loyihalash.

Maruzachi o’qituvchi: katta o’qituvchi Ganihodjayeva Dilfuza Ziyavutdinovna

5-Maruza: Hasis algoritmlar.

Reja:

1. 
   Hasis algoritmlar.
   
2. 
   Hasis tanlov hususiyatlari.
   
3. 
   Algoritm to’griligi.
   
4. 
   Haffmann kodi.
   

Hasis algoritmlar.

Ko'pgina optimallashtirish muammolari uchun dinamik dasturlashdan ko'ra sodda va tezkor algoritmlar mavjud. Ushbu ma'ruzada hasis algoritmlar yordamida hal qilinishi mumkin bo'lgan muammolarga qaraymiz. Bunday algoritm har bir qadamda oxirgi echim ham maqbul bo'lishiga umid qilib, mahalliy eng maqbul tanlovga aylantiradi. Bu har doim ham shunday emas - lekin ko'pgina vazifalar uchun bunday algoritmlar haqiqatan ham eng maqbulligini ta'minlaydi. Bizning birinchi misolimiz - bu oddiy, ammo unchalik ahamiyatsiz bo'lmagan dasturlarni tanlash. Keyingi, hasis algoritmlar qaysi vazifalarga mos kelishini muhokama qilamiz.

Hasis algoritm sizga bir qator tanlovlarni amalga oshirish orqali muammoning maqbul echimini topishga imkon beradi. Algoritmdagi har bir qaror nuqtasida hozirgi paytda eng yaxshi ko'rinishga ega bo'lgan tanlov amalga oshiriladi. Ushbu evristik strategiya har doim ham eng maqbul echimni ta'minlamaydi, ammo baribir yechim eng maqbul bo'lishi mumkin. Hasis algoritmlarning rivojlanishi quyida keltirilgan bosqichlarning ketma-ketligi sifatida namoyish etilishi mumkin. 1. Optimallashtirish masalasini, tanlov amalga oshirilgandan so'ng, faqat bitta pastki bandni hal qilish uchun olib keling. 2. Aslida hasis tanlov orqali olinishi mumkin bo'lgan asl muammoning eng maqbul echimi borligini isbotlang, shunda bunday tanlov har doim haqiqiy bo'ladi. 3. Hasis tanlovdan so'ng subproblemning eng maqbul echimini qilingan hasis tanlov bilan birlashtirgan va substrulning asl maqbul echimiga olib keladigan subproblema qolganligini ko'rsating. Yuqorida tavsiflangan jarayon keyingi vazifalarda qo'llaniladi. Eslatma. Har qanday hasis algoritmning markazida deyarli har doim dinamik dasturlash uslubidagi yanada murakkab echim bo'ladi. Savol hasis algoritm bizdan oldin optimizatsiya masalasini hal qila olishini qanday aniqlash mumkin? Bu erda umumiy yo'l yo'q, ammo ikkita asosiy komponentni ajratib ko'rsatish mumkin - hasis tanlov xususiyati va maqbul pastki tuzilma. Agar vazifa bu ikkita xususiyatga ega ekanligini namoyish etish mumkin bo'lsa, unda hasis algoritmni ishlab chiqish mumkin.