Algoritmni qo’llashga misol Aytaylik, Siz ochko’z o'g'risiz. Siz sumkangiz bilan do'kondasiz va u yerdagi narsalarni o'g'irlashingiz mumkin. Ammo siz faqat sumkangizga mos keladigan og’irlikdagi narsalarni olishingiz mumkin. Sumka 35 funtni ko’tarishi mumkin. Siz sumka ichiga yig'ilishi mumkin bo'lgan maksimal qiymatga ega tovarlar to'plamini olishingiz kerak. Siz qanday algoritmdan foydalanasiz? Algoritmni qo’llashga misol Bunda , xasislik algoritm juda oddiy ko'rinadi: - Sumkaga to'g'ri keladigan eng qimmat narsani tanlang.
- Sizning sumkangizga mos keladigan keyingi eng qimmat narsani tanlang ... va hokazo.
Ayrim vaqtlarda bu algoritm ishlamay qolishi mumkin. Masalan, uchta narsani o'g'irlashingiz mumkin deylik. Algoritmni qo’llashga misol - Sumka umumiy og'irligi 35 funtdan oshmaydigan tovarlarga mos keladi. Eng qimmat mahsulot - magnitafon, siz uni tanlaysiz. Endi boshqa joy qolmadi.
- Siz 3000 dollarlik tovarlar oldingiz. Shoshmay turing! Agar siz magnitafon o'rniga noutbuk va gitara tanlasangiz, tovarlar narxi 3500 dollarni tashkil etadi!
- Shubhasiz, xasislik strategiya optimal yechimni ta'minlamaydi. Biroq, natija optimal darajadan unchalik uzoq emas. Ammo do'konga kirgan o'g'ri idealga intilishi qiyin.
- “Yetarlicha yaxshi” yechim yetarli bo’ladi.
- Ikkinchi misol bizni quyidagi xulosaga olib keladi: ba'zida ideal yaxshining aksidir. Ba'zi hollarda masalani yaxshi yechimini topish uchun bu algoritm yetarli. Bunday masalalarda xasislik algoritmlar juda yaxshi ishlaydi, chunki ular oson amalga oshiriladi va natija odatda optimal yechimga yaqin bo’ladi.
Xoffman kodi - Xoffman 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 Xoffman 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.
Do'stlaringiz bilan baham: |
