Evristik algoritm nima

Evristik algoritm (evristika) — algoritm bo‘lib, masalani yechishning amaliy usulini o‘z ichiga oladi. Bu usulning aniq yoki optimal natija berishi kafolatlanmaydi, biroq u qo‘yilgan masalani hal qilish uchun yetarli bo‘ladi. Aniq yechimni topish imkoni bo‘lmagan hollarda masalani tezroq hal qilishga yordam beradi.

Ta’rif

Evristik algoritm — masalani yechishga mo‘ljallangan algoritm bo‘lib, uning barcha mumkin bo‘lgan holatlarda to‘g‘ri ishlashi isbotlanmagan. Shunga qaramay, aksariyat hollarda u yetarlicha yaxshi yechim berishi ma’lum. Hatto evristik algoritmning formal jihatdan noto‘g‘ri ekani ma’lum (ya’ni isbotlangan) bo‘lishi ham mumkin. Agar u faqat ayrim, juda kam uchraydigan va oson ajratib olinadigan holatlarda noto‘g‘ri natija bersa yoki unchalik aniq bo‘lmasa-da, maqbul natija taqdim etsa, undan baribir foydalanish mumkin.

Soddaroq aytganda, evristika — matematik jihatdan to‘liq asoslanmagan (hatto «to‘liq to‘g‘ri bo‘lmagan»), biroq amalda foydali algoritmdir.

Evristika masalani yechishning to‘g‘ri algoritmidan quyidagi xususiyatlari bilan farqlanishini tushunish muhim:

  • U eng yaxshi yechim topilishini kafolatlamaydi;
  • Yechim mavjudligi oldindan aniq bo‘lsa ham, uni topishni kafolatlamaydi (ya’ni «maqsadni ko‘zdan qochirish» mumkin);
  • Ayrim hollarda noto‘g‘ri yechim berishi mumkin.

Qo‘llanilishi

Evristik algoritmlar yuqori hisoblash murakkabligiga ega masalalarni yechishda keng qo‘llanadi. Bunday hollarda ko‘p vaqt talab qiladigan, ba’zan esa texnik jihatdan imkonsiz bo‘lgan barcha variantlarni to‘liq ko‘rib chiqish o‘rniga ancha tez ishlaydigan, ammo nazariy jihatdan yetarlicha asoslanmagan algoritmdan foydalaniladi. Sun’iy intellekt sohasida, xususan, obrazlarni tanib olishda ham masalaning umumiy yechimi mavjud emasligi sababli evristik algoritmlar keng qo‘llanadi. Turli evristik yondashuvlar antivirus dasturlarida, kompyuter o‘yinlarida va boshqa sohalarda ishlatiladi. Masalan, shaxmat o‘ynaydigan dasturlar o‘yinning o‘rta bosqichida asosan evristik algoritmlarga tayanadi (o‘yinning debyutida ma’lumotlar bazasidan, endshpilida — Nalimov jadvallaridan foydalanish mumkin, biroq mittelshpilida mumkin bo‘lgan yurishlar soni ko‘pincha barcha variantlarni to‘liq ko‘rib chiqishga imkon bermaydi, to‘g‘ri o‘ynashning aniq algoritmlari esa uzoq vaqt mavjud bo‘lmagan).

Tadqiqotchi Juda Perlning ta’kidlashicha, evristik usullar muammoni kompyuter yordamida hal qilish strategiyalarini bir nechta muqobil yondashuvlardan foydalangan holda intellektual izlashga asoslanadi.

Har bir muayyan masalani yechishda evristikadan foydalanish mumkinligi (yoki bunga yo‘l qo‘yilishi) aniq va evristik usullar bilan yechish xarajatlarining o‘zaro nisbatiga, xato narxiga hamda evristikaning statistik ko‘rsatkichlariga bog‘liq. Bundan tashqari, yakuniy natijani inson baholaydigan «sog‘lom fikr filtri» mavjudligi yoki mavjud emasligi ham muhim.

Evristik yechimni baholashga misol

Mavhum misolni ko‘rib chiqaylik. Faraz qilaylik, masalani yechishning ma’lum, biroq nihoyatda murakkab aniq algoritmi hamda undan 1000 baravar kam xarajat talab qiladigan va ko‘pincha maqbul yechim beradigan evristik usul mavjud (aytaylik, 95 % hollarda). Soddalik uchun aniq yechimning qiymati ham, xatoning qiymati ham o‘zgarmas deb hisoblaymiz.

U holda evristik usulda masalani yechishning o‘rtacha qiymati (T/1000+0.05∗E), bu yerda T — aniq yechimning qiymati, E esa xatoning qiymati. Aniq va evristik usullar bilan yechish qiymatlari o‘rtasidagi o‘rtacha farq (T−T/1000−0,05∗E)=(19,98∗T−E)/20=0,999∗T−E/20, ya’ni xatoning qiymati aniq yechim qiymatidan yigirma baravar (!) oshmasa, evristik usul o‘rtacha hisobda aniq usulga qaraganda tejamkorroq bo‘ladi.

Agar olingan natijani yakunda inson tanqidiy baholasa, vaziyat yanada yaxshilanadi: evristika yo‘l qo‘ygan xato inson sezmaydigan darajada kichik bo‘lsa, odatda uning qiymati ham ancha past bo‘ladi; jiddiy xatolar esa «sog‘lom fikr filtri» orqali ajratib tashlanadi va shu sababli katta zarar keltirmaydi.

Adabiyotlar

  • S. Gudman. Algoritmlarni ishlab chiqish va tahlil qilishga kirish / S. Gudman, S. Xidetniyemi. — M. : Mir, 1981.
  • D. D. Ulman. Ma’lumotlar tuzilmalari va algoritmlar / A. V. Axo, D. E. Xopkroft, D. D. Ulman. — M. : Vilyams ; SPb. ; Kiyev, 2001.