Qidiruv orqali masalalarni yechish. Ma'ruza

Reja: Eniga qidirish usuli Chuqurlikga qidirish A* qidiruv Ushbu ma’ruzada maqsadga yo’naltirilgan agent hisoblangan masalalarni echadigan agentlar qarab chiqiladi. Bunday agentlar kutilgan natijaga erishish uchun qanday amal bajarish kerakligini aniqlaydi, amallar ketma-ketligini belgilaydi. Agentlar masala echimini ma’lum bir algoritmlar orqali qidiradi. Bunday algorimtlar ikki guruhga bo’linadi: axborotli qidirish va axborotsiz qidirish. Har bir agent o’zining unumdorlik ko’rsatkichlarini maksimallashtirish xususiyatiga ega. Qandaydir bir agent Arad shahrida joylashgan, u turist sifatida ta’tilni o’tkazyapti. Agentning unumdorlik ko’rsatkichlariga bir necha komponentlar kiradi: oftobda toblanishni yaxshilash, rumin tili bo’yicha bilimini yaxshilash, diqqatga sazovor joylarni ko’rish, tungi hayot bilan zavqlanish, kutilmagan hodisalarda saqlanish va hokazo. Bu masalani echish juda murakkab hisoblanadi. Chunki bularni o’rinlash uchun ko’pchilik kompromisslarni hisobga olish zarur. Bundan tashqari agentda qaytarib bo’lmaydigan Buxarestga ertaga uchish uchun bilet bor. Bu holatda agent Buxarestga borish maqsadiga qarab harakat qiladi. Maqsad harakatlarni belgilab beradi, oraliq bosqichlarni cheklashi mumkin. Masalani echishdagi birinchi bosqich bu joriy holat va unumdorlik ko’rsatkichlarini hisobga olib maqsadni aniqlab olish. Maqsadni agent muhit holati ko’pligi sifatida qaraydi. Agentning vazifasi maqsad holatiga olib boruvchi amallar ketma-ketligini aniqlash. Bundan oldin agent u qaysi amal va holatni qarab chiqishini aniqlab oladi. Masalani aniqlab olish bu biror bir maqsadni hisobga olib qaysi amal va holatni qarab chiqishni aniqlab olish jarayoni. Bu masalada biz agent bir shahardan boshqa shaharga avtomobilda harakat qiladi deb hisoblaymiz. Demak agent avtomobilda Arad shahridan Buxarest shahriga borishni o’z oldiga maqsad qilib qo’ydi. Agentning har bir shaharda bo’lishini bir holat deb qaraymiz. Arad shahridan chiquvchi uchta yo’l bo’lib, ular Sibiu, Timishoaru va Zerind shaharlariga olib boradi. Bu shaharlardan birortasi ham maqsad shahri bo’lib hisoblanmaydi. Bundan tashqari agent qaysi shahar Buxarestga olib borishini ham bilmaydi. Boshqacha aytganda agent eng yaxshi echimni bilmaydi, chunki unda holatlar haqidi etarlicha ma’lumot yo’q. Agar agent holatlar haqida etarlicha ma’lumotga ega bo’lmasa u berk yo’lga borib qolishi mumkin. Bu holatda eng yaxshi echim tasodifiy yo’lni tanlash. Lekin agentda Ruminiya xaritasi bor deb hisoblaymiz. Xarita orqali agent o’zining duch kelishi mumkin bo’lgan va o’rinlashi mumkin bo’lgan holatlar haqida ma’lumotga ega bo’ladi. Agent bu ma’lumotlardan foydalanishi mumkin. Xaritada Arad shahridan Buxarestgacha olib boruvchi yo’lni aniqlab, agent o’z maqsadiga erishi mumkin.

Qidiruv orqali masalalarni yechish

