Qurumsoq(xasislik)

“Qurumsoq(xasislik)” algoritmi.

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. Agar ochko'z algoritm ushbu muammoni echishga imkon beradigan bo'lsa, qanday qilib bilasiz? Bu erda umumiy retseptlar mavjud emas, ammo hasis algoritmlar tomonidan hal qilingan muammolarga xos bo'lgan ikkita xususiyat mavjud. Bu hasis tanlov printsipi va pastki qismlarga maqbullik xususiyati. Yuqorida aytib o'tilgan hasis algoritmning asosiy tarkibiy qismlaridan birinchisi hasis tanlov xususiyatidir: global maqbul echimni mahalliy maqbul (hasis) tanlov orqali olish mumkin. Boshqacha qilib aytganda, qaysi tanlovni tanlash haqida bahslashib, biz hozirgi vazifada eng yaxshi ko'rinadigan tanlovni qilamiz; vujudga kelgan pastki qismlarning natijalari hisobga olinmaydi. Hasis va dinamik dasturlash o'rtasidagi farqni ko'rib chiqing. Dinamik dasturlashda har bir bosqichda tanlov qilinadi, lekin odatda bu tanlov pastki qismlarning yechimlariga bog'liq. Shuning uchun, dinamik dasturlash usulidan foydalanib, muammolar odatda yuqoriga yo'naltirilgan, ya'ni. avval sodda taglavhalar, so'ngra murakkabroqlari qayta ishlanadi.

Hasis algoritmda hozirgi vaqtda eng yaxshi ko'rinishga ega bo'lgan tanlov amalga oshiriladi, shundan so'ng ushbu tanlov natijasida olingan pastki band hal qilinadi. Hasis algoritmda qilingan tanlov oldingi tanlovlarga bog'liq bo'lishi mumkin, ammo u biron bir tanlovga yoki keyingi qo'shimcha vazifalarning qarorlariga bog'liq bo'lolmaydi. Shunday qilib, subkastrlar ko'tarilish tartibida hal qilinadigan dinamik dasturlardan farqli o'laroq, hasis strategiya, odatda, hasis tanlovlar birma-bir amalga oshirilganda, kamayib boruvchi tartibda yuzaga keladi, natijada joriy vazifalarning har bir misoli soddalashtirilgan holatga tushiriladi. Aytishlaricha, hasislik bilan tanlangan mulk tamoyili mahalliy optimallashtirilgan (hasis) tanlovlar ketma-ketligi global miqyosda eng maqbul echimni beradigan bo'lsa, optimallashtirish muammosiga nisbatan qo'llaniladi. Hasis va dinamik dasturlash o'rtasidagi farqni quyidagicha izohlash mumkin: har bir qadamda hasis algoritm "eng semiz parcha" ni oladi va keyin qolganlari orasidan eng yaxshisini tanlashga harakat qiladi; dinamik dasturlash algoritmi barcha variantlarning oqibatlarini oldindan hisoblash orqali qaror qabul qiladi.

Hasis algoritm maqbul echim berishini qanday isbotlash mumkin? Bu har doim ham ahamiyatsiz emas, lekin odatiy holatda bunday isbot Teorem 1 isbotida ishlatilgan sxemaga amal qiladi. Birinchidan, birinchi bosqichda hasis tanlov maqbul echimga olib boradigan yo'lni yopib qo'ymasligini isbotlaymiz: har bir echim uchun hasis tanlovga mos keladigan va undan ham yomon bo'lmagan yana bir bor. birinchi Keyin birinchi bosqichdagi hasis tanlovdan keyin paydo bo'ladigan pastki qismning boshlang'ichga o'xshashligi va dalil indüksiya bilan yakunlanishi ko'rsatilgan.

Quyi masalalar uchun maqbullik

