Mavzu: Qidiruv Beam search algoritmi. Ishdan maqsad

8.1.rasm. Shaxmat oynasi 

O’sish  tartibidagi  kesishuvchi  raqamlar  bo’ylab  qirolichalarni  harakatlantiramiz. 

Bunda Nta qirolicha masalasi kata N uchun tezda yechiladi. 

Beam Search algoritmi 

OPEN = {Boshlang’ich holatni berish} 

While OPEN bo’sh emas bo’lsa, bajarilsin 

OPENdan eng yaxshi tugunni o’chirish 

Agar n maqsadli holat bo’lsa, yo’lni nga qaytarish va yo’lni qaytarish 

N ning vorislarini yaratish 

Har bir vorisni baholash, uni OPENga qo’shish, va uning otasini yozib olish 

Agar  OPEN  >  ß  bo’lsa,  eng  yaxshi  ß  tugunlarni  olish  va  qolganlarini  OPENdan 

olib tashlash. 

X-o o’yini  - 3x3 kvadrat kataklardagi 2ta raqiblar orasidagi  mantiqiy  o’yin.  Bitta 

o’yinchi x lar bilan ikkinchisi o lar bilan o’ynaydi. An’anaviy xitoy o’yinida qora va oq 

toshlardan  foydalaniladi.  Kim  o’z  belgilari  bilan  kataklarni  gorizontal  yoki  vertical  va 

yoki  x  bo’yicha  to’ldirsa  yutgan  hisoblanadi.  Har  bir  tomonda  durang  qiluvchi  yoki 

raqibini  yutishga  imkon  beruvchi  umumiy  ma’lum  algoritmlar  mavjud.    Bu  o’yinni 

---

kompyuterda  bajarish  uchun  mini-maks  usuli  bilan  mos  keluvchi  o’yin  holatlari  daraxti 

quriladi.  Bunday  daraxtning  tugunlari  soni  255168taga  teng.  Bu  son  barcha  mumkin 

bo’lgan  birinchi qadamdagi  variantlar  soni  –  9  taning  yig’indisidan  olinadi.  2-qadamda 

9taning har biri uchun 8 ta variant bo’ladi. 3-qadamda 72ta variantning har biri uchun 7ta 

variant bo’ladi va hk. 

Hamma  natijalar  ham  yaxshi  ya`ni  kutilganidek  bo`lmasligi  mumkin  .  Masalan 

men  tanlab  olgan  x  o  o`yinida  ham  doim  g`olib  bo`lavaermaydi  .  Demak  doim 

muvaffaqiyatli natija chiqmasligi mumkin . 

“x o ” o`yini uchun kombinatsiyalarning ba`zi birlani ko`rib chiqamiz.