Algoritmlarni loyihalash mustaqil ishi

.”Hasis” algoritm qo’llanishi. 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 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.

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.

Daraxt tushunchasini kiritamiz.

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.

Dastur kodi mavjud:

Xulosa.Biz bu mavzuda Hasis algoritm tushunchasisni tushunib oldik.

Bunda Hasis algoritm bizga bir qator tanlovlarni amalga oshirish orqali muammoning maqbul yechimini topishga imkon beradi. Algoritmdagi har bir qaror nuqtasida hozirgi paytda eng yaxshi ko’rinishga ega bo’lgan tanlov amalga oshiriladi.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 .