Yechimlar daraxti
Dasturlashda xotirani va vaqtni tejash nuqtai nazaridan funksiyalar yoki formulalarni (ifodalarni) grafik ko‘rinishda “tabiiy” ifodalash (massivlarda) bilan to‘g‘ridan-to‘g‘ri bog‘liqlikka ega bo‘lmagan, lekin amallarni bajarishga maxsus yo‘naltirilgan ko‘rinishda ifodalash samaraliroq hisoblanadi. N o‘zgaruvchili Bul funksiyasi rostlik jadvalini n+1 balandlikdagi to‘liq binary daraxt ko‘rinishida ifodalash mumkin. Daraxt yaruslari (qavatlari) o‘zgaruvchilarga mos keladi, daraxt shoxlari esa o‘zgaruvlar qiymatlariga mos keladi. Chap shoxga – 0, o‘ng shoxga esa – 1 qiymat mos qo‘yiladi. Daraxt yaproqlari – oxirgi yarusda esa daraxt ildizidan shu yaproqgacha bo‘lgan yo‘lga mos kortejdagi funksiya qiymatlari mos qo‘yiladi. Bunday daraxt yechimlar daraxti yoki semantik daraxt deyiladi.
Buni quyidagicha misolda ko‘rib chiqamiz. F(A,B,C) funksiya quyidagicha rostlik jadvali bilan berilgan bo‘lsin:
1)Yechimlar daraxtini ayrim hollarda barcha barglarni bir xil qiymatga ega bo‘lgan daraxt ostilarini, shu qiymat bilan almashtirilsa yechimlar daraxti hajmining sezilarli darajada ixchamlashtiradi.
Agar bog‘liqliklarning daraxt ko‘rinishidan voz kechilsa, yechimlar daraxtini anchagina kompaktlashtirish mumkin. Quyidagicha uchta ketma-ket shakl almashtirishlardan so‘ng binary yechimlar daraxtidan binar yechimlar diagrammasi hosil bo‘ladi:
1. 0 va 1 qiymatlarni qabul qilgan yaproqlar birlashtiriladi. Natijada daraxt quyidagi ko‘rinishni oladi:
Diagrammada izomorf (o‘xshash) diagramma ostilari birlashtiriladi:
Ikkala chiquvchi shoxi ham bitta joyga boradigan tugunlar ahamiyatsiz o‘zgaruvchi sifatida tushirib qoldiriladi va bu tugunga kiruvchi shox chiquvchi shoxlar boradigan tugunlargacha davom ettiriladi.
Natijada F(A,B,C) funksiya qiymatlarini yechimlarning binar diagrammasi orqali berish mumkin:
if A=B=0 or A=C=0 and B=1 or A=B=1 and C=0 then F(A,B,C)=1 else F(A,B,C)=0
Yechimlar daraxtidan yechimlar diagrammasiga o‘tish natijasi boshlang‘ich yechimlar daraxtida o‘zgaruvchilarni yaruslarga qaysi tartibda qo‘yilganligiga ham sezilarli darajada bog‘liq.
Yuqoridagi misolda yechimlar daraxtida o‘zgaruvchilarni yaruslarga B,A, C tartibida joylashtirilsa, u holda yechimlar diagrammasi yanada ixchamlashadi:
Natijada F(A,B,C) funksiya qiymatlarini yechimlarning binar diagrammasi orqali berish mumkin:
if B=1 then F(A,B,C)=ØC else F(A,B,C)=ØA
Ushbu ko‘rilgan misol shundan dalolat beradiki, ayrim hollarda funksiyalarning shunday maxsus ko‘rinishlarini qurish mumkinki, funksiyalarni massivlar yoki formulalar yordamida ifodalash kabi universal usullarga nisbatan, xotirada kam ma’lumot saqlashni va shu bilan birga hisoblashni tezroq amalga oshirish imkonini beradi.
|
