Fai001-2 talabasi Erkinov Jamshid Amaliy ishlar – 9-13 Ishning nomi

Alpha-Beta Azizillo ishi:

Alpha-beta Azizillo ishini tushunish uchun ikkita o'yinchi qidiruv daraxtiga misol keltiraylik
1-qadam: Birinchi bosqichda Maks o'yinchi birinchi navbatda A tugunidan harakatni boshlaydi, bu erda a= -∞ va b= +∞, bu alfa va beta qiymatlari B tuguniga o'tadi, bu erda yana a= -∞ va b= + ∞ va B tugun bir xil qiymatni o'zining D bolasiga o'tkazadi.

2-qadam: D tugunida a qiymati uning Maks uchun navbati sifatida hisoblanadi. a ning qiymati avval 2, keyin esa 3 bilan taqqoslanadi va maksimal (2, 3) = 3 D tugunidagi a qiymati bo'ladi va tugun qiymati ham 3 ga teng bo'ladi.
3-qadam: Endi algoritmni B tuguniga qaytaring, bu yerda b qiymati Min burilish bo‘lgani uchun o‘zgaradi, Endi b= +∞ mavjud keyingi tugunlar qiymati bilan solishtiriladi, ya’ni min (∞, 3) = 3, demak, B tugunida endi a= -∞, va b= 3.

Keyingi bosqichda algoritm E tugun bo'lgan B tugunining keyingi vorisi orqali o'tadi va a= -∞ va b= 3 qiymatlari ham uzatiladi.
4-qadam: E tugunida Maks o'z navbatini oladi va alfa qiymati o'zgaradi. Alfa ning joriy qiymati 5 bilan solishtiriladi, shuning uchun maks (-∞, 5) = 5, demak, E tugunida a= 5 va b= 3, bu erda a>=b, shuning uchun E ning o'ng vorisi kesiladi, va algoritm uni aylanib o'tmaydi va E tugunidagi qiymat 5 ga teng bo'ladi.

5-qadam: Keyingi bosqichda algoritm yana daraxtni B tugunidan A tuguniga qaytaradi. A tugunida alfa qiymati o'zgaradi, maksimal mavjud qiymat 3 ga teng, maksimal (-∞, 3)= 3 va b. = +∞, bu ikki qiymat endi C tugun bo'lgan A ning o'ng davomchisiga o'tadi.
C tugunida a=3 va b= +∞ va xuddi shu qiymatlar F tuguniga uzatiladi.
6-qadam: F tugunida yana a qiymati 0 ga teng bo‘lgan chap bo‘linma bilan, max(3,0)= 3 bilan, so‘ngra 1 bo‘lgan o‘ng bo‘lak bilan solishtiriladi va max(3,1)= 3 hali ham a 3 bo'lib qoladi, lekin F ning tugun qiymati 1 ga aylanadi.


7-qadam: F tugun 1 tugun qiymatini C tuguniga qaytaradi, C a= 3 va b= +∞ da, bu erda beta qiymati o'zgaradi, u 1 bilan solishtiriladi so min (∞, 1) = 1. Endi C da, a=3 va b= 1 va yana u a>=b shartni qanoatlantiradi, shuning uchun C ning G bo‘lgan keyingi bolasi kesiladi va algoritm butun G kichik daraxtini hisoblamaydi.

8-qadam: C endi 1 dan A qiymatini qaytaradi, bu erda A uchun eng yaxshi qiymat maks (3, 1) = 3. Quyida hisoblangan tugunlar va hech qachon hisoblanmagan tugunlarni ko'rsatadigan yakuniy o'yin daraxti keltirilgan. Demak, maksimallashtiruvchi uchun optimal qiymat bu misol uchun 3 ga teng.