Boshqacha qilib aytganda, hasis algoritmlar yordamida hal qilingan muammolar maqbul pastki tuzilish xususiyatiga ega: butun muammoning eng maqbul echimi pastki qismlarga maqbul echimlarni o'z ichiga oladi. (Biz bu xususiyat bilan tanishgan edik, dinamik dasturlash haqida gaplashamiz). Masalan, 1-teorema isbotida, agar A 1-sonli da'voni o'z ichiga olgan maqbul da'volar yig'indisi bo'lsa, A '= A {1} - bu da'volarning kichikroq to'plami S' uchun talablarning optimal to'plamidir, deb da'volarni o'z ichiga oladi. Hasis algoritmda hozirgi vaqtda eng yaxshi ko'rinishga ega bo'lgan tanlov amalga oshiriladi, shundan so'ng ushbu tanlov natijasida olingan pastki band hal qilinadi. Hasis algoritmda qilingan tanlov oldingi tanlovlarga bog'liq bo'lishi mumkin, ammo u biron bir tanlovga yoki keyingi qo'shimcha vazifalarning qarorlariga bog'liq bo'lolmaydi. Shunday qilib, subkastrlar ko'tarilish tartibida hal qilinadigan dinamik dasturlardan farqli o'laroq, hasis strategiya, odatda, hasis tanlovlar birma-bir amalga oshirilganda, kamayib boruvchi tartibda yuzaga keladi, natijada joriy vazifalarning har bir misoli soddalashtirilgan holatga tushiriladi. Haffman kodlari (Haffman kodlari) - ma'lumotlarning xususiyatlariga qarab odatda hajmning 20% ​​dan 90% gacha tejaydigan ma'lumotni siqishning keng tarqalgan va juda samarali usuli. Belgilar ketma-ketligini ko'rsatadigan ma'lumotlarni ko'rib chiqing. Hasis Haffman algoritmi muayyan belgilar paydo bo'lish chastotalarini o'z ichiga olgan jadvaldan foydalanadi. Ushbu jadvaldan foydalanib, har bir belgi ikkilik sim shaklida maqbul vakili aniqlanadi. Aytaylik, siz siqmoqchi bo'lgan 100000 ta belgi ma'lumotlari fayli mavjud. Ushbu fayldagi belgilar 1-jadvalda ko'rsatilgan chastota bilan topilgan. Shunday qilib, butun fayl oltita turli xil belgilarni o'z ichiga oladi va masalan, a belgisi unda 45000 marta uchraydi. Bunday ma'lumotlar faylini taqdim etishning ko'plab usullari mavjud. Ikkilik belgilar kodini ishlab chiqish vazifasini ko'rib chiqing, unda har bir belgi noyob ikkilik satr bilan ifodalanadi.

Agar sobit uzunlikdagi kod yoki yagona kod ishlatilsa, oltita belgini ko'rsatish uchun 3 bit kerak bo'ladi: a = 000, b = 001, ..., / = 101. Ushbu usuldan foydalanganda butun faylni kodlash uchun 300000 bit kerak bo'ladi. Yaxshi natijalarga erishish mumkinmi?

1-jadval. Belgilar ketma-ketligini kodlash vazifasi.

O'zgaruvchan uzunlikdagi kod yoki notekis koddan foydalanib, sobit uzunlikdagi kodni ishlatishdan ancha yaxshi natijalarga erishish mumkin. Bunga tez-tez uchraydigan belgilar qisqa kodli so'zlar bilan, kamdan-kam uchraydigan belgilar uzoq belgilar bilan solishtirilganligi sababli erishiladi.

Bunday kod 1-jadvalning oxirgi qatorida keltirilgan. Unda a harfi 1 bitli satr bilan ifodalanadi, f harfi esa 4 bitli satr bilan ifodalanadi 1100. Ushbu koddan foydalanib faylni ko'rsatish uchun sizga kerak bo'ladi (45 • 1 + 13 • 3 + 12 • 3 + 16 • 3 + 9 • 4 + 5 • 4) • 1000 = 224000 bit. Bu qo'shimcha ravishda tovushning 25 foizini tejaydi.

Faqatgina A, B, C, D harflaridan iborat bo'lgan 130 uzunlikdagi chiziqni ko'rib chiqing. Bundan tashqari, har bir belgining chastotasi ma'lum deb hisoblang: ABCD 70 3 20 37 Bizning vazifamiz har bir belgi uchun tegishli kodlangan bo'lishi uchun bit kodni berishdir. chiziq imkon qadar qisqa edi. Kodlash variantlaridan biri: A = 00, B = 01, C = 10, D = 11. Keyin kodda 260 bit bo'ladi. Men A kodli belgi bir bit bilan kodlangan kodlash bilan shug'ullanishni xohlayotganim intuitiv ravishda ravshan (masalan, B qiymati uchga teng bo'lishi mumkin).

Biroq, turli xil uzunlikdagi bitli ketma-ketlik bilan belgilarni kodlashda dekodlash muammosi paydo bo'lishi mumkin. Ushbu muammoni hal qilishning bir usuli - bu prefiks kodlash. Ushbu kodlash bilan har qanday ikkita belgi uchun birining kodi boshqasining kodi prefiksi emas. Har bir bunday kodlash qirralarida 0 va 1 bo'lgan to'liq bargli (har bir uchida yoki nol yoki ikkita o'g'il) ikkilik daraxti va barglarida kodlangan belgilar bilan ifodalanishi mumkin.