Guruh Abror Askarov Ishdan maqsad

211-17 guruh Abror Askarov

Ishdan maqsad: Ushbu amaliy ishi natijasida o’yinlarning algoritmini tuzishda foydalaniladigan α va β izlash usulini ko’rib chiqish va amaliyotda qo’llay olish.

Masalaning qo’yilishi. α va β izlashdan foydalanib labirintda ikki nuqta orasidagi yo’lni toppish dasturini tuzing.

Uslubiy ko’rsatmalar:

α va β izlash usulini – bu o’yin davomida qadamlarning sonini kamaytirish, yani avvaldan qo’yilishi mumkin bo’lgan ammallarning sonini aniqlab berish uchun qo’llaniladi. Bu optimallashtirish ham daraxtlar va graflar bilan bog’liq bo’lib ularning optimallashgan ko’rinishi hisoblanadi.

Alfa-beta kesish algoritmi minimaks algoritmi daraxtida baholangan tugunlarni qisqartirish uchun ishlatiladigan qidiruv algoritmi bo’lib, u antagonik o’yinlar va mashina o’yinlari uchun ishlatiladi. Bu algoritmning asl ma’nosi shundaki, qidiruv daraxtning baholanayotgan tarmog’i baho ffunksiyasi har qanday holda ham oldingi tarmoqdagidan yomon bo’lsa u holda qidiruv to’xtatiladi.

Bu algoritm mustaqil ravishda bir necha olimlar tomonidan bir-biridan behabar holda yaratilgan. Uni ilk marta “Aproksimatsiya” deb nomlashgan. 1956-yilda Makkarti ismli olim Darmurd seminarida bu g’oya haqida aytib o’tgan. 1963-yilda Aleksandr Brudno mustaqil ravishda algoritmni yaratdi va uni ommaga havola etdgan. 1975-yilda esa Donald Kunt va Ronald Mur algoritmga “beta”-kesishishni qo’shib mukammallashtirishdi.

• 
  Dastlabki qo'ng'iroq A dan boshlanadi. Bu erda alfa qiymati-INFINITY va beta qiymati +INFINITY. Bu qiymatlar daraxtdagi keyingi tugunlarga tushadi. A da maximizer b va C ning max ni tanlashi kerak, shuning uchun a avval b chaqiradi
  
•