Yuqorida qarab chiqilgan jarayon qidirish deb ataladi. Xohlagan qidirish algoritmi kirish ma’lumotlarini oladi va echimni amallar ketma-ketligi ko’rinishida qaytaradi. Echim topilgandan keyin amallar bajariladi. Bu faoliyat o’rinlash bosqichida amalga oshiriladi. Bundan «aniqlash, topish, o’rinlash» prinsipidagi oddiy agentni yaratish mumkin, 1.1 listingda ko’rsatilgan. 2.1-listing. Masala yechadigan oddiy agent function Simple-Problem-Solving-Agent(percept) returns action inputs: percept static: seq, state, goal, problem state  ß Update-State (state, percept) if seq bo’lsh bo’lsa then do goal ß Formulate-Goal(state) problem ß Formulate-Problem(state, goal) seq ß Search (problem) action ß First(seg) seg <— Rest (seg) return action bu erda, percept – qabul qilish natijasi, seq – amallar ketma-ketligi, state – joriy holat, goal – maqsad, problem – masala.

Masalaning to'rtta komponenti

Masala to’rtta komponent orqali ta’riflanishi mumkin: Boshlang’ich holat, bunda agent ishga tushadi. Masalan Ruminiya masalasidagi agentning boshlag’ich holati bu uning Arad shahrida joylashganligi, In(Arad). Agentning mumkin bo’lgan amallarini ta’riflash, vorisni aniqlash funksiyasi. Agar aniq holat x belgilangan bo’lsa, Successor-Fn(x) funksiyasi bir qancha taxlangan juftliklarni <action, successor> qaytaradi. action bu x holatidan mumkin bo’lgan amal, successor bu shu amal bajarilgandagi x ning holati. Masalan In(Arad) holatidan funksiya quyidagi qiymatlarni qaytardi: {<Go(Sibiu), In(Sibiu)>, <Go(Timisoara), In(Timisoara)>, <Go(Zerind), In(Zerind)>} Boshlang’ich holat va vorisni aniqlash funksiyasi birgalikda joriy masalaning holatlar fazosini belgilaydi. Fazo grafni shakllantiradi, unda uzellar bu holatlar, yoylar esa amallarni ko’rsatadi (2.1-rasm). Maqsadni tekshirish, joriy holat maqsad holati ekanligi tekshiriladi. Ayrim masalalarda maqsad holati bir necha bo’lishi mumkin. Ruminiya masalasida maqsad holati bu In(Bucharest). Yo’l narxi funksiyasi har bir yo’lning narxini sonli qiymat ko’rinishida qaytaradi. Agent yo’l narxining o’zining unumdorlik ko’rsatkichlariga mosligiga qarab amalni tanlaydi. Ruminiya masalasida yo’l narxi bu shaharlar o’rtasidagi masofa.. Masala qo’yilgandan so’ng uning echimi qidiriladi. Qidiruv holatlar fazosida amalga oshiriladi. Boshlang’ich holat va vorisni aniqlash funksiyasi echimlar daraxtini tashkil qiladi.

1 (binary/octet-stream)

Caption: : 2.1-rasm. Ruminiya masalasidagi holatlar fazosi grafi.

Eniga qidirish usuli (BFS)

Axborotsiz qidirish usullaridan biri hisoblangan eniga qidirish usuli eng oddiy usul bo’lib hisoblanadi.  Bu usulda eng birinchi ildiz uzel qarab chiqiladi. Keyin esa uning voris uzellari qarab chiqiladi. Undan keyin har voris uzelning voris uzellari qarab chiqiladi va qidiruv jarayoni shu ketma-ketlikda davom ettiriladi. Ya’ni echmilar daraxtida qidirish echimlar daraxti darajalari bo’yicha amalga oshiriladi.          Eniga qidirish usuli Tree-Search prosedurasini chaqirish orqali amalga oshiriladi, unda qidirish FIFO (First-In-First-Out) ketma-ketligida qidiruv amalga oshiriladi. 2.3-rasmda binar daraxtida qidirish bosqichlari ko’rsatilgan. 2.3-rasmda ko’rsatilgan ketma-ketlikda qidiruv bajariladi. Eng birinchi bo’lib 0 ildiz uzel qaralaid, keyin esa 1, 2, 3, … ko’rinishda davom ettiriladi. Eniga qidirish usulini to’rtta kriteriya bo’yicha baholaymiz. Qidiruv to’liq hisoblanadi, chunki maqsad uzeli daraxtning oxirgi d chuqurligida joylashgan. Demak qidiruv davomida bu uzel albatta topiladi. Demak, har bir holat b vorislarga ega. Bu daraxtning ildizi birinchi darajada b uzellarni shakllantiradi. Ularning har biri yana b uzelni shakllantiradi, b2. Uchinchi darajada b3 uzel bor. Maqsad uzeli d chuqurlikda joylashgan. Va shu ko’rinishda davom ettirilsa uzellar sonini quyidagicha hisoblash mumkin. b+b2+b3+…+bd+(bd+1-b)=O(bd+1) Har bir qarab chiqilgan uzel xotirada saqlanishi shart, sababi echim topilmagan holatda qidirish shu uzellarning voris uzeliga o’tishi kerak. Shu sababli vaqt muammosi bilan bir xil xotira muammosini ham e’tiborga olish lozim.

