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.

Hasislik tanlovi

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.

Hasislik tanlovi

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.

Ilovalarni tanlash vazifasi

Bitta auditoriyada dars o'tkazish uchun n ariza berilsin. Ikki xil sinf o'z vaqtida bir-biriga zid bo'lolmaydi. Har bir ilovada darsning boshi va otlari ko'rsatilgan (i-chi dastur uchun s_i va f_i). Turli xil ilovalar bir-birining ustiga chiqishi mumkin va keyin ulardan faqat bittasini qondirish mumkin. Biz har bir dasturni [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 raqamlari bo'lgan dasturlar mos keladi (mos keladi), agar intervallar kesishmasa (s_i, f_i) va (s_j, f_j)

• f_l £ s_j yoki f_j £ s_i). Ilovalarni tanlash vazifasi (faoliyatni tanlash muammosi) bir-biri bilan qo'shilib ketadigan ilovalarning maksimal sonini to'plashdir.

Hasis algoritm quyidagicha ishlaydi. Taxmin qilamizki, buyurtmalar tugash vaqtiga tobora ko'payib boradi:

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

Agar bunday bo'lmasa, siz ularni vaqt ichida tartiblashingiz mumkin O (n log n); bir xil tugash vaqti bo'lgan buyurtmalar tasodifiy tartibda joylashtirilgan. Keyin algoritm quyidagicha ko'rinadi (f va s massiv):

Greedy-Activity- Selector (s, f)

1 n ¬ length [s]

2 A ¬ {1}

3 j ¬ 1

4 for i ¬ 2 to n

do if s_i ³ f_j

then A ¬ A È{i}

j ¬ i

return A

Ushbu algoritmning ishlashi 1-rasmda ko'rsatilgan. F to'plami tanlangan dasturlarning raqamlaridan iborat, j - ularning oxirgilarining soni; vaqt

• Fj = max {fk: k Î A}, (17.2)

chunki dasturlar tugash vaqtini ko'paytirish orqali saralanadi. Birinchidan, A dasturning raqamini 1 va j = 1 ni (2-3 qatorlar) o'z ichiga oladi. Keyingi (4-7-qatorlardagi tsikl), ilova tugashidan oldinroq boshlanadigan dastur qidiriladi. Agar topilsa, u Φ to'plamga kiritiladi va j o'zgaruvchisiga uning raqami beriladi (6-7 qatorlar).

Greedy-Activity-Selector algoritmi faqat q (n) bosqichni talab qiladi (oldindan saralashdan tashqari). Hasis algoritmga muvofiq, har bir qadamda u bo'sh vaqtni maksimal darajada oshirish uchun tanlov qiladi.

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.

Hasis algoritm qachon qo'llaniladi?

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.

Hasis tamoyil

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. ³ f1.

Xaffman kodlari

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.

Optimal daraxt

Bizning vazifamiz barglari ramzlar bilan belgilangan va daraxtning narxini minimallashtiradigan, deb belgilangan aniq, binar daraxtni topishdir.

(daraxtdagi i-chi belgi chuqurligi). Biz daraxtning ichki uchining chastotasini o'g'illarining chastotalari yig'indisi sifatida aniqlaymiz. Ushbu ta'rif bilan daraxtning har bir uchining chastotasi shunchaki kodlash yoki dekodlash paytida ushbu uchga kirishlar soni ekanligini ko'rish mumkin. Daraxtning narxi, ildizdan tashqari, daraxtning barcha uchlari chastotalarining yig'indisiga teng bo'ladi. Ikkala noyob belgilar eng maqbul daraxtning eng pastki qismida osib qo'yilishi aniq. NUO, f1, f2 - bu minimal chastotalar. F1 va ... fn, aka-uka va opa-singillar bo'lgan f1, ... fn chastotalar uchun maqbul daraxtning qiymati yig'indiga (f1 + f2) va chastotalar uchun eng maqbul daraxt narxiga (f1 + f2), ... fn.

Алгоритм



Xulosa

Hasis algoritmning ikkita o'ziga xos xususiyati:

  hasis printsip

 - pastki kategoriyalar uchun maqbullik xususiyati.

Subtasklar uchun maqbullik xususiyati dinamik dasturlash uchun ham amal qiladi. Ba'zi hollarda, hasis strategiya maqbuldan ham yomon bo'lmagan echimni topadi.

Foydalanilgan adabiyotlar:

1. 
   Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ» Вильямс, 2013 год, 1324 стр. Издание 3-е
   
2. 
   http://www.math.nsc.ru/LBRT/k5/OR-MMF/Kleinberg_Tardoc_algoritmy_razrabotka_i_primenenie.pdf
   
3. 
   https://e-maxx.ru/bookz/files/cormen.pdf
   
4. 
   https://studfile.net/preview/5535319/page:24/
   
5. 
   https://dl.sumdu.edu.ua/textbooks/95352/387299/index.html#p1