Saidakbar Umarov 8 -amaliy ish. Mavzu: qidiruv beam search algoritmi

610-17 Saidakbar Umarov

8 -Amaliy ish. MAVZU: QIDIRUV BEAM SEARCH ALGORITMI

Ishdan maqsad: Bu laboratoriya ishi orqali talabalarda qidiruv Beam search algoritmi haqida ma’lumot hosil qilishdir.

Uslubiy kо‘rsatmalar: Qidiruv Beamsearch algoritmini chuqurlik bо‘ylab tarqalish deb atashimiz mumkin. Bu atama birinchi marta Raj Reddy tomonidan Carnegi Mllon Universitetida ishlatilgan. Bu qidiruvda har bir usuldan bir birigia о‘tish imkoniyatlari mavjud bо‘ladi. Beam search eng yaxshi birinchi qidiruv algoritmlari bо‘lib xotiradan joy olishi qisqartirib optimallashtiradi. Beam search qidiruv daraxtidan qidirishda foydalaniladi. Uni kо‘plab mashina ishini boshqarishda foydalanamiz. Bu algoritmdan foydalanishda biz natijalarni tezda olamiz, chunki natijalar ham о‘zaro bir biriga bog‘langan bо‘ladi. Beam searchni nurli qidiruv deb tarjima qilamiz. Nurli qidiruv optimallashtirilgan “birinchisining eng yaxshisi” algoritmidir. Orginaliga о‘xshab u har bir tugunni evristik baholash funksiyasidan foydalanadi. Biroq, faqat har bir о‘tishdagi birinchi eng kо‘p istiqbolli m tugun baholanadi. Bu yerda m – fiksirlangan son.

Beam search qidiruv daraxtini quraishda breadth-first search dan foydalanadi. Daraxtning har bir darajasida u holatlarni evristik bahoning o’sish tartibida saralab joriy darajadagi barcha holat davomchilarini ishlab chiqadi. Shunga qaramay, u β – oldindan belgilangan har bir darajadagi eng yaxshi holat nomerini saqlab qoyadi (nur kengligi deb nomlanadi). Faqat shu holatlar keyingisini kengaytiradi. Eng kata nur kengligi, eng kam holat kesib tashlanadi. “Beam search” atamasini birinchi bo’lib Carnegi Mellon Universitetidan Raj Reddy ishlatgan.

c. Eng yaxshi tarjimani tanlash uchun har bir qism qо‘zg‘atiladi va turli xil tarjima yo’llari bilan sо‘zlar paydo bо‘ladi. Ularning gap tuzilishi о‘rniga eng yaxshi tarjima qо‘shimchasi saqlanadi. Tarjimon keyin berilgan kriteria о‘rniga tarjimalarga baho beradi. Beam search birinchi marta 1976-yil Carnegi Mellon Universitetida Harpy nutqni tanish tizimida qо‘llanilgan.

Beam search quyidagilarda ishlatiladi: Integratsiyalashgan dizayn zanjiri Factory-floor layout

Ishni rejalashtirish Tarmoqni optimizatsiyalash

Transport yo’nalishini aniqlash Sayohat uyushtirish muammolarida Mashinali tarijama qilishda

Nta qirolichalar masalasi. NxN katakli doskaga Nta qirolichani qator yoki ustun va yoki dioganal bо‘yicha 2tadan joylashtirmasdan qо‘yamiz.

1. 
   rasm. Shaxmat oynasi
   

О‘sish tartibidagi kesishuvchi raqamlar bо‘ylab qirolichalarni harakatlantiramiz. Bunda Nta qirolicha masalasi kata N uchun tezda yechiladi.

Beam Search algoritmi

OPEN = {Boshlang‘ich holatni berish} While OPEN bо‘sh emas bо‘lsa, bajarilsin

OPENdan eng yaxshi tugunni o’chirish

Agar n maqsadli holat bо‘lsa, yo’lni nga qaytarish va yo’lni qaytarish N ning vorislarini yaratish

Har bir vorisni baholash, uni OPENga qо‘shish, va uning otasini yozib olish Agar OPEN > ß bо‘lsa, eng yaxshi ß tugunlarni olish va qolganlarini OPENdan olib tashlash.

X-o о‘yini - 3x3 kvadrat kataklardagi 2ta raqiblar orasidagi mantiqiy о‘yin. Bitta о‘yinchi x lar bilan ikkinchisi o lar bilan о‘ynaydi. An’anaviy xitoy о‘yinida qora va oq toshlardan foydalaniladi. Kim о‘z belgilari bilan kataklarni gorizontal yoki vertical va yoki x bо‘yicha tо‘ldirsa yutgan hisoblanadi. Har bir tomonda durang qiluvchi yoki raqibini yutishga imkon beruvchi umumiy ma’lum algoritmlar mavjud. Bu о‘yinni kompyuterda bajarish uchun mini-maks usuli bilan mos keluvchi о‘yin holatlari daraxti quriladi. Bunday daraxtning tugunlari soni 255168taga teng. Bu son barcha mumkin bо‘lgan birinchi qadamdagi variantlar soni – 9 taning yig‘indisidan olinadi. 2-qadamda 9taning har biri uchun 8 ta variant bо‘ladi. 3-qadamda 72ta variantning har biri uchun 7ta variant bо‘ladi va hk.

Hamma natijalar ham yaxshi ya’ni kutilganidek bо‘lmasligi mumkin. Masalan men tanlab olgan x o о‘yinida ham doim g‘olib bо‘lavaermaydi . Demak doim muvaffaqiyatli natija chiqmasligi mumkin.

“x o ” о‘yini uchun kombinatsiyalarning ba’zi birlani kо‘rib chiqamiz.

2.