Mirzo ulugʻbek nomidagi oʻzbekiston milliy universitetining jizzax filiali

Daraxt chuqurligini cheklash. Algoritm filiallarda belgilangan bo'linish soniga erishgandan so'ng to'xtaydi. Ushbu yondashuv daraxtning aniqligiga ham salbiy ta'sir qiladi.
Tugundagi minimal ruxsat etilgan misollar sonini belgilash. Misol raqami berilgan raqamdan kam bo'lgan tugunlarni yaratish uchun cheklov o'rnatiladi (masalan, 7). Bunday holda, ahamiyatsiz bo'limlar va ahamiyatsiz qoidalar yaratilmaydi.
Ushbu yondashuvlar kamdan-kam hollarda qo'llaniladi, chunki ular yaxshi natijaga kafolat bermaydi. Ko'pincha, ular faqat ma'lum holatlarda ishlaydi. Har qanday usuldan foydalanish bo'yicha tavsiyalar mavjud emas, shuning uchun tahlilchilar sinov va xatolar orqali amaliy tajriba to'plashlari kerak.
Filiallarni kesish
"O'sish" cheklovisiz, qaror daraxti juda katta va murakkab bo'lib, keyingi talqinni imkonsiz qiladi. Va agar siz 2-3 ta misol tushadigan tugunlarni yaratish uchun hal qiluvchi qoidalarni qilsangiz, ular amaliy ahamiyatini yo'qotmaydi.
Shuning uchun, ko'plab mutaxassislar muqobil variantni afzal ko'rishadi — barcha mumkin bo'lgan daraxtlarni qurish va keyin oqilona chuqurlikda tanib olish xatosining maqbul darajasini ta'minlaydigan daraxtlarni tanlash. Bunday vaziyatda asosiy vazifa daraxtning murakkabligi va aniqligi o'rtasidagi eng foydali muvozanatni topishdir.
Ammo bu erda ham muammo bor: bunday vazifa NP-to'liq vazifalar sinfiga tegishli va siz bilganingizdek, ular samarali echimlarga ega emas. Shuning uchun ular 3 bosqichda amalga oshiriladigan filiallarni kesish usuliga murojaat qilishadi:
To'liq daraxtni qurish, unda barglar bitta sinf misollarini o'z ichiga oladi.
Ikki ko'rsatkichning ta'rifi: modelning nisbiy aniqligi (to'g'ri tan olingan misollar sonining umumiy misollar soniga nisbati) va mutlaq xato (noto'g'ri tasniflangan misollar soni).
Yo'qotish modelning aniqligi va xatoning oshishiga minimal ta'sir ko'rsatadigan varaqlar va tugunlarni olib tashlash.
Shoxlarni kesish daraxtning o'sishiga qarama-qarshi, ya'ni pastdan yuqoriga, tugunlarni barglarga ketma-ket aylantirish orqali amalga oshiriladi.
"Filiallarni kesish" usuli va erta to'xtash o'rtasidagi asosiy farq aniqlik va tushunarlilik o'rtasidagi maqbul munosabatni topishdir. Shu bilan birga, o'rganish uchun ko'proq vaqt talab etiladi, chunki ushbu yondashuv doirasida to'liq daraxt dastlab quriladi.