2 (binary/octet-stream)

Caption: : 2.3-rasm. Eniga qidirish algoritmi

Chuqurlikga qidirish

Chuqurlikga qidirish algoritmida birinchi uzeldan boshlab uning eng chuqur uzeligacha qidiriuv davom ettiriladi. Qidiruv asta-sekin qidiruv daraxtidagi eng chuqur darajasigacha davom ettiriladi. Oxirgi uzel qarab chiqilgandan so’ng bir daraja orqaga qaytiladi va keyingi uzeldan qidiruv davom ettiriladi. 2.4-rasmda qidiruv daraxti keltirilgan. Bunda qidiruv ildiz uzel 0 dan boshlanadi. Keyin uning vorisi 1 uzel qarab chiqiladi. Agar echim topilmasa qidiruv 1 uzelning vorisi 3 uzel qarab chiqiladi. 3 chi uzel daraxtdagi eng oxirgi uzel bo’lganligi sababli, bu yo’nalishda qidiruv to’xtatiladi va bir daraja yuqoriga ko’tariladi. 4 uzel qarab chiqiladi. Keyin esa 2, 5, 6 uzellar qarab chiqiladi. Bu algoritm LIFO (Last In First Out) usulida ishlaydi. Bu vektor stek deb ataladi. Ko’pincha bu algoritm rekursiya orqali amalga oshiriladi.

3 (binary/octet-stream)

Caption: : 2.4-rasm. Chuqurlikga qidirish algoritmi

Chuqurligi chegaralangan qidiruv

Masalalarda cheksiz daraxt muammosi ushrashi mumkin. Bu muammo cheksiz qidiruvga olib kelishi mumkin. Muammoning echimi bu qidiruv daraxtida chuqurlikni l cheklab qo’yish. Qidiruv shu l chuqurligigacha davom ettiriladi va shu daraja daraxtning eng oxirgi darajasi deb hisoblanadi. Bu usul chuqurligi chegaralangan qidiruv deb ataladi. Agar masalada l<d bo’lsa, u holda echim topilmaydi. Shu sababli l ning qiymatini l>d ifodasini hisobga olib belgilash lozim. Rasmdagi qidiruv daraxtida l=2, ya’ni ikkinchi darajada cheklov qo’yilgan. Qidiruv ikkinchi darajagacha amalga oshiriladi.

4 (binary/octet-stream)

Caption: : 2.5 – rasm. Chuqurligi cheklangan qidiruv

Iterativ chuqurlashadigan qidirish usuli

Iterativ chuqurlashadigan qidirish usuli chuqurligi chegaralangan qidirish usuliga o’xshash bo’lib hisoblanadi. Bunda chegara l ning qiymati sekin asta orttirilib boriladi, dastlab l=0 bo’ladi, shu daraja qarab chiqilgandan so’ng l ning qiymati orttiriladi, l=1, l=2, l=3, …. Bu jarayon maqsad uzeli topilgancha davom ettiriladi. Bu algoritm psevdokodi 2.2 listingda ko’rsatilgan.   2.2 – listing. Iterativ chuqurlashadigan chuqurlikga qidirish usuli function Iterative-Deepening-Search(problem) returns result yoki failure inputs: problem, zadacha for depth ß 0 to ꝏ do result ß Depth-Limited-Search(problem, depth) if result ≠ cutoff then return result            Iterativ chuqurlashadigan qidirish usuli eniga qidirish va chuqurlikga qidirish usullarining afzalliklarini o’z ichiga olgan. Chuqurlikga qidirish usuliga o’xshash bu usul hotirada katta talab qo’ymaydi. Eniga qidirish usuliga o’xshash to’liq bo’lib hisoblanadi. 2.6-rasmda bu usulning to’rt iterasiyadagi amali ko’rsatilgan.

5 (binary/octet-stream)

Caption: : 2.5 – rasm. Iterativ chuqurlashadigan qidirish usuli.

Ikki tarafli qidirish usuli

Ikki tarafli qidirish usulida bir vaqtda ikkita qidiruv amalga oshiriladi, boshlang’ich holatda to’g’ri yo’nalishda va maqsad holatidan teskari yo’nalishda. Ikki yo’nalish markazda uchrashganda qidiruv to’xtatiladi (2.6-rasm). bd ga qaraganda bd/2+bd/2 qiymati kichik, ya’ni kki kichik doiraning maydoni bir katta doira maydonidan kichik. Ikki tarafli qidiruvda ikki jarayonda ham qaralayotgan uzel ikkinchi jarayonning qidiruv daraxtiga tegishliligi tekshirilib boriladi. Agar tekshirish natijasi ijobiy bo’lsa echim topilgan hisoblanadi. Masalan d=6 bo’lsa, u holda ikki jarayon uchinchi darajada uchrashadi.

6 (binary/octet-stream)

Caption: : 2.6 – rasm. Ikki tarafli qidirish usuli

A* qidiruv

Best First Search qidiruv usulining eng taniqli turi bu A* qidiruv usuli. Unda uzellar baholash quyidagicha hisoblanadi: f(n) = g(n) + h(n) Unda joriy uzel narxi g(n) va joriy uzeldan maqsadgacha bo’lga narx h(n) summasi hisoblanadi. g(n) funksiyasi boshlang’ich uzeldan boshlab joriy uzelgacha bo’lgan narxni hisoblab boradi. h(n) funksiyasi esa joriy uzeldan maqsad uzeligacha bo’lgan narxni hisoblaydigan evristik funksiya. Narx qiymati kichik echimni topish uchun avval g(n)+h(n) qiymatini tekshirib ko’rish lozim. Agar h(n) evristik funksiyasi talab to’liq javob beradigan bo’lsa u holda A* qidiruv usuli to’liq va optimal bo’lib hisoblanadi. Agar bu usul Tree-Search algoritmi bilan birgalikda qo’llanilsa, uning optimalligini tekshirish murakkab hisoblanmaydi. Agar h(n) mumkin bo’lgan evristik funksiya bo’lsa A* usuli optimal bo’lib hisoblanadi. 2.8-rasmda A* usulining qidirish jarayoni ko’rsatilgan. Bunda evristik funksiya sifatida hSLD olingan. Masalan Arad shahrining bahosi 366=0+366. Bu erda 366 qiymati hSLD funksiyasining qiymati, 0 esa boshlang’ich uzeldan joriy uzelgacha bosib o’tilgan masofa. Sibiu shahrida esa g(n) = 140.

7 (binary/octet-stream)

Nazorat savollari:

Axborotli va axborotsiz qidirish usullarining qanday farqlari bor? Qidiruv daraxtida qidirish degani nima? Masalaning to’rtta komponentni ta’riflang. Vorisni aniqlash funksiyasi qanday ishlaydi? Eniga qidirish usulini tushuntiring. Chuqurlikka qidirish usulini tushuntiring. Iterativ chuqurlashadigan qidiruv usulini tushuntiring. Eniga qidirish usuli qaysi prinsipda amalga oshiriladi? Chuqurlikga qidirish usuli qaysi prinsipda amalga oshiriladi? A* qidirish usulini tushuntiring.

• Qidiruv orqali masalalarni yechish. Flesh karta