logo
  1. Главная страница
  2. Рефераты
  3. Общий
  4. Sun’iy intellekt masalalarini holatlar fazosida namoyish etish

Sun’iy intellekt masalalarini holatlar fazosida namoyish etish

Загружено в:

19.11.2024

Скачано:

0

Размер:

1636.1259765625 KB
Скачать
Sun’iy intellekt masalalarini holatlar fazosida namoyish etish Reja: 1. Sun’iy intellekt tizimlarining masalalari. 2. Sun’iy intellekt masalalarini echishning umumiy uslublari. 3. Sun’iy intellekt masalalarini echishning usullari. 3.1. Predmet soha xususiyatlari va masalalarni echish usullarini sinflash. 3.2. Holatlar fazosida echimni izlash. 3.2.1. Holatlar fazosida echimni izlash usullari. 3.2.2. Chuqurligi bo’yicha izlash strategiyasi. 3.2.3. Kengligi bo’yicha izlash strategiyasi. 3.2.4. Evristikli izlash. 3.2.4.1. А * algoritmi. Tayanch iboralar: Sun’iy intellekt (Artificial Intelligence), statik va dinamik masalalar (static and dynamic problems), bilimlarni namoyish etish (knowledge representation), interpretatsiya (interpretation), diagnostika (diagnostics), bashoratlash (prediction), rejalashtirish (planning), loyihalash (design), o’rganisg (training), boshqarish (control), vektorlar (vectors), matritsalar (matrix), graflar (counts), operatorlar (operators), maqsadli holat (targetstate), tupikli tugunlar (deadlock tops), holatlar fazosida echimni izlash (statespace search), birma-bir tekshirish (exhaustive search), kengligi bo’yicha birma-bir tekshirish (toomuc hindepth), evristik algoritm (heuristic algorithm), echimlar daraxti (decision tree), iyerarxikli va alternativli fazolar (hierarchical and alternative space), ochiq va yopiq tugunlar (opening and closing thetopof), marshrut (route), tartiblangan birma-bir tekshirish algoritmi (algorithm ordered strumming). 1. Sun’iy intellekt tizimlarining masalalari Sun’iy intellekt tizim(SIT)larining masalalari turli predmet sohalarni qamrab olgan bo’lib, ular orasida bizness, ishlab chiqarish, tibbiyot, loyihalash va boshqarish tizimlari kabilar ilg’or sohalar hisoblanadi. Keltirilgan masalalarni umumiy xususiyatlari bo’yicha quyidagicha sinflash mumkin [1-4, 8-10]. 1) Tahlil va sintez qilish masalalari. Tahlil qilish masalasida obyekt modeli beriladi va ushbu modelning noma’lum parametrlarini aniqlash talab etiladi. Sintez qilish masalasida obyekt modelining noma’lum xarakteristikalarini qanoatlantiruvchi shartlar beriladi va ushbu obyektning modelni qurish talab etiladi. 2) Statikli va dinamikli masalalar. Statikli masalalarda echimlarni hosil qilish jarayonida vaqt hisobga olinmaydi va olam haqidagi bilimlar o’zgarmas deb qaraladi. Dinamikli masalalarda esa yuqoridagining aksi qaraladi. 3 ) Bilimlarni namoyish etish ucun umumiy tasdiqlardan foydalanish . Bunda foydalaniladigan umumiy tasdiqlarda aniqlanadigan aniq obyektlarga ochiq havolalar berilmaydi. 1 4) Xususiy havolalardan foydalanish. Bunda aniq obyektlarga havolalarni o’z ichiga oluvchi xususiy havolalardan foydalaniladi. Echiladigan masalalarni quyidagi tiplarga ajratish mumkin: • interpretatsiyalash – ma’lumotlarning ma’nosini aniqlash jarayoni; • tashhislash –obyektlarni anglash yoki tizimning nosozligini aniqlash; • monitorihglash -haqiqiy vaqt oralig’ida ma’lumotlarni uzluksiz izohlash va ba’zi parametrlarning etarli chegaralardan chiqishi haqida signallar berish; • bashoratlash -oldingi va hozirgi modellar asosida obyektlar harakatining rejasini qurish; • rejalashtirish -ba’zi funksiyalarni bajarish qobilyatiga ega obyektlarning harakat rejasini qurish; • loyihalash -oldin mavjud bo’lmagan obyektni yaratish va oldindan aniqlangan xossalar asosida obyektlarni hosil qilishni tasniflashga tayyorlash; • o’rganish -obyektlar haqidagi ma’lumotlarni o’rganish uslubiyoti; • boshqarish -tizimlar funksiyasi bo’lib, tizimlarning qandaydir rejimda faollashuvini qo’llab quvvatlash yoki qandaydir berilgan vazifani bararishga mo’ljallangan murakkab tizimlarning harakatini boshqarish; • qaror qabul qilishni qo’llab-quvvatlash- protseduralar majmuasi bo’lib, u qaror qabul qilish uchun zarur ma’lumotlar bilan ta’minlangan bo’ladi va qaror qabul qilish jarayoni uchun ko’rsatmalar beradi. Masalalarni namoyish etish uslubini tanlashda odatda ikkita holat e’tiborga olinadi [1, 5-7]: -masalalarni namoyish etish haqiqiylikni etarli aniq modellashtirishi zarur ; - masalalarni namoyish etish uslublari shunday bo’lishi kerakki, ushbu masalani echish EHM (echuvchi) uchun qulay bo’lsin . 2. Sun’iy intellekt masalalarini echishning umumiy uslublari Masalani echish jarayoni qoidaga ko’ra ikki pog’onadan iborat bo’ladi: masalani namoyish etish va echimni izlash. Mashina yordamida masalalarni namoyish etish shakllarini izlash masalasi qiyin formallashgan ijodiy jarayon hisoblanadi. Shuning uchun masalalarni namoyish etishda qo'llaniladigan ba’zi shakllarni quyidagich keltirish mumkin [1]: 1) Holatlar fazosi(HF)da namoyish etish; 2) Masalalarni masalalar ostilariga keltirish yo’li bilan namoyish etish; 3) Teoremalar ko’rinishida namoyish etish; 4) Kombinatsiyali namoyish etish. Masalalarning holatini tavsiflashning turli shakllari mavjud. Xususan, masalalarni qatorlar , vektorlar, matritsalar va graflar ko’rinishda tavsiflash mumkin HFda echimlarni izlash protseduralari boshlang’ich holatni maqsad funksiyaga aylantiruvchi operatorlar ketma-ketligini aniqlashga asoslanadi. Daraxt deb shunday yo’naltirilgan grafga aytiladiki , bunda uning ildizidan tashqari har bir tuguniga faqat bitta yoy kiradi. Shunday qilib, daraxtda ildizdan tashqari har bir tiguni bitta yoyning oxiri va 2 A И В Е F G C D H I И 6.1-rasm.Masalalarni reduksiyalash daraxti. G FE H IDA K B C 6.2-rasm. Almashtirilgan reduksiyalash daraxti. кцииbitta yoki bir nechta yoyning boshi bo’ladi. Daraxtda V tugundan Vi tugunlar hosil bo’ladi. Bunda V - bosh tugun, Vi - ichki tugunlar deb nomlanadi. Bosh tugun (ildiz) 0-pog’onali, ildizdan hosil bo’lgan tugunlar 1-pog’onali, 2-pog’onali va h.k. k-pog’onali bo’lishi mumkin. Masalalar ostilarining o’zaro aloqasi strukturasi ikki tipda bo’lishi mumkin: VA- strukturalar va VA-YOKI -strukturalar. VA-strukturalarda asosiy masalani echishda barcha masalalar ostilarini echish talab etiladi. VA-YOKI - strukturalarda xususiy masalalar guruhlarga bo’linadi va bu guruhlar bir-biri bilan YOKI munosabati yordamida , guruhlar ichidagilar esa bir-biri bilan VA munosabati yordamida bog’lanadi. Bunday holda boshlang’ich masalani echish uchun, faqat qandaydir bitta guruhga taalluqli barcha masalalar ostilarini echish etarli hisoblanadi. Masalalarni masalalar ostilariga keltirishni namoyish etishni tavsiflash uchun masalalarni reduksiya(tiklash)lash grafi deb nomlanuvchi grafdan foydalaniladi (6.1- rasm). Bunda grafning tugunlariga masalalar, yoylriga esa masalalarni reduksiyalash operatorlari mos qo’yiladi. Daraxt ildiziga boshlang’ich masala, 1-pog’ona tugunlarga esa boshlang’ich masaladan hosil qilingan masalalar ostilari mos qo’yiladi. A masala echiladi, agarda B va C masalalar yoki D masala echilsa. B masala echiladi, agarda E yoki F masala echilsa. C- masala echiladi, agarda G masala echilsa. D masala echiladi, agarda H va I masalalar echilsa. VA- strukturali tugunlarning bog’lanishini ko’rsatish uchun maxsus egri chiziqdan foydalaniladi. Agar daraxtda VA- strukturali bog’langan tugunlar bo’lsa, u holda ular uchun qo’shimcha tugunlar kiritiladi va ushbu tugunlar VA- strukturali tugunlarning bosh tugunlariga aylanadi ( рис . 6.2). 3 Bundan keyin faqat a lmashtirilgan reduksiyalash daraxtlarini qaraymiz . Masalalarni masalalar ostilariga keltirishni namoyish etishda boshlang’ich masalani bir nechta masalalar octilariga bo’lish qaraladi va bo’lingan har bir masala osti echimi boshlang’ich masalaning echimini beradi. Har bir masala ostilari oz navbatida yana masala ostilariga bo’linishi mumkin. Masala ostilariga bo’lish jarayoni nazariy jihatdan chegaralanmagan. Amaliy jihatdan masala ostilariga bo’lish jarayoni eng quyi pog’onadagi masala ostilari yordamida echimni olguncha davom ettiriladi. 3. Sun’iy intellekt masalalarini echishning usullari 3.1. Predmet soha xususiyatlari va masalalarni echish usullarini sinflash Masalalarni izlashga keltirishga asoslangan echish usullari masala echilayotgan predmet soha hususiyatlariga va masala echimiga foydalanuvchi tomonidan qo’yilgan talablarga bevosita bog’liq bo’ladi. Predmet soha xususiyatlari [1] : 1) Echim izlanayotgan fazo hajmi; 2) Sohaning vaqtli va fazoli o’zgarish darajasi (ststistik va dinamik sohalar); 3) Sohani tavsivlovchi modelning to’liqligi. Agar model to’liq bo’lmasa, u holda sohani tavsiflashda bir-birini to’ldiruvchi bir nechta modellardan foydalaniladi; 4) Echilayotgan masala haqidagi ma’lumotlarning aniqligi, ya’ni ma’lumotlarning aniqlik(hatolik) va to’liqlik(to’liqmaslik) darajasi. SITlari masalalarini echishda qo’llaniladigan mavjud usullarni quyidagicha sinflash mumkin [1, 8]: 1) Bir o’lchovli fazoda echimni izlash usullari – bu usullardan o’lchovi katta bo’lmagan sohalarda, modellar to’liq, ma’lumotlar aniq va to’liq bo’lganda foydalaniladi; 2) Ierarhik fazoda echimni izlash usullari - bu usullardan o’lchovi katta bo’lgan sohalarda echimlarni izlashda foydalaniladi; 3) Ma’lumotlar xatoli va t o’liqmas bo’lganda izlash usullari; 4) Bir nechta modellar yordamida izlash usullari - bu usullardan sohani tavsiflashda bitta modelning o’zi etarli bo’lmaganda foydalanilad. 3.2. Holatlar fazosida echimni izlash 3.2.1. Holatlar fazosida echimni izlash usullari HFda echimni izlash usullari odatda quyidagilarga bo’linadi [1-4]: 1) Chuqurligi bo’yicha izlash; 2) Kengligi bo’yicha izlash; 3) Evristikli izlash. HFda echimlarni izlash protseduralari boshlang’ich holatni maqsad funksiyaga aylantiruvchi operatorlar ketma-ketligini aniqlashga asoslanadi. Agar operatorlar ketma-ketligi bir nechta va optimallashtirish mezoni berilgan bo’lsa, u holda masala 4 A B C12 11 8 10 6.3-rasm.Marshrutni tanlash masalasi.D 55 6 A AC 10 15 15 11 108 6 3 8 11 5 11 112 10 8 6 8 14 12 10 3929 *36 *39 *36 * 29 * ADCBA ACDBA ACBDAABCDAABDC AABDC ABDC ABCD ACDB ADCB ADBCADC ADB ACDACBABCABD AB AD 6.4-rasm. Masalaning holatlar grafi.ushbu mezonni qanoqtlantiruvchi optimal operatorlar ketma-ketligini izlash masalasiga keltiriladi. HFda echimlarni izlash usullarini holatlar daraxti(grafi)dan foydalanib tavsivlash qulay hisoblanadi. Holatlar daraxtida echimlarni izlash masalasi daraxt ildizidan maqsadli holatga mos tugungacha bo’lgan yo’lni (optimalli, agar optimallik mezoni berilgan bo’lsa) topishga keltiriladi. Umumiy holda holatlar daraxtini (S0 ,F,G) uchlik ko’rinishda berish mumkin. Bu erda S0−¿ bitta elementdan iborat to’plam , F- operatorlar to’plami, G-maqsadli holatlar to’plami. Holatlar daraxtini qurish quyidagicha amalga oshiriladi: avvalo daraxt ildiziga(boshlang’ich holat) F dagi operatorlarni qo’llab 1-pog’onali tugunlar quriladi; Keyin, F dagi operatorlardan 1-pog’onali tugunlarga qo’llaniladiganlaridan foydalanib 2-pog’onali tugunlar quriladi va h.k. Ushbu protsedura maqsadli tugunni topguncha davom ettiriladi. Misol. Yuk tashuvchi robot A punktdan chiqib, (B, C, D) punktlarning har birida faqat bir martadan bo’lib, yana A punktga qaytib kelishi kerak. Punktlar orasidagi masofalar va marshrutlar sxemasi 6.3-rasmda keltirilgan. Marshrutni tanlash masalasi uchun HFda echimlarni izlash 6.4-rasmda keltirilgan [1]. 5 ADBCA Ushbu grafda boshlang’ich tugunga A holat mos keladi. A tugun AB, AC, AD holatlarga mos keluvchi uhta 1-pog’onali ichki tugunlarni hosil qiladi. 1-pog’onali AB, AC, AD ichki tugunlar 2-pog’onali ichki tugunlarni hosil qiladi va h.k. Grafda tugunlarning ochilish tartibi izlash strategiyasi deb ataladi. 3.2.2. Chuqurligi bo’yicha izlash strategiyasi Masalani echishning ba’zi strategiyalrini qarab chiqamiz. Graflarda hal qiluvchi yo’llarni qurishga yo’naltirilgan bir qator strategiyalar masalani echishda baholash funksiysi(BF)ga asoslanadi. BF grafning tugunlarida aniqlanadi va haqiqiy qiymatlarni qabul qiladi. Ixtiyoriy tugun uchun hosil qilingan BF qiymati ushbu tugundan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini aniqlaydi. Masalani BFni hisoblash asosida echish strategiysi evristik izlashning bir ko’rinishi hisoblanadi. BFni hisoblash asosida masalani echishning boshqa strategiyalariga chuqurligi bo’yicha izlash va kengligi bo’yicha izlash kiradi. Chuqurligi bo’yicha izlashda ixtiyoriy tugunning baholash funksiyasi qiymati ushbu tugundan boshlang’ich tugungacha bo’lgan masofaga to’g’ri proportsional bo’ladi. Kengligi bo’yicha izlashda bu bog’lanish teskari proportsional bo’ladi. Tugunlarning chuqurligi deganda tugunlarning pog’onalari tartib raqamiga teng bo’lgan son tushuniladi. Quyida masalani echishning boshqa strategiyalarini keltiramiz . 1) Shoxlar va chegaralar usuli. Qidirish jarayonida tugamagan yo’llardan eng qisqasi tanlab olinadi va bir qadamga uzaytiriladi. Hosil qilingan yangi tugamagan yo’llar (mazkur tugunda qancha shox bo’lsa ularning soni ham shuncha bo’ladi) eskilari bilan bir qatorda ko’riladi va yana ulardan eng qisqasi bir qadamga uzaytiriladi. Jarayon birinchi maqsadli tugunga yetguncha takrorlanadi va yechim saqlanadi. So’ngra qolgan tugamagan yo’llardan tugagan yo’lga nisbatan uzunroq yoki unga teng yo’llar olib tashlanadi, qolganlari esa xuddi shunday algoritm bo’yicha ularning uzunligi tugagan yo’lnikidan katta bo’lguncha uzaytiriladi. Natijada yo barcha tugamagan yo’llar olib tashlanadi, yo ular orasidan oldingi olingan yo’ldan qisqaroq bo’lgan yo’l shakllanadi. Oxirgi yo’l etalon hisoblanadi va h.k. 2) Murning qisqaroq yo’llarni topish algoritmi. Boshlang’ich X 0 tugun 0 soni bilan belgilanadi. Algoritm ishlash jarayonining boshlang’ich qadamida X i tugunning tarmoq tugunlar to’plami X(X i ) olingan bo’lsin. U holda oldin olingan barcha tugunlar undan o’chiriladi, qolganlari esa x i tugunning nishoniga qaraganda bir birlikka oshirilgan nishon bilan belgilanadi va ulardan X i ga tomon ko’rsatkichlar o’tkaziladi. Keyin hali ko’rsatkichlar manzili sifatida qatnashmaydigan belgilangan tugunlar to’plamida eng kichik nishonli tugun olinadi va u tugun uchun tarmoqlanuvchi tugunlar quriladi. Tugunlarni belgilab chiqish maqsadli tugun hosil qilinguncha takrorlanadi. Minimal qiymat bilan yo’lni aniqlashning Deykstr algoritmi o’zgaruvchan uzunlikdagi yoyni kiritish hisobiga Mur algoritmining umumlashmasi hisoblanadi. 6 3) Doran va Mitchining past baho bilan qidirish algoritmi . Qidirish bahosi optimal yechimning bahosiga nisbatan katta bo’lgan holda ishlatiladi. Bu holda Mur va Deykstr algoritmlaridagiday boshidan eng kam uzoqlikda joylashgan tugunni tanlash o’rniga maqsadgacha bo’lgan masofaning evristik bahosi eng kam bo’lgan tugun tanlanadi. Yaxshi baholashda yechimni tez hosil qilish mumkin, ammo yo’lning minimalligiga kafolat berilmaydi. 4) Xart, Nilson va Rafael algoritmi . Algoritmda ikkala kriteriya birlashtirilgan: g(x) tugungacha bo’lgan yo’l narxi (bahosi) va h(x) tugundan additiv baholanadigan f{x}=g(x)-h(x) funksiyagacha bo’lgan yo’l narxi hisoblanadi. h(x)<hp(x) shartda (bu yerda hp(x) maqsadgacha bo’lgan haqiqiy masofa) algoritm optimal yo’lni topishga kafolat beradi. Grafda yo’llarni qidirish algoritmlari qidirish yo’nalishi bilan ham farq qiladi. To’g’ri, teskari va ikki tomonga yo’nalgan qidirish usullari mavjud. To’g’ri izlash boshlang’ich holatdan ketadi va maqsad holat oshkormas holda berilganda qo’llaniladi. Teskari qidirish maqsadli holatdan ketadi va boshlang’ich holat oshkor berilmagan, maqsadli holat oshkor berilgan holda qo’llaniladi. Ikki tomonga yo’nalgan qidirish ikkita muammoning qoniqarli yechimini talab qiladi: qidirish yo’nalishining almashishi va «uchrashuv nuqta»sini optimallashtirish. Birinchi muammoni yechish kriteriyalardan biri qidirish «kengligi»ni ikkala yo’nalishda taqqoslashdan iborat. Qidirishni toraytiradigan yo’nalish tanlanadi. Ikkinchi muammoning yuzaga kelishiga sabab to’g’ri va teskari yo’llar ajralib ketishi mumkin va qidirish qancha tor bo’lsa uning ehtimoli ko’proq bo’ladi. 5) Cheng va Sleyg algoritmi . Ixtiyoriy VA/YOKI grafni har bir YOKI shoxi faqat oxirida VA tugunga ega maxsus YOKI grafga aylantirishga asoslangan. Ixtiyoriy VA/YOKI grafni muloxazalar mantiqining ixtiyoriy formulasiga aylantirish va keyin bu formulani diz’yunktiv normal shaklga keltirishdan foydalanib aylantirish amalga oshiriladi. Bunday aylantirish keyinchalik Xart, Nilson va Rafael algoritmlaridan foydalanishga imkon beradi. 6) Kalit operatorlar usuli. <A,B> masala berilgan bo’lsin va f operator albatta bu masalaning yechimiga kirishi ma’lum bo’lsin. Bunday operator kalit operator deb ataladi. f ni qo’llash uchun S holat kerak bo’lsin, uni qo’llash natijasi esa I(c) bo’lsin. U holda VA tugun uchta tarmoq tugunlarni keltirib chiqaradi: <A,C>, <C,f{c}> va <f(c),B>. Ulardan o’rtadagisi elementar masala hisoblanadi. <A,C> va <f(c),B> masalalar uchun ham kalit operatorlar tanlanadi va ko’rsatilgan reduksiyalash prosedurasi mumkin bo’lgunga qadar takrorlanadi. Natijada <A,B> boshlang’ich masala har biri HFda rejalashtirish usuli bilan yechiladigan masala ostilarining tartiblangan majmuiga ajratiladi. Kalit operatorlarni tanlashda alternativlar bo’lishi mumkin, shuning uchuun umumiy holda VA/YoKI graf sodir bo’ladi. Ko’pgina masalalarda kalit operatorni ajratishga erishilmaydi, faqatgina uni o’z ichiga oladigan to’plamni ko’rsatishga erishiladi. Bu holda <A,B> masala uchun A va V ning farqi hisoblanadi. Oxirgisi kalit operator bo’ladi. 7) Umumiy masala yechuvchi(UME)ni rejalashtirish usuli. UMEni rejalashtirish eng mashxur model sifatida paydo bo’lgan. U integral hisob, mantiqiy xulosa, grammatik tahlil va shu kabi boshqa masalalarni yechish tuchun ishlatilgan. 7 UME qidirishning ikkita asosiy prinsiplarini birlashtiradi: maqsadlarni va vositalarni tahlil qilish va masalani rekursiv yechish. Qidirishning har bir siklida UME uchta turdagi standart masalalarni qat’iy ketma-ketlikda yechadi: A obyektni B obyektga almashtirish, A va B orasidagi D farqni kamaytirish, f operatorni A obyektga qo’llaydi. 8) Mantiqiy xulosa asosida rejalashtirish. Bunday rejalashtirish holatlarni qandaydir mantiqiy hisobning to’g’ri qurilgan formulalari (TQF) ko’rinishida tavsiflashni; operatorlarni yoki TQF ko’rinishda yoki bir TQFni boshqasiga o’girish qoidalari ko’rinishida tavsiflashni taqozo etadi. Operatorlarni TQF ko’rinishida tasvirlash rejalashtirishning deduktiv usullarini yaratishga imkon beradi, operatorlarni o’girish qoidalari ko’rinishida tasvirlash esa deduktiv xulosa elementlari bilan rejalashtirish usullarini yaratishga imkon beradi. Chuqurligi bo’yicha izlash strategiyasini faqat tugunlar N = { n 1 , n 2 , …, n r } ro’yxati va yoylar L = { l 1 , l 2 , …, l s } ro’yxatidan iborat HFberilganda qo’llash maqsadga muvofiq. Bu erda l k = ( n ik , n jk ) qirralar bo’lib, n ik tugundan n jk tugunga yo’naltirilgan bo’ladi. Chuqurligi bo’yicha izlash algoritmining g’oyasi quyidagidan iborat: grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi.Undan keyin boshlang’ich tugundan chiqadigan bir qancha alternativ tugunlardan boshlang’ich tugundan eng uzoqda (uzunligi bo’yicha) joylashgan tugun tanlanadi. Navbatdagi tugunlararni tanlash, xuddi boshlang’ich tugundagidek, o’zidan oldingi tugunga nisbatan eng uzoqda joylashgan tugunni tanlash bilan davom ettiriladi. Tugunlarni tanlash algoritm bo’yicha maqsadga erishuvchi yo’lni topishgacha davom ettiriladi. Chuqurligi bo’yicha birma-bir izlash algoritmi [1, 5-7] . Tugunlarning chuqurligi - tugunlarning pog’onalari tartib raqamiga teng bo’lgan son bilan aniqlahadi. Chuqurligi bo’yicha birma-bir izlash algoritmida tugunlar orasidan eng katta chuqurlikga ega bo’lgan tugunlar ochiladi. Bunda bir xil chuqurlikga ega bo’lgan bir nechta tugunlardan bittasi tanlanadi. Bundan tashqari, odatda ba’zi mulohazalarga ko’ra tugunlarning chegaravuy chuqurliklari beriladi. Bu holda tugunlar orasidan, tygunlari chuqurliklari chegaraviy chuqurlikga teng bo’lganlari ochilmaydi. Shunday qilib, chuqurligi bo’yicha birma-bir izlash algoritmida tugunlar orasidan, tygunlar chuqurliklari chegaraviy chuqurlikdan kichchik bo’lgan tugunlar ochilmaydi. Chuqurligi bo’yicha birma-bir izlash algoritmini strukturalashgan holda qaraymiz: 1) Boshlang’ich tugunni «ochiq» royxatiga joylashtirish; 2) Agar «ochiq» royxati bo’sh bo’lsa, u holda 1-qadamga, aks holda 3-qadamga o’tiladi; 3) «Ochiq» royxatidan birinch tugunni olish va uni «yopiq» royxatiga o’tkazish va unga v nomni berish; 4) Agar v tugunning chuqurligi chegaraviy churlikga teng bo’lsa, u holda 2- qadamga o’tish, aks holda 5-qadamga o’tish; 8 5) v tugunni ochish. v tugunning barcha ichki tugunlarini «ochiq» royxatining boshiga joylashtirish va barcha ichki tugunlardan v tugunga keladigan ko’rsatkichlarni qurish; Agar v tugun ichki tugunlarga ega bo’lmasa, u holda 2- qadamga o’tish; 6) Agar ushbu tugunlardan birortasi maqsadli echimni hosil qilsa, u holda chiqishda echimni hosil qilish, aks holda 2-qadamga o’tish. Qaralgan algoritmda boshlang’ich tugun sifatida faqat bitta tugun qatnashadi. Agar boshlang’ich tugunlar bir nechta bo’lsa, u holda algoritmning 1-qadamidagi «ochiq» royxatiga barcha boshlang’ich tugunlar joylashtiriladi. Misol. Misol sifatida marshrutni tanlash masalasi uchun HFda echimlarni izlashda A, AD, ADC, ADCB, ADCBA optimal marshrutni keltirish mumkin ( 6.3, 6.4-rasmlar). Ta’kidlash lozimki, echimni c huqurligi bo’yicha izlashda eng chuqurlikga ega bo’lgan tugunlar bir nechta bo’lsa, u holda ular orasidan eng chapdagisi tanlanadi. Agar echimni izlash tupikli holatga kelib qolsa , ya’ni joriy tugun maqsadli echimga olib kelmasa va uning chuqurroq tugunlar bilan aloqasi bo’lmasa, u holda oldingi tugunga qaytiladi va ushbu tugundan echimni c huqurligi bo’yicha izlash davom ettiriladi. Misol. 6.5, а -rasmda HFda echimni c huqurligi bo’yicha izlashda qanday tugunlardan foydalanish kerakligi ko’rsatilgan. Bu erda a boshlang’ich, j va f oxirgi holatlarga mos keladi. Ajratilgan [ a , b , e , j ] va [ a , c , f ] yo’llar – bu topilgan hal qiluvchi yo’llar, [ a , c , f ] yo’l esa – hal qiluvchi qisqa yo’l hisoblanadi. HFda echimni c huqurligi bo’yicha izlash ko’p hollarda 6.5, а -rasmda ko’rsatilgandek yaxshi ishlaydi . Ba’zi hollarda u to'xtash holatiga ham tushib qolishi mumkin, masalan, sikllanish holatiga tushishi mumkin. Masalan 6.5, б –rasmda sikllanish holatlari [ d , h , d ] va [ b , e , i , b ] keltirilgan. 6.5-rasm. Chuqurligi bo’yicha izlash strategiyasi. 9a) b) 3.2.3. Kengligi bo’yicha izlash strategiyasi Kengligi bo’yicha izlash algoritmining g’oyasi quyidagidan iborat: grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi.Undan keyin boshlang’ich tugundan chiqadigan bir qancha alternativ tugunlardan boshlang’ich tugunga yaqin (uzunligi bo’yicha) joylashgan tugun tanlanadi. Navbatdagi tugunlararni tanlash, xuddi boshlang’ich tugundagidek, o’zidan oldingi tugunga nisbatan eng yaqin joylashgan tugunni tanlash bilan davom ettiriladi. Tugunlarni tanlash algoritm bo’yicha maqsadli echimga erishuvchi yo’lni topishgacha davom ettiriladi. Ta’kidlash lozimki , echimni kenglik bo’yicha izlashda boshlang’ich tugunga yaqin bo’lgan tugunlar bir nechta bo’lsa, u holda ular orasidan eng chapdagisi tanlanadi. Agar echimni izlash tupikli holatga kelib qolsa , ya’ni joriy tugun maqsadli echimga olib kelmasa va uning chuqurroq tugunlar bilan aloqasi bo’lmasa, u holda oldingi tugunga qaytiladi va ushbu tugundan echimni kengligi bo’yicha izlash davom ettiriladi. Misol. 6.6 -rasmda HFda echimni kengligi bo’yicha izlashda qanday tugunlardan foydalanish kerakligi ko’rsatilgan. Bu erda a boshlang’ich, j va f oxirgi holatlarga mos keladi. Ajratilgan [ a , c, f] – bu birinch topilgan hal qiluvchi yo’l bo’lib, u qisqa yo’l hisoblanadi. Ikkinchi hal qiluvchi yo’l [ a , b, e, j] bo’lib, u to’liq birma-bir tekshirish orqali hosil qilinadi. Misol. Qisqa yo’l haqudagi masala . Qisqa yo’l bilan grafning bir tugunidan boshqa tuguniga qanday borish mumkin? Ishlab chiqarishni boshqarish masalalarida: qisqa 6.6- rasm. Kengligi bo’yicha yo’l bilan (masalan, eng kam yoqilg’i va vaqt, izlash strategiyasi. ancha orzon) А punktdan Б punktga qanday borish mumkin? Bu masalani echish uchun yo’naltirilgan grafning boshlang’ich tugunidan oxirgi tugunigacha bo’lgan har bir yoyiga harakat vaqtini ifodalovchi son mos qo’yiladi (6.7-rasm). 6.7-rasm. Qisqa yo’l haqudagi masalauchun boshlang’ich qiymatlar. 105 2 1 21 2 4 6 5 7 1 4 3 3 5 3 Boshlang’ich qiymatlarni 6.1-jadval ko’rinishda ham berish mumkin. 6.1-jadval. Qisqa yo’l haqudagi masalauchun boshlang’ich qiymatlar. Yoyning boshi Yoyning oxiri Yo’ldagi vaqt 1 2 7 1 3 1 2 4 4 2 6 1 3 2 5 3 5 2 3 6 3 5 2 2 5 4 5 6 5 3 Talab qilinadi : qanday qisqa yo’l bilan 1–tugundan 4 – tugunga borish mumkin? Echimi . Quyidagi belgilashni kiritamiz : С ( Т ) – 1- tugundan T- tugungacha qisqa yo’lning uzunligi. Qaralayotgan masalada 1- tugundan 4- tugungacha bo’lgan С (4) qisqa yo’lni hisoblash talab etiladi. 6.7-rasmda va 6.1-jadvalda keltirilgan boshlang’ich qiymatlarni hisobga olsak, u holda 1-tugundan 3-tugunga uning uzunligi 1 ga teng bo’lgan faqat bitta yo’naltirilgan yoy chiqayapti, shuning uchun С (3)=1. Bundan tashqari, ko’rinib turibdiki С (1)=0. 4-tugunga uzunligi 4 ga teng bo’lgan 2-tugundan yoki uzunligi 5 ga teng bo’lgan 5-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli С (4) = min { С (2) + 4; С (5) + 5}. Demak, С (4) ni topish uchun avval С (2) va С (5) ni topish talab etiladi. 5-tugunga uzunligi 2 ga teng bo’lgan 3-tugundan yoki uzunligi 3 ga teng bo’lgan 6-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli С (5) = min { С (3) + 2; С (6) + 3}. Bilamizki, С (3) = 1. Shuning uchun С (5) = min {1+2; С (6) + 3}= min {3 ; С (6) + 3}. (6.1) 6-tugunga uzunligi 3 ga teng bo’lgan 3-tugundan yoki uzunligi 1 ga teng bo’lgan 2-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli С(6) = min { С(3)+3; С(2) +1}= min {4 ; С(2) +1}. (6.2) 2- tugunga uzunligi 7 ga teng bo ’ lgan 1- tugundan yoki uzunligi 5 ga teng bo ’ lgan 3- tugundan yoki uzunligi 2 ga teng bo ’ lgan 5- tugundan borish mumkin . Shuning uchun quyidagi munosabat o’rinli С(2) = min {С(1) + 7; С(3) + 5 ; С(5) + 2}. Bizga ma ’ lumki С(1) = 0, С(3) = 1, С(5) = 3. Shuning uchun С (2) = min {0 + 7; 1 + 5 ; 3 + 2} = 5. (6.3) (6.3) ni hisobga olsak С (6) = min {4; С (2) +1}= min {4 ; 5+1}=4. (6.4) (6.4) ni hisobga olsak, (6.1) dan С (5) = min {3; С (6) + 3}= min {3 ; 4+ 3}=3. 11 Endi С (4) ni topish mumkin: С (4) = min { С (2) + 4; С (5) + 5} = min {5 + 4; 3 + 5} = 8. (6.4) Shunday qilib, 1-tugundan 4-tugungacha bo’lgan qisqa yo’lning uzunligi 8. (6.5) munosabatdan ma’lumki, 4-tugunga 5-tugundan borish kerak. 5-tugunga 3- tugundan borish kerak. 3-yugunga esa faqat 1-tugundan birish mumkin. Demak, qisqa yo’l: 1 → 3 → 5 → 4 . 6.7-rasmda va 6.1-jadvalda keltirilgan boshlang’ich qiymatlar uchun qisqa yo’lni toppish masalasi to’liq echildi. 3.2.4. Evristikli izlash Churligi va kengligi bo’yicha izlash strategiyalari bosh tugundan chiquvchi yo’llar orasidan hal qiluvchi (qisqa, minimal) yo’lni izlab topishda barcha tugunlarni birma-bir tekshirishga asoslanadi. Ko’rinib turibdiki, bizga faqat tugunlar N va yoylar L ro’yxatidan iborat frag berilgan bo’lsa, u holda maqsadli hal qiluvchi y’olni topishda tugunlarni birma-bir tekshirish yordamida erishish mumkin. Ko’p hollarda maqsadli hal qiluvchi y’olni topishda tugunlar N va yoylar L ro’yxatidan iborat grafda izlashni qisqartirish (vaqtni, hisoblash hajmini) maqsadida ba’zi bir qo’shimcha axborotlardan foydalanish imkoniyatlari mavjud. Shunday qo’shimcha axborotlar evristikli deyiladi. Evristikli axborotlar yordamida izlash evristikli izlash deyiladi. Masala haqidagi evristik axborotlarni hisobga olib alternative tugunlarni tanlash protsedurasi evristike deyiladi, Masala haqidagi qo’shimcha (evristikli) axborotlar ba’zi hollarda tugunlardan iborat HFda, ya’ni tugunlar to’plamida baholash funksiyasi f ( n ) shaklida sonli ifoda ko’rinishida ifodalanishi mumkin. HFdagi n-tugundagi baholash funksiyasi f( ּ ), n – tugunlardan izlashni davom ettirishni baholash uchun haqiqiy son f ( n ) bilan taqqoslanadi. f ( n ) ning qiymati qanchalik kichchik (ba’zi masalalarda qanchalik katta) bo’lsa, ushbu n-tugundan izlashni davom ettirish maqsadga muvofiq bo’ladi. Shuning uchun ham evrisrtik izlashni ba’zi hollarda maqsadli (afzalli) izlash deb atashadi. Evristik izlashning g’oyasi quyidagidan iborat: yo’lning bo’shlanish tuguni sifatida nomzod tugunlar orasidan afzalroq tugunni tanlash kerak va ushbi tugun grafdagi hal qiluvchi yo’lning boshlang’ish tuguni sifatida qabul qilinadi. Undan keyin boshlang’ich tugundan boshlanadigan yo’lni davom ettirish uchun boshlanf’ich tugundan chiqadigan bir qancha alternativ tugunlardan baholash funksiyasi kichchikroq (ba’zi hollarda kattaroq) qiymatga ega bo’lgan tugun tanlanadi. Yo’lni davom ettirish uchun navbatdagi tugunlarni tanlashda bir qancha alternativ tugunlardan baholash funksiyasi kichchikroq (ba’zi hollarda kattaroq) qiymatga ega bo’lgan tugunlar tanlanadi. Tugunlarni tanlash algoritm bo’yicha maqsadli echimga erishuvchi yo’lni topishgacha davom ettiriladi. Baholash funksiyasidan foydalnishga asoslangan ko’plab evristik izlash usullari mavjud. Bular qatoriga chiziqli programmalashtirishdagi simpleks usuli, A * algoritmi, sonli tahlildagi ketma-ket yaqinlashish usullari, minimaxli usullar, al’fa- 12 betta algoritm, dinamik programmalash, shoxlar va chegaralar usuli, bo’linish va baholash usulilarini kiritish mumkin . Evristik izlashni namoyish etrish uchun namuna sifatida А * algoritmini keltiramiz. 3.2.4.1. А * algoritmi Bu algoritm HFko’rinishida berilgan tugunlar to’plamida evristik axborotlar baholi funksiya shaklida ifodalanganda evristik izlashda qo’llaniladi. Aytaylik, echiladigan masalaning HFni ifodalovchi grafda N = { n 1 , n 2 , …, n r } –tugunlar to’plami, L = { l 1 , l 2 , …, l s } – yoylar to’plami berilgan bo’lsin. Ushbu grafdagi ixtiyoriy L= (ni,n j)∈ L yoy uchun ushbu yoyning bahosini ifodalovchi c ( n i , n j ) son aniqlangan bo’lsin.Dgar bir nechta maqsadli tugunlar mavjud bo’lsa, u holda boshlang’ich tugunni n 0 , maqsadli tugunni esa t yoki t i bilan belgilaymiz. Baholash funksiyasi f( ּ ) ning qiymatini shunday aniqlaymizki , uning n tugunlardagi qiymati f ( n ) ikkita qiymatlar yig’indisi bahosidan iborat bo’ladi: 1) boshlang’ich n 0 tugunlardan n tugungacha bo’lgan yo’lning minimal bahosi; 2) n tugunlardan qaysidir maqsadli t yoki t i tugungacha bo’lgan yo’lning minimal bahosi; Agar birinchi bahoni g * ( n ) va ikkinchi bahoni h * ( n ) bilan belgilasak, u holda f ( n ) baholsh funksiyasi f * ( n ) =g * ( n ) + h * ( n ). g * ( n ) va h * ( n ) fynksiyalarni c ( n i , n j ) lar yordamida quyidagicha aniqlash mumkin: g¿(n)= min {lα}n0 n ∑ lα∈{lα}n0n c(niα,njα) h¿(n)= min lα min {lα}n0n ∑ lα∈{lα}n0n c(niα,njα) Bu erda formuladagi g * ( n ) uchun minimum boshlang’ich n 0 tugundan n tugungacha bo’lgan barcha {lα}n0 n yo’llar bo’yicha hisoblanadi. Formuladagi h * ( n ) uchun tashqi minimum barcha maqsadli t i tugunlar bo’yicha, ichki minimum esa boshlang’ich n tugundan tugallanadigan maqsadli t i tugungacha bo’lgan barcha {lα}n ti yo’llar bo’yicha hisoblanadi. {lα}m n belgilash, boshlang’ich m tugundan n tugallanadigan ixtiyoriy yo’l uchun foydalaniladi. Umumiy holda baholash funksiyasini f ( n ) = g ( n ) + h ( n ), aniqlash mumkin, bu erda g ( n ) funksiy - g * ( n ) funksiyalarning qandaydir bahosi (yaqinlashish), h ( n ) funksiy esa - h * ( n ) funksiyalarning qandaydir bahosi 13 7 33 6.8-rasm(yaqinlashish). g ( n ) funksiyning bahosi sifatida n 0 tugunlardan n tugungacha bo’lgan{lα}n0 n yo’llardagi yoylar bahosining yig’imdisi, ya’ni g(n)= ∑ lα∈{lα}n0n c(niα,njα). Barcha maqsadli bo’lmagan tugunlar uchun h(n)≤ h∗(n) shatni qanoatlantiruvchi baholash funksiyasi f ( n ) = g ( n ) + h ( n ), А * algotitmi deb ataladi. Barcha maqsadli bo’lmagan tugunlar uchun h(n)≤ h∗(n) shat qatnashmasa baholash funksiyasi f ( n ) = g ( n ) + h ( n ), А algotitmi deb ataladi . А va А * algoritmlarida g ( n ) funksiy g * ( n ) funksiyalarning qandaydir bahosi hisoblanadi. Ikkala algoritmda ham tugunlarni izlashni davom ettirish uchun alternativ tugunlar orasidan f ( n ) funksiyaning eng kichchik qiymatiga mos keladigan tugun tanlanadi. Misol. Aitaylik izlashning 1-qadamida S0 tugun ochilgan bo’lsin va undan yo’lning baholash qiymatlari ^ g( V 1 ) = 3 va ^ g( V 2 ) = 7 ega bo’lgan V 1 va V 2 tugunlar chiqqan bo'lsin. 2-qadamda V1 tugun ochiladi va undan V 3 va yana V 2 tugun chiqadi, bunda V 1 tugundan V 2 tugunga olib boruvchi yolning baholash funksiyasi qiymati qiymatlari ^g(V1)=3 . Ko’rinib turibdiki, S0 tugundan V2 tugungacha bo;lgam qisqa yo’lning bahosi ^ g( V 2 ) = 6 (6.8-rasm). Ta’kidlash joizki, ^ g( V ) = 7 ≥ g ( V ) = 6 . Misol. Aytaylik , A, B, S, D, E, F zavodlar va ular orasidagi yo’l masofalari berilgan bo’lsin (6.9-rasm). Biz A zavoddan F zavodga kelishimiz kerak. Zavodlar orasidagi masofa ikki yoqlama, ya’ni xarakat ikki tomonga ham yo’naltirilgan bo’lishi mumkin. 14 B S E F 8371 16 4829 37 27 31 47A 6.9-rasm. Zavodlarga borish yo’lini izlash masalasi10 D A B(93) S (64) E(16) F(0) 8371 16 4829 37 27 31 47A(95) 6.10-rasm. Zavodlarga borish yo’lini izlash masalasi. misol.10Bizga tugunlar orasidagi masofalar berilganligi uchun ular orasidagi yo’lni izlash uchun BFdan foydalanamiz. A zavodga eng yaqin zavod- B (10 км ), keyin – S(29), D(47), E(71), F(16). Yo’lning umumiy uzunligi - 173 км bo’lib, u optimal 95 км (A-S-E-F) yo’ldan ancha farq qiladi. Faraz qilaylik, bizga har bir zavoddan F gacha bo’lgan masofalar ma’lum bo’lsin (6.10-rasm). Bu ma’lumotlardan navbatdagi punktni tanlashda foydalanish mumkin. Demak, Adan boradigan punktlarga B (93 км ), S (64) va D (83) kiradi. Har bir qadamda maqsadli punktga maksimal yaqinlashish maqsadida, biz birinchi qadamda - S, ikkinchi qadamda -E, keyin–Fni tanlaymiz. Umumiy yo’lning uzunligi optmal qiymatga teng bo’ladi. Izlashning ushbu ko’rinishi xasisli ( жадным ) izlash deb ataladi. Bunda har bir yangi tugun baholash funksiyasi f(n) asosida tanlanadi. Biz aniq baholashga ega bo’lmaganligimiz sababli evristik funksiya h(n) yoki evristikadan foydalanamiz . Qaralayotgan masalada evristik funksiya h(n) sifatida to’g’ri chiziq bo’yicha maqsadli punktgacha bo’lgan masofa olinadi. 15D(83) B(93) S (64) E(16) F(0) 83 71 16 4829 37 27 31 47A(95) 6.11-rasm. Zavodlarga borish yo’lini izlash masalasi.10 D(83) A zavod B zavod 10+(93) =103 D zavod 27+(83) =110 S zavod 31+(64) =95Optimal marshrut minimal yo’llardan iborat bo’lgani uchun, ulardan izlashning oxirida natijalarni baholash uchun emas, balki izlashning har bir qadamida foydalanish kerak. Biz to’liq ma’lumotlarga ega bo’lmasakda, bizda bosib o’tilgan yo’l haqidagi aniq axborot va evristik funksiya mavjud. Ulardan foydalanib, har bir etapda yo’lning umumiy uzunligini baholash mumkin. Echimlar bahosini baholshlar yig’indisini minimallashtirish usuli А * algoritm deb ataladi . Baholash funksiyasi f(n) har bir qadamda f(n) = g(n) + h(n), hisaoblanadi, bu erda g(n)-n-tugunda erishiladigan bahosi, h(n)- n-tugunda evristik funksiyaning maqsadga erishiladigan bahosi. Baholash funksiyasini 6.10-rasmda keltirilgan zavodlarga borish yo’lining oxirgi varianti uchun qaraymiz. Adan chiqadigan punktlarni qaraydigan bo’lsak, u holda baholash funksiyasi quyidagi qiymatlarga ega bo’ladi (6.12-rasm) . 6.12-rasm. Ko’rinib turibdiki, S minimal BFga ega. Shuning uchun navbatdagi punkt sifatida S punkti tanlanadi. Ikkinchi qadamda biz uchib o’tilgan 31 км . yo’lga ega bo’lamiz. Shuning uchun Sdan navbatdagi punktlargacha baholash funksiyasi qiymatlari 6.13-rasmdagidek bo’ladi. 16 A zavod B zavod 10+(93) =103 D zavod 27+(83) =110 S zavod 31+(64) =95 A zavod 31+29+(93) =153 E zavod 31+48+(16) =95D zavod 31+47+(83) =161 A zavod B zavod 10+(93) =103 D zavod 27+(83) =110 S zavod 31+(64) =95 B zavod 31+29+(93) =153 E zavod 31+48+(16) =95D zavod 31+47+(83) =161 D zavod 31+48+(83) =162 A zavod B zavod 10+(93) =103 D zavod 27+(83) =110 S zavod 31+(64) =95 S zavod 10+29+(64) =103D zavod 10+37+(83) =140 6.13-rasm . Navbatdagi marshrut punk ti sifatida E tanlanadi (6.14-rasm) 6.14-rasm. Edan faqat Dgacha yo’l bor, lekin uning baholash funksiyasining qiymati A - D marshruti baholash funksiyasining qiymatiga nisbatan katta. Bundan kelib chiqadiki, bu marshrut (A - S - E - D - …) optimal echimni bermaydi. Shuning uchun S punktining o’rniga boshqa zavodni tanlash kerak. Baholash funksiyasi qiymatIning o’sishini e’tiborga olsak, u holda S punktidan keyin B tanlanadi. B tanlanadigan bo’lsa baholash funksiyalri bo’yicha punktlar 6.15- rasmdagidek joylashadi : 17 6.15- rasm . Bu erda D и S punktlari uchun ham olingan baholash fuksilarining qiymatlari oldingi marshrutlarda olingan baholash fuksilarining qiymatlaridan yuqori bo ’ layapti . Shuning uchun marshrutni Ddan boshlash kerak. Ddan to’g’ri Fga boriladi. Maqsadli echimga erishildi va u optimal echim hisoblanadi. Misol. S 0 boshlang’ich holatdan S t oxirgi holatga o’tuvchi ≪ Sakkiz ≫ o’yinini qaraymiz (6.16-rasm). Bu o’yinda har bir yurish harakati bo’sh katakga, ya’ni mos matritsada o (nol) raqami turgan katakga amalga oshiriladi. 6.16-rasm. Bu o’yinning maqsadi S 0 boshlang’ich holatdan S t oxirgi holatga o’tishni tamonlovchi o raqami turgan katakning yurish harakatining qisqa ketma-ketligini izlshdan iborat. S yordamida bir nechta yurish harakatidan keyin hosi bo;lgan joriy holatni belgilaymiz. Baholash funksiyasini f ( S ) = g ( S ) + h ( S ) aniqlaymiz. Bunda g ( S ) funksiyga- S 0 boshlang’ich holatdan S t oxirgi holatga olib keluvchi haqiqiy yurish harakatlari sonini, h ( S ) evristik funksiyaga esa - S t maqsadli holatga nisbatan S holatda o’zining joyida joylshmagan fishka(raqam)lar sonini mos qo’yamiz. Masala sharti va h ( S ) evristik funksiyaning aniqlanishidan barcha maqsali bo;lmagan tugunlar uchunh(S)≤ h∗(S) tengsizlik kelib chiqadi. А * algoritmga asosan maqsadli echimni izlash daraxti 6.17 –rasmda keltirilgan. 18 6.17-rasm. Ushbu rasmda har bir yurish harakati holatining o’ng pastki qismidagi kvadrat qavsda g ( S ) va h ( S ) funksiyalarning mos qiymatlari keltirilgan . Optimal hal qiluvchi yo’l qalin chiziq bilan ajratilgan. Ushbu holda S 0 boshlang’ich holatdan S t maqsadli holatni olish uchun o (nol) raqamli bo’sh katakchani eng kami bilan 5 marta yurish harakati amalga oshiriladi. Echimlar daraxti bahosi [1]. Echimlar daraxtini aniqlashda ikkita baholash qaraladi. Birinchisi echimlar daraxtida barcha yo’ylar baholari yig’indisidan iborat yig’indi baho bo’lsa, ikkinchisi esa echimlar daraxtida ikkita tugun orasidagi maksimal baholardan tashkil topgan yo’llarning maksimal bahosidan iborat. Yo’lning bahosi ushbu yo’lni tashkil etuvchi yo’ylar baholari yig’indisi bilan aniqlanadi. Misol. Keltirilgan tushunchalarni 6.18-rasmda keltirilgan daraxtli echimda tushuntishirish mumkin, bu erda yoylardagi raqamlar baholarni anglaradi. Bu misolda yig’indi baho 49 , maksimal baho 39 ga teng. 19 1 2 4 1 0 5 1 3 5 1 4 6 Z 6.18-rasm. Reduksiyali grafda yechimlar daraxti. Minimal bahoga ega bo’lgan echinlar daraxti optimal deyiladi. Tajriba orttirish uchun misol va topshiriqlar . 1- topshiriq. Nazariy qismni o`zlashtirish va B/B/B jadvalini to`ldirish. B/B/B texnikasini qo`llash bo`yicha ko`rsatma. 1. Ma’ruza rejasiga mos holda 2-ustunni to`ldiring. 2. O`ylang, juftlikda hal eting va javob bering, ushbu savollar bo`yicha nimani bilasiz, 3-ustunni to`ldiring. 3. O`ylang, juftlikda hal eting va javob bering, ushbu savollar bo`yicha nimani bilish kerak, 4-ustunni to`ldiring. 4. Ma’ruzani o`qing va materiallar bilan tanishing. 5. 5-ustunni to`ldiring. B/B/B jadvali (Bilaman/Bilishni hoxlayman/Bilib oldim) № Mavzu savoli Bilaman Bilishni ho x layma n Bilib oldim 1. 2. 3. 4. 5. 2-topshiriq. “Bilib oldim” ustuni asosida “T” jadvalini to`ldirish. Nazariy qismdan tayanch iboralarni aniqlash va “T” jadvalini qurish. Tayanch ibora Mazmuni 1. 2. ... n . 6- ma ’ ruza uchun adabiyotlar 1. Иванов В. М. Интеллектуальные системы : учебное пособие / В. М. Иванов. - Екатеринбург : Изд-во Урал.ун-та, 2015. — 92 с.ISBN 978-5-7996-1325-9. 20 2. Павлов С. Н. Системы sun’iy intellekt : учеб.пособие. В 2-х частях. / С. Н. Павлов. - Томск: Эль Контент, 2011. - Ч. 1. - 176 c. ISBN 978-5-4332-0013-5. 3. Назаров В. М. Техническая имитация интеллекта: учеб.пособие для вузов /В. М. Назаров, Д. П. Ким, И. М. Макрова.-М. :Высш. шк., 1998. - 144 с. 4. 4.Нильсон Н. Принципы искусственного интеллекта: пер. с англ. /Н. Нильсон. -М. : Радио и связь, 1985. - 375 с. 5. Тельнов Ю. Ф. Интеллектуальные информационные системы в экономике /Ю. Ф. Тельнов. -М. : Московский государственный университет экономики, статистики и информатики, 1998. - 174 с. 6. Newell A., Siwon H. GPS: A Program that Simulates Human Thought / Ed. By Feigenbaum E. A. and Feldman J. // Computers and Thought. - №4: McGraw Hill, 1963. 7. Allen J. AI Growing up / J. Allen // AI MAGAZINE. - 1998. - V. 19. - №4.- Р . 13- 23. 8. Russell S. L. Artificial intelligence: a modern approach / S. L. Russell,P. Norvig. - Upper Saddle River, New Jersey: Prentice - Hall Inc., 1995. - 905 p. 6-ma’ruza o’zini-o’zi tekshirish savollari 1. SITlarining masalalari umumiy xususiyatlari bo’yicha qanday sinflash mumkin? 2. SITlari yordamida echiladigan masalalarni qanday tiplarga ajratish mumkin ? 3. Masalalarni namoyish etish uslubini tanlashda odatda nechta holat e’tiborga olinadi ? 4. Masalani echish jarayoni qoidaga ko’ra nechta pog’onadan iborat bo’ladi ? 5. Mashina yordamida masalalarni namoyish etish shakllarini keltiring ? 6. Masalalarning holatini tavsiflashning qanday shakllari mavjud ?. 7. Daraxt mina ? 8. Daraxtda tugunlarning pog’onalari qanday aniqlanadi ? 9. Daraxtda masalalar ostilarining o’zaro aloqasi strukturasi qanday tiplarda bo’lishi mumkin ? 10. Daraxtda reduksiyalash nima ? 11. Almashtirilgan reduksiyalash daraxti nima ? 12. Predmet soha qanday xususiyatlarga ega? 13. SITlari masalalarini echishda qo’llaniladigan mavjud usullarni qanday sinflarga ajratiladi? 14. Holatlar fazosida echimni izlash usullari odatda qanday tiplarga bo’linadi ? 15. Umumiy holda holatlar daraxtini qandy ko’rinishda berish mumkin ? 16. Holatlar daraxtini qurish qanday amalga oshiriladi ? 17. Baholash funksiysi nima va qanday aniqlanadi ? 18. Tugunlarning chuqurligi deganda nima tushuniladi ? 19. Chuqurligi bo’yicha izlash algoritmining g’oyasi nimadan iborat ? 20. Chuqurligi bo’yicha birma-bir izlash algoritmi qanday qadamlardan iborat? 21. Kengligi bo’yicha izlash algoritmining g’oyasi nimadan iborat ? 22. Qanday axborotlar evtistik deyiladi ? 21 23. Evristikli izlash nima ? 24. Evristik izlashning g’oyasi nimadan iborat ? 25. А * algoritm qanday holatda qo’llaniladi ? 26. Umumiy holda А * algoritmda baholash funksiyasi qanday ko’rinishda aniqlanadi ? Masalalar va topshiriqlar 1. A boshlang’ich tugunli 2 va 3 qatlamli daraxtni quring. 2. A boshlang’ich tugunli 2 va 3 qatlamli “va” tipli daraxtni quring. 3. A boshlang’ich tugunli 2 va 3 qatlamli “yoki” tipli daraxtni quring. 4. A boshlang’ich tugunli 3 va 5 qatlamli “va-yoki” tipli daraxtni quring. 5. Daraxtning K tuguni uchun ichki tugunlarni toping va mantiqiy formula ko’rinishda ifodalang. 6. Daraxtning 2 va 3- qatlamlarini aniqlang. 7. Quyidagi “va-yoki” graflar uchun mantiqiy formulalarni tuzing : 8. Quyidagi “va-yoki” graflar uchun mantiqiy formulalarni tuzing : 22 А 2 D А 2С А 2В 2А 2 D Д А 2С А 2В 2А 2 D А 2С А 2В 2 V В С А 2 А 2 C Г Д А 2B Б В 2 Е В 2 H И В 2 А 2 G Г Д А 2V С А 2B В 2 D Д В 2 Е В 2 H И В 2D 9. Quyidagi “va-yoki” graflar uchun mantiqiy formulalarni tuzing : 10. “Agar B va C yoki D va K masalalar yechilsa, uholda A va Ye yoki F va G masalalar yechiladi” muloxazani graf ko’rinishda tasvirlang. 11. “ A masala yechilishi mumkin, agarda B va C va K yoki D yoki G masalalar yechilsa” muloxazani graf ko’rinishda tasvirlang. 12. ((B∧C∧ D )∨(D∧G ))→ A mantiqiy formulani graf ko’rinishda tasvirlang. 13. ((((E∨ F )→ B)∧ (G → C ))∨((H ∧ I)→ D ))→ C )→ A mantiqiy formulani graf ko’rinishda tasvirlang. 14. (((E→ F )→ B)∧ (G → C ))∨((H → I)∨ D ))→ A mantiqiy formulani graf ko’rinishda tasvirlang. 15. Robot o’z xarakatini n punktlarning ixtiyoriy bittasidan boshlab, har birida faqat bir martadan bo’lib, yana boshlang’ich punktiga qaytib kelishi kerak. Quyidagi grafda berilgan A→ E,A→ H ,B→ H ,V → E marshrutlar uchun eng qisqa yo’lni toping. Ushbu marshrutlarni daraxt ko’rinishda tasvirlang. 16. Robot o’z xarakatini n punktlarning ixtiyoriy bittasidan boshlab, har birida faqat bir martadan bo’lib, yana boshlang’ich punktiga qaytib kelishi kerak. Quyidagi grafda berilgan A→ D ,A→ B,B→ D ,V → A marshrutlar uchun eng qisqa yo’lni toping. Ushbu marshrutlarni daraxt ko’rinishda tasvirlang. 23 А 2 G Г Д А 2B В 2 D В 2 Е В 2 H И В 2V Б В 2 V 1B 1 V 2 V 3 Е 1А 2 G Д А 2B Б В 2 D В 2 Е В 2 H В 2V Б В 2 B 2 Г Д А 2B 1 C 1 Д В 2 G 2 Е В 2 G 3 B Б А V В H ИЕ 20 35 5 10 12Г Д14 16 2223 4 25 348 24 . 17. Samarqand viloyati tumanlarini, shaxarlarini hamda tuman va shaharlarini bog’lovchi transport harakati mavjud (6.1-jadval). 6.1-jadvaldan foydalanib tumanlar, shaxarlar hamda tuman va shaharlarni bog’lovchi eng qisqa transport harakati marshrutini toping va graf ko’rinishda tasvirlang. 6.1-jadval. Samarqand viloyati tumanlari, shaharlari hamda tuman va shaharlari orasidagi masofalar ( km ) . № Viloyat tumanlari va shaharlariSam arkand sh. Bulung’ur Jom boy Ishtixon K attako’rg’an Q o’shrabot N arpay N urobod O qdaryo PayariQ Pastdarg’om Paxtachi Sam arqand Tayloq Urgut 1. Samarkand sh. 37 19 61 70 95 104 75 35 34 29 124 12 15 43 2. Bulung’ur 37 23 92 106 110 145 11 65 47 66 166 43 38 56 3. Jomboy 19 23 74 88 115 128 94 49 43 48 146 30 19 46 4. Ishtixon 61 92 74 23 40 54 57 25 37 47 74 72 75 101 5. Kattaqo’rgan 70 106 88 23 65 34 57 48 61 44 55 90 93 117 6. Qushrabot 95 110 115 40 65 95 170 65 38 115 118 107 110 135 7. Narpay 104 145 128 54 34 95 86 79 91 78 27 122 125 150 8. Nurobod 75 111 94 57 53 170 86 70 95 55 107 87 90 107 9. Oqkdaryo 35 65 49 25 48 65 79 70 40 47 99 47 50 75 10. Payariq 34 47 43 37 61 38 91 95 40 50 112 52 55 74 11. Pastdarg’om 29 66 48 47 44 115 78 55 47 50 99 32 35 76 12. Paxtachi 124 166 146 74 55 118 27 107 99 112 99 147 150 166 13. Samarqand 12 43 30 72 90 107 122 87 47 52 32 147 18 52 14. Tayloq 15 38 19 75 73 110 125 90 50 55 35 150 18 27 24А В V D G12 15 12 18 24 9 14 2222 15. Urgut 43 56 46 101 117 135 150 107 75 74 76 166 52 27 6 .2-jadval. Topshiriq variantlari: Variant raqami Boshlang’ich punkt Oxirgi punkt 1. Samarqand sh. Payariq 2. Kattaqo’rgon Tayloq 3. Oqdaryo Pastdargom 4. Bulung’ur Paxtachi 5. Qo’shrabot Narpay 6. Paxtachi Jomboy 7. Payariq Nurobod 8. Narpay Urgut 9. Samarqand sh. Paxtachi 10. Tayloq Qo’shrabot 11. Nurobod Jomboy 12. Payariq Bulung’ur 13. Urgut Samarqand sh. 14. Jomboy Narpay 15. Paxtachi Qo’shrabot 16. Payariq Urgut 17. Narpay Nurobod 18. Bulung’ur Tayloq 19. Ishtixon Jomboy 20. Qo’shrabot Urgut 21. Ishtixon Samarqand sh. 22. Jomboy Nurobod 23. Bulung’ur Paxtachi 24. Jomboy Urgut 25. Nurobod Bulung’ur 26. Narpay Jomboy 27. Samarqand sh. Nurobod 25 28. Tayloq Narpay 29. Paxtachi Payariq 30. Nurobod Paxtachi 18. O’zbekiston Respublikasi viloyatlarini bog’lovchi transport harakati mavjud (6.3-jadval). 6.3-jadvaldan foydalanib viloyatlarni bog’lovchi eng qisqa transport harakati marshrutini toping va graf ko’rinishda tasvirlang. 6.3 -jadval. O’zbekiston Respublikasi viloyatlarini bog’lovchi transport harakati masofasi (km) № BiloyatlarToshkent Farg’ona Andijon Namangan Sirdaryo Jizzax Samarqand Qashqadaryo Surxondaryo Navoiy Buxoro Xorazm Korakalpog’iston Respublikasi 1. Toshkent 320 348 282 73 201 305 452 621 468 575 949 1092 2. Farg’ona 320 80 81 335 402 560 707 876 669 829 1202 1347 3. Andijon 348 80 67 432 499 603 750 919 766 857 1230 1390 4. Namangan 282 81 67 360 427 532 679 848 694 790 1164 1318 5. Sirdaryo 73 335 432 360 129 233 380 549 395 502 876 1020 6. Jizzax 201 402 499 427 129 108 255 424 271 374 748 895 7. Samarqand 305 560 603 532 233 108 146 329 167 273 647 791 8. Qashkadaryo 452 707 750 679 380 255 146 218 263 181 586 710 9. Surxondaryo 621 876 919 848 549 424 329 218 446 386 791 983 10. Navoiy 468 669 766 694 395 271 167 263 446 117 491 634 11. Buxoro 575 829 857 790 502 374 273 181 386 117 407 548 12. Xorazm 949 1202 1230 1164 876 748 647 586 791 491 407 195 13. Q ora q alpo - g’iston Respublikasi 1092 1347 1390 1318 1020 895 791 710 983 634 548 195 26 6 .4-jadval. Topshiriq variantlari: Variant raqami Boshlang’ich punkt Oxirgi punkt 1. Toshkent Fargona 2. Andijon Sirdaryo 3. Jizzax Namangan 4. Sirdaryo Qashkadaryo 5. Namangan Toshkent 6. Fargona Sirdaryo 7. Jizzax Andijon 8. Samarqand Surxondaryo 9. Navoiy Fargona 10. Toshkent Jizzax 11. Sirdaryo Namangan 12. Xorazm Samarqand 13. Surxondaryo Toshkent 14. Kashkadaryo Navoiy 15. Jizzax Sirdaryo 16. Fargona Buxoro 17. Qorakalpog’iston Respublikasi Andijon 18. Surxondaryo Navoiy 19. Namangan Samarqand 20. Sirdaryo Xorazm 21. Toshkent Andijon 22. Navoiy Jizzax 23. Fargona Qashkadaryo 24. Sirdaryo Qorakalpog’iston Respublikasi 25. Buxoro Sirdaryo 26. Andijon Surxondaryo 27. Namangan Fargona 28. Sirdaryo Toshkent 27 29. Navoiy Qorakalpog’iston Respublikasi 30. Andijon Xorazm Masofalar geografik karta asosida olingan. 19. Quyida robotning xarakati marshruti keltirilgan. Kyeltirilgan ma’lumotlardan foydalanib, robotning bir tugun(punkt)dan boshqa tugungacha bo’lgan eng uzun yo’lini toping: 1) 1-tugundan 5 -tugungacha. 2) 3-tugundan 5 -tugungacha. 3) 1-tugundan 6 -tugungacha. 20. Robot o’z xarakatini n punktlarning ixtiyoriy bittasidan boshlab, har birida faqat bir martadan bo’lib, yana boshlang’ich punktiga qaytib kelishi kerak. Quyidagi grafda berilgan A→ G ,G → V ,B→ V ,V → G marshrutlar uchun eng uzun yo’lni toping. Ushbu marshrutlarni daraxt ko’rinishda tasvirlang. . 21. Robot o’z xarakatini n punktlarning ixtiyoriy bittasidan boshlab, har birida faqat bir martadan bo’lib, yana boshlang’ich punktiga qaytib kelishi kerak. Quyidagi grafda berilgan A→ G ,G → V ,B→ E,A→ E marshrutlar uchun eng uzun yo’lni toping. Ushbu marshrutlarni daraxt ko’rinishda tasvirlang. 22. Samarqand viloyati tumanlarini, shaxarlarini hamda tuman va shaharlarini bog’lovchi transport harakati mavjud (6.1-jadval). 6.1-jadvaldan foydalanib 28А В G DV12 18 24 9 14 2222 1662 Е 3012 512 11 18 1 101 2 4 64 7 8 1 4 3 3 5 3 5 3 7 9 8 1 2 9 8 1 12 50А Б V А В 10 13 1414 0 11 40 G Г tumanlar, shaxarlar hamda tuman va shaharlarni bog’lovchi eng uzun transport harakati marshrutini toping va graf ko’rinishda tasvirlang. 23. O’zbekiston Respublikasi viloyatlarini bog’lovchi transport harakati mavjud (6.3-jadval). 6.3-jadvaldan foydalanib viloyatlarni bog’lovchi eng uzun transport harakati marshrutini toping va graf ko’rinishda tasvirlang. 24. Aytaylik , shaxarlar orasidagi xavoli uchish yo’li masofalari berilgan bo’lsin. Shaxarlar orasidagi masofa ikkiyoqlama, ya’ni xarakat ikki tomonga ham yo’naltirilgan bo’lishi mumkin. A * algoritmdan foydalanib shaxarlar orasidagi optimal marshrutni aniqlang. 1) Xelsinki-Tver; 2) Tallin-Tver; 3) Moskva-S.Peterburg; 4) Moskva-Xelsinki. 25. Aytaylik , zavodlar orasidagi masofalar berilgan bo’lsin. Zavodlar orasidagi masofa ikkiyoqlama, ya’ni xarakat ikki tomonga ham yo’naltirilgan bo’lishi mumkin. Zavodlar orasidagi masofaning yig’indi qiymati va maksimal qiymatini aniqlang: 1) A-K; 29 2) A-D; 3) A-Ye; 4) A-I; 5) A-G; 6) A-B. 26. Aytaylik , fakultetlar orasidagi masofalar berilgan bo’lsin. Fakultetlar orasidagi masofa ikkiyoqlama, ya’ni xarakat ikki tomonga ham yo’naltirilgan bo’lishi mumkin. Fakultetlar orasidagi masofaning yig’indi qiymati va maksimal qiymatini aniqlang: 1) A-G; 2) A-E; 3) A-D; 4) A-I; 5) A-L; 6) A-M; 7) A-N. 27. Samarqand viloyati tumanlarini, shaxarlarini hamda tuman va shaharlarini bog’lovchi transport harakati mavjud (6.1-jadval). 6.1-jadvaldagi ma’lumotlar asosida A * algoritmdan foydalanib tumanlar, shaxarlar hamda tuman va shaharlarni bog’lovchi optimal transport harakati marshrutini toping va graf ko’rinishda tasvirlang. 28. O’zbekiston Respublikasi viloyatlarini bog’lovchi transport harakati mavjud (6.3-jadval). 6.3- jadvaldagi ma’lumotlar asosida A * algoritmdan foydalanib viloyatlarni bog’lovchi optimal transport harakati marshrutini toping va graf ko’rinishda tasvirlang. 6-ma’ruza uchun testlar 1. Sun’iy intellkt masalalarini umumiy xususiyatlari bo’yicha ………………..kabi sinflarga ajratish mumkin. a) tahlil va sintez, statikli va dinamikli, bilimlarni namoyish etish ucun umumiy tasdiqlardan foydalanish va xususiy havolalardan foydalanish masalalari; b) tahlil va sintez, mantiqli va dinamikli, obyektlarni taqqoslash ucun umumiy tasdiqlardan foydalanish va xususiy havolalardan foydalanish masalalari; c) tahlil va sintez, strukturali va nominalli, jarayonlarni o’rganish ucun xususiy teoremalardan foydalanish va integralli havolalardan foydalanish masalalari; 30 e) o’rganish va o’rgatish, tahlil va sintez, integralli va differensialli, bilimli va bilimsiz va xususiy havolalardan foydalanish masalalari. 2. Sun’iy intellktda echiladigan masalalarning tiplarini aniqlang ? a) interpretatsiyalash, tashhislash, monitorihglash, bashoratlash, rejalashtirish, loyihalash, o’rganish-boshqarish, qaror qabul qilishni qo’llab-quvvatlash; b) interpretatsiyalash, tashhislash, mantiqli va dinamikli, obyektlarni taqqoslash ucun umumiy tasdiqlardan foydalanish va xususiy havolalardan foydalanish masalalari; c) tahlil va sintez, o’rganish-boshqarish, jarayonlarni o’rganish ucun xususiy teoremalardan foydalanish va integralli havolalardan foydalanish masalalari; e) o’rganish va o’rgatish, tahlil va sintez, integralli va differensialli, bilimli va bilimsiz va xususiy havolalardan foydalanish masalalari. 3. Sun’iy intellktda masalani echish jarayoni qoidaga ko’ra ………… pog’onalardan iborat. a) masalani namoyish etish va echimni izlash; b) masalani interpretatsiyalash va tashhislash; c) masalani o’rganish va boshqarish; e) masalani integrallash va differensiallash. 4. Masalalarning holatini tavsiflashning ……………. ………shakllari mavjud. a) qatorlar, vektorlar, matritsalar va graflar; b) qatorlar, bilimlar, matritsalar va graflar; c) ma’lumotlar, qatorlar, bilimlar va graflar hqarish; e) integrallar, differensiallar va o’zgaruvchilar. 5. Daraxt deb shunday yo’naltirilgan grafga aytiladiki , bunda uning ……….. a) ildizidan tashqari har bir tuguniga faqat bitta yoy kiradi; b) ildizidan tashqari har bir tuguniga bir nechta yoy kiradi; c) markazidan tashqari har bir tuguniga faqat bitta yoy kiradi; e) ildizidan markazigacha har bir tuguniga faqat bitta yoy kiradi. 6. Daraxtda VA – strukturalarga ……………………mos keladi. а ) bog’langan tugunlar; б ) tupikli va siklli tugunlar; с ) bog’lanmagan tugunlar; e) bo’sh tugunlar. 7. Daraxtda YOKI – strukturalarga ……………………mos keladi. а ) bog’lanmagan tugunlar; б ) tupikli va siklli tugunlar; с ) bog’langan tugunlar; д ) bo’sh tugunlar. 8. Daraxtda masalalar ostilarining o’zaro aloqasi strukturasi …………………tiplarda bo’lishi mumkin. a) VA-strukturalar va VA-YOKI-strukturalar; b) VA-strukturalar va VA-U HOLDA-strukturalar; c) VA-strukturalar va U HOLDA-YOKI-strukturalar; e) AGAR –U HOLDA -strukturalar va VA-YOKI-strukturalar. 9. Daraxtda masalalarni reduksiya(tiklash)lashda ………………. mos qo’yiladi. a) tugunlarga masalalar, yoylarga esa masalalarni reduksiyalash operatorlari; b) tugunlarga VA- reduksiyalash, yoylarga esa VA-U HOLDA-strukturalar; c) tugunlarga VA-strukturalar, yoylarga esa U HOLDA-YOKI- reduksiyalash; 31 A VA И В Е F G C D H I VA И A VA И В Е F G C D H I VA И A VA И В Е F G C D H I VA И A VA И В Е F G C D H I VA Иe) yoylarga AGAR –U HOLDA –strukturalar, tugunlarga esa VA-YOKI- strukturalar. 10. Daraxtda boshlang’ich tugunni aniqlang ? a) A; b) AB; c)AD; e) E. 11. Daraxtda 2-pog’onali tugunlarni aniqlang ? a) B, C, D; b) A, B, E; c)A, C, G; e) A, D, H. 12. Daraxtda 3-pog’onali tugunlarni aniqlang ? a) E, F, G, H, I; b) ABE, ACG, ADI; c)A, C, G; e) A, D, H. 13. Daraxtda A masala echiladi, agarda ……………………masalalar echilsa. a) B va C yoki D; b) B yoki E; c) B va C yoki G; e) B va C yoki H. 32 A VA И В Е F G C D H I VA И A VA И В Е F G C D H I VA И A VA И В C D A VA И В Е F G C D H I VA И14. Daraxtda B masala echiladi, agarda ……………………masalalar echilsa. a) E yoki F; b) A yoki E; c) A va F; e) A va E yoki A va H. 15. Daraxtda D masala echiladi, agarda ……………………masalalar echilsa. a) H va I; b) A yoki H; c) A va I; e) A va I yoki A va H. 16. Berilgan daraxtga mos mantiqiy formulani quring ?. a) ((B∧C)∨ D)→ A ; б ) (B∨ C ∨ D )→ A ; с ) (B→ C → D )→ A ; e) (B∧ C ∧ D )→ A . 17. Berilgan daraxtga mos mantiqiy formulani quring ?. a) (((E∨ F )→ B)∧(G → C ))∨ ((H ∧ I)→ D ))→ A ; б ) (((E∧ F )→ B)∧(G → C ))∨ ((H ∨ I)→ D ))→ A ; с ) (((E→ F )→ B)∧ (G → C ))∨((H → I)→ D ))→ A ; 33 e) (((E∨ F )→ B)→ (G → C ))∨((H ∧ I)→ D ))→ A . 18. Sun’iy intellekt tizimlari masalalarini echishda qo’llaniladigan mavjud usullar sinfini ko’rsating ? a) Bir o’lchovli fazoda, ierarhik fazoda, ma’lumotlar xatoli va to’liqmas bo’lganda va bir nechta modellar yordamida izlash usullari; б ) Bir o’lchovli fazoda, ierarhikmas fazoda, ma’lumotlar xatoli va to’liq bo’lganda va ikkita model yordamida izlash usullari; с ) Bir o’lchovli fazoda, ierarhik fazoda, ma’lumotlar xatolikmas va to’liqmas bo’lganda, uchta model yordamida izlash usullari; e) Yarim o’lchovli fazoda, ierarhik fazoda, ma’lumotlar xatoli va to’liq bo’lganda, to’liqmas modellar yordamida izlash usullari. 19. Sun’iy intellekt tizimlari masalalarini echishda bir o’lchovli fazoda echimni izlash usullaridan ………………………. …….foydalaniladi; a) o’lchovi katta bo’lmagan sohalarda, modellar to’liq, ma’lumotlar aniq va to’liq bo’lganda; б ) o’lchovi kichchik bo’lmagan sohalarda, modellar to’liq, ma’lumotlar aniq va to’liqmas bo’lganda; с ) o’lchovi katta bo’lgan sohalarda, modellar to’liqmas, ma’lumotlar aniqmas va to’liq bo’lganda; e) o’lchovi katta bo’lmagan sohalarda, modellar to’liqmas, ma’lumotlar aniq va to’liqmas bo’lganda. 20. Sun’iy intellekt tizimlari masalalarini echishda ierarhik fazoda echimni izlash usullaridan ………………………. …….foydalaniladi; a) o’lchovi katta bo’lgan sohalarda echimlarni izlashda; б ) o’lchovi kichchik bo’lgan sohalarda echimlarni izlashda; с ) o’lchovi aniqmas bo’lgan sohalarda echimlarni izlashda; e) o’lchovi aniq, lekin echimi aniqmas sohalarda echimlarni izlashda. 21. Sun’iy intellekt tizimlari masalalarini echishda holatlar fazosida echimni izlash odatda ……………………………..usullari yordamida amalga oshuriladi. a) evristikli, chuqurligi va kengligi bo’yicha izlash; б ) evristikli, o’lchovi kichchik bo’lgan sohalarda echimlarni izlash; с ) evristikli, o’lchovi aniqmas bo’lgan sohalarda echimlarni izlash; e) chuqurligi, o’lchovi aniq aniqmas sohalarda echimlarni izlash. 22. Grafda b aholash funksiysi ………… aniqlanadi. a) grafning tugunlarida ; б ) grafning yoylarida ; с ) faqat grafning bosh va oxirgi tugunlarida ; e) faqat grafning oxirgi tugunida . 23. Grafda i xtiyoriy tugun uchun hosil qilingan baholash funksiysi qiymati ushbu ………………………………………….. aniqlaydi. a) tugundan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini ; б ) yoydan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini ; с ) tugunga qo’shma bo’lgan yoydan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini ; 34 e) ushbu tugunga qo’shni bo’lgan tugundan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini . 24. Grafda i xtiyoriy tugun uchun hosil qilingan baholash funksiysi qiymati ushbu ………………………………………….. aniqlaydi. a) tugundan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini ; б ) yoydan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini ; с ) tugunga qo’shma bo’lgan yoydan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini ; e) ushbu tugunga qo’shni bo’lgan tugundan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini . 25. Grafda tugunlarning chuqurligi deganda …………….. teng bo’lgan son tushuniladi. a) tugunlarning pog’onalari tartib raqamiga; б ) yoylarning pog’onalari tartib raqamiga; с ) tugun va yoylarning pog’onalari tartib raqamiga; e) qo’shma tugunlarning pog’onalari tartib raqamiga. 26. Grafda yo’lni c huqurligi bo’yicha izlashda ixtiyoriy tugunning baholash funksiyasi qiymati ushbu ………………. bo’ladi. a) tugundan boshlang’ich tugungacha bo’lgan masofaga to’g’ri proportsional ; б ) tugundan oxirgi tugungacha bo’lgan masofaga to’g’ri proportsional ; с ) tugundan boshlang’ich tugungacha bo’lgan masofaga teskari proportsional ; e) tugundan oxirgi tugungacha bo’lgan masofaga teskari proportsional . 27. Grafda yo’lni kengligi bo’yicha izlashda ixtiyoriy tugunning baholash funksiyasi qiymati ushbu ………………. bo’ladi. a) tugundan boshlang’ich tugungacha bo’lgan masofaga teskari proportsional ; б ) tugundan oxirgi tugungacha bo’lgan masofaga to’g’ri proportsional ; с ) tugundan boshlang’ich tugungacha bo’lgan masofaga to’g’ri proportsional ; e) tugundan oxirgi tugungacha bo’lgan masofaga teskari proportsional. 28. Grafda c huqurligi bo’yicha izlash strategiyasini qanday vaqtda qo’llah qulay ? a) faqat tugunlar va yoylar ro’yxatidan iborat holatlar fazosi berilganda ; б ) faqat tugunlar ro’yxatidan iborat holatlar fazosi berilganda ; с ) faqat yoylar ro’yxatidan iborat holatlar fazosi berilganda ; e) faqat tugunlarning baholash funksiyasi berilganda . 29. Grafda yo’lni c huqurligi bo’yicha izlash strategiyasini qanday vaqtda qo’llah qulay ? a) faqat tugunlar va yoylar ro’yxatidan iborat holatlar fazosi berilganda ; б ) faqat tugunlar ro’yxatidan iborat holatlar fazosi berilganda ; с ) faqat yoylar ro’yxatidan iborat holatlar fazosi berilganda ; e) faqat tugunlarning baholash funksiyasi berilganda . 30. Grafda yo’lni c huqurligi bo’yicha izlash strategiyasida boshlang’ich va oxirgi tugunlar qanday tanlanadi? a) grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi va undan eng uzoqda (uzunligi bo’yicha) joylashgan tugun tanlanadi ; 35 б ) grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi va unga eng yaqin (uzunligi bo’yicha) joylashgan tugun tanlanadi ; с ) grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi va unga eng yaqin (uzunligi bo’yicha) joylashgan qo’shma tugun tanlanadi ; e) tugunlar ixtiyoriy olinadi . 31. Grafda yo’lni kengligi bo’yicha izlash strategiyasida boshlang’ich va navbatdagi tugun qanday tanlanadi? a) grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi va unga eng yaqin (uzunligi bo’yicha) joylashgan tugun tanlanadi ; б ) grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi va undan eng uzoq (uzunligi bo’yicha) joylashgan tugun tanlanadi ; с ) grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi va unga eng yaqin (uzunligi bo’yicha) joylashgan qo’shma tugun tanlanadi ; e) tugunlar ixtiyoriy olinadi . 32. Grafda yo’lni kengligi bo’yicha izlash strategiyasida boshlang’ich tugunga yaqin bo’lgan tugunlar bir nechta bo’lsa, u holda ular orasidan ……………………….tanlanadi. a) eng chapdagisi; б ) eng o’ngdagisi; с ) tupiklisi; e) qo’shnisi . 33. Grafda yo’lni kengligi bo’yicha izlash strategiyasida echimni izlash tupikli holatga kelib qolsa, u holda ……………………… izlash davom ettiriladi. a) oldingi tugunga qaytiladi va ushbu tugundan echimni kengligi bo’yicha; б ) keyingi tugunga o’tiladi va ushbu tugundan echimni kengligi bo’yicha; с ) oldingi tugunga qaytiladi va ushbu tugundan echimni chuqurligi bo’yicha; e) faqat boshlang’ich tugunga qaytiladi va ushbu tugundan echimni kengligi bo’yicha . 34. Grafda yo’lnining navbatdagi tugunlarini tanlashda nimaga asoslanadi ?. a) tugunlarning baholash funksiylariga ; б ) yoylarning baholash funksiyalariga ; с ) tugunlar va yoylarning baholash funksiylariga ; e) tugunlar va yoylarning baholash funksiylarining yig’indisiga . 35. А * algoritmda baholash funksiyasi umumiy holda qanday beriladi ? a) f ( n ) = g ( n ) + h ( n ) ; б ) f ( n ) = h ( n ) ; с ) f ( n ) = g ( n ) ; e) f ( n ) = g ( n ) + h ( n )+1. 36

Sun’iy intellekt masalalarini holatlar fazosida namoyish etish Reja: 1. Sun’iy intellekt tizimlarining masalalari. 2. Sun’iy intellekt masalalarini echishning umumiy uslublari. 3. Sun’iy intellekt masalalarini echishning usullari. 3.1. Predmet soha xususiyatlari va masalalarni echish usullarini sinflash. 3.2. Holatlar fazosida echimni izlash. 3.2.1. Holatlar fazosida echimni izlash usullari. 3.2.2. Chuqurligi bo’yicha izlash strategiyasi. 3.2.3. Kengligi bo’yicha izlash strategiyasi. 3.2.4. Evristikli izlash. 3.2.4.1. А * algoritmi. Tayanch iboralar: Sun’iy intellekt (Artificial Intelligence), statik va dinamik masalalar (static and dynamic problems), bilimlarni namoyish etish (knowledge representation), interpretatsiya (interpretation), diagnostika (diagnostics), bashoratlash (prediction), rejalashtirish (planning), loyihalash (design), o’rganisg (training), boshqarish (control), vektorlar (vectors), matritsalar (matrix), graflar (counts), operatorlar (operators), maqsadli holat (targetstate), tupikli tugunlar (deadlock tops), holatlar fazosida echimni izlash (statespace search), birma-bir tekshirish (exhaustive search), kengligi bo’yicha birma-bir tekshirish (toomuc hindepth), evristik algoritm (heuristic algorithm), echimlar daraxti (decision tree), iyerarxikli va alternativli fazolar (hierarchical and alternative space), ochiq va yopiq tugunlar (opening and closing thetopof), marshrut (route), tartiblangan birma-bir tekshirish algoritmi (algorithm ordered strumming). 1. Sun’iy intellekt tizimlarining masalalari Sun’iy intellekt tizim(SIT)larining masalalari turli predmet sohalarni qamrab olgan bo’lib, ular orasida bizness, ishlab chiqarish, tibbiyot, loyihalash va boshqarish tizimlari kabilar ilg’or sohalar hisoblanadi. Keltirilgan masalalarni umumiy xususiyatlari bo’yicha quyidagicha sinflash mumkin [1-4, 8-10]. 1) Tahlil va sintez qilish masalalari. Tahlil qilish masalasida obyekt modeli beriladi va ushbu modelning noma’lum parametrlarini aniqlash talab etiladi. Sintez qilish masalasida obyekt modelining noma’lum xarakteristikalarini qanoatlantiruvchi shartlar beriladi va ushbu obyektning modelni qurish talab etiladi. 2) Statikli va dinamikli masalalar. Statikli masalalarda echimlarni hosil qilish jarayonida vaqt hisobga olinmaydi va olam haqidagi bilimlar o’zgarmas deb qaraladi. Dinamikli masalalarda esa yuqoridagining aksi qaraladi. 3 ) Bilimlarni namoyish etish ucun umumiy tasdiqlardan foydalanish . Bunda foydalaniladigan umumiy tasdiqlarda aniqlanadigan aniq obyektlarga ochiq havolalar berilmaydi. 1

4) Xususiy havolalardan foydalanish. Bunda aniq obyektlarga havolalarni o’z ichiga oluvchi xususiy havolalardan foydalaniladi. Echiladigan masalalarni quyidagi tiplarga ajratish mumkin: • interpretatsiyalash – ma’lumotlarning ma’nosini aniqlash jarayoni; • tashhislash –obyektlarni anglash yoki tizimning nosozligini aniqlash; • monitorihglash -haqiqiy vaqt oralig’ida ma’lumotlarni uzluksiz izohlash va ba’zi parametrlarning etarli chegaralardan chiqishi haqida signallar berish; • bashoratlash -oldingi va hozirgi modellar asosida obyektlar harakatining rejasini qurish; • rejalashtirish -ba’zi funksiyalarni bajarish qobilyatiga ega obyektlarning harakat rejasini qurish; • loyihalash -oldin mavjud bo’lmagan obyektni yaratish va oldindan aniqlangan xossalar asosida obyektlarni hosil qilishni tasniflashga tayyorlash; • o’rganish -obyektlar haqidagi ma’lumotlarni o’rganish uslubiyoti; • boshqarish -tizimlar funksiyasi bo’lib, tizimlarning qandaydir rejimda faollashuvini qo’llab quvvatlash yoki qandaydir berilgan vazifani bararishga mo’ljallangan murakkab tizimlarning harakatini boshqarish; • qaror qabul qilishni qo’llab-quvvatlash- protseduralar majmuasi bo’lib, u qaror qabul qilish uchun zarur ma’lumotlar bilan ta’minlangan bo’ladi va qaror qabul qilish jarayoni uchun ko’rsatmalar beradi. Masalalarni namoyish etish uslubini tanlashda odatda ikkita holat e’tiborga olinadi [1, 5-7]: -masalalarni namoyish etish haqiqiylikni etarli aniq modellashtirishi zarur ; - masalalarni namoyish etish uslublari shunday bo’lishi kerakki, ushbu masalani echish EHM (echuvchi) uchun qulay bo’lsin . 2. Sun’iy intellekt masalalarini echishning umumiy uslublari Masalani echish jarayoni qoidaga ko’ra ikki pog’onadan iborat bo’ladi: masalani namoyish etish va echimni izlash. Mashina yordamida masalalarni namoyish etish shakllarini izlash masalasi qiyin formallashgan ijodiy jarayon hisoblanadi. Shuning uchun masalalarni namoyish etishda qo'llaniladigan ba’zi shakllarni quyidagich keltirish mumkin [1]: 1) Holatlar fazosi(HF)da namoyish etish; 2) Masalalarni masalalar ostilariga keltirish yo’li bilan namoyish etish; 3) Teoremalar ko’rinishida namoyish etish; 4) Kombinatsiyali namoyish etish. Masalalarning holatini tavsiflashning turli shakllari mavjud. Xususan, masalalarni qatorlar , vektorlar, matritsalar va graflar ko’rinishda tavsiflash mumkin HFda echimlarni izlash protseduralari boshlang’ich holatni maqsad funksiyaga aylantiruvchi operatorlar ketma-ketligini aniqlashga asoslanadi. Daraxt deb shunday yo’naltirilgan grafga aytiladiki , bunda uning ildizidan tashqari har bir tuguniga faqat bitta yoy kiradi. Shunday qilib, daraxtda ildizdan tashqari har bir tiguni bitta yoyning oxiri va 2

A И В Е F G C D H I И 6.1-rasm.Masalalarni reduksiyalash daraxti. G FE H IDA K B C 6.2-rasm. Almashtirilgan reduksiyalash daraxti. кцииbitta yoki bir nechta yoyning boshi bo’ladi. Daraxtda V tugundan Vi tugunlar hosil bo’ladi. Bunda V - bosh tugun, Vi - ichki tugunlar deb nomlanadi. Bosh tugun (ildiz) 0-pog’onali, ildizdan hosil bo’lgan tugunlar 1-pog’onali, 2-pog’onali va h.k. k-pog’onali bo’lishi mumkin. Masalalar ostilarining o’zaro aloqasi strukturasi ikki tipda bo’lishi mumkin: VA- strukturalar va VA-YOKI -strukturalar. VA-strukturalarda asosiy masalani echishda barcha masalalar ostilarini echish talab etiladi. VA-YOKI - strukturalarda xususiy masalalar guruhlarga bo’linadi va bu guruhlar bir-biri bilan YOKI munosabati yordamida , guruhlar ichidagilar esa bir-biri bilan VA munosabati yordamida bog’lanadi. Bunday holda boshlang’ich masalani echish uchun, faqat qandaydir bitta guruhga taalluqli barcha masalalar ostilarini echish etarli hisoblanadi. Masalalarni masalalar ostilariga keltirishni namoyish etishni tavsiflash uchun masalalarni reduksiya(tiklash)lash grafi deb nomlanuvchi grafdan foydalaniladi (6.1- rasm). Bunda grafning tugunlariga masalalar, yoylriga esa masalalarni reduksiyalash operatorlari mos qo’yiladi. Daraxt ildiziga boshlang’ich masala, 1-pog’ona tugunlarga esa boshlang’ich masaladan hosil qilingan masalalar ostilari mos qo’yiladi. A masala echiladi, agarda B va C masalalar yoki D masala echilsa. B masala echiladi, agarda E yoki F masala echilsa. C- masala echiladi, agarda G masala echilsa. D masala echiladi, agarda H va I masalalar echilsa. VA- strukturali tugunlarning bog’lanishini ko’rsatish uchun maxsus egri chiziqdan foydalaniladi. Agar daraxtda VA- strukturali bog’langan tugunlar bo’lsa, u holda ular uchun qo’shimcha tugunlar kiritiladi va ushbu tugunlar VA- strukturali tugunlarning bosh tugunlariga aylanadi ( рис . 6.2). 3

Bundan keyin faqat a lmashtirilgan reduksiyalash daraxtlarini qaraymiz . Masalalarni masalalar ostilariga keltirishni namoyish etishda boshlang’ich masalani bir nechta masalalar octilariga bo’lish qaraladi va bo’lingan har bir masala osti echimi boshlang’ich masalaning echimini beradi. Har bir masala ostilari oz navbatida yana masala ostilariga bo’linishi mumkin. Masala ostilariga bo’lish jarayoni nazariy jihatdan chegaralanmagan. Amaliy jihatdan masala ostilariga bo’lish jarayoni eng quyi pog’onadagi masala ostilari yordamida echimni olguncha davom ettiriladi. 3. Sun’iy intellekt masalalarini echishning usullari 3.1. Predmet soha xususiyatlari va masalalarni echish usullarini sinflash Masalalarni izlashga keltirishga asoslangan echish usullari masala echilayotgan predmet soha hususiyatlariga va masala echimiga foydalanuvchi tomonidan qo’yilgan talablarga bevosita bog’liq bo’ladi. Predmet soha xususiyatlari [1] : 1) Echim izlanayotgan fazo hajmi; 2) Sohaning vaqtli va fazoli o’zgarish darajasi (ststistik va dinamik sohalar); 3) Sohani tavsivlovchi modelning to’liqligi. Agar model to’liq bo’lmasa, u holda sohani tavsiflashda bir-birini to’ldiruvchi bir nechta modellardan foydalaniladi; 4) Echilayotgan masala haqidagi ma’lumotlarning aniqligi, ya’ni ma’lumotlarning aniqlik(hatolik) va to’liqlik(to’liqmaslik) darajasi. SITlari masalalarini echishda qo’llaniladigan mavjud usullarni quyidagicha sinflash mumkin [1, 8]: 1) Bir o’lchovli fazoda echimni izlash usullari – bu usullardan o’lchovi katta bo’lmagan sohalarda, modellar to’liq, ma’lumotlar aniq va to’liq bo’lganda foydalaniladi; 2) Ierarhik fazoda echimni izlash usullari - bu usullardan o’lchovi katta bo’lgan sohalarda echimlarni izlashda foydalaniladi; 3) Ma’lumotlar xatoli va t o’liqmas bo’lganda izlash usullari; 4) Bir nechta modellar yordamida izlash usullari - bu usullardan sohani tavsiflashda bitta modelning o’zi etarli bo’lmaganda foydalanilad. 3.2. Holatlar fazosida echimni izlash 3.2.1. Holatlar fazosida echimni izlash usullari HFda echimni izlash usullari odatda quyidagilarga bo’linadi [1-4]: 1) Chuqurligi bo’yicha izlash; 2) Kengligi bo’yicha izlash; 3) Evristikli izlash. HFda echimlarni izlash protseduralari boshlang’ich holatni maqsad funksiyaga aylantiruvchi operatorlar ketma-ketligini aniqlashga asoslanadi. Agar operatorlar ketma-ketligi bir nechta va optimallashtirish mezoni berilgan bo’lsa, u holda masala 4

A B C12 11 8 10 6.3-rasm.Marshrutni tanlash masalasi.D 55 6 A AC 10 15 15 11 108 6 3 8 11 5 11 112 10 8 6 8 14 12 10 3929 *36 *39 *36 * 29 * ADCBA ACDBA ACBDAABCDAABDC AABDC ABDC ABCD ACDB ADCB ADBCADC ADB ACDACBABCABD AB AD 6.4-rasm. Masalaning holatlar grafi.ushbu mezonni qanoqtlantiruvchi optimal operatorlar ketma-ketligini izlash masalasiga keltiriladi. HFda echimlarni izlash usullarini holatlar daraxti(grafi)dan foydalanib tavsivlash qulay hisoblanadi. Holatlar daraxtida echimlarni izlash masalasi daraxt ildizidan maqsadli holatga mos tugungacha bo’lgan yo’lni (optimalli, agar optimallik mezoni berilgan bo’lsa) topishga keltiriladi. Umumiy holda holatlar daraxtini (S0 ,F,G) uchlik ko’rinishda berish mumkin. Bu erda S0−¿ bitta elementdan iborat to’plam , F- operatorlar to’plami, G-maqsadli holatlar to’plami. Holatlar daraxtini qurish quyidagicha amalga oshiriladi: avvalo daraxt ildiziga(boshlang’ich holat) F dagi operatorlarni qo’llab 1-pog’onali tugunlar quriladi; Keyin, F dagi operatorlardan 1-pog’onali tugunlarga qo’llaniladiganlaridan foydalanib 2-pog’onali tugunlar quriladi va h.k. Ushbu protsedura maqsadli tugunni topguncha davom ettiriladi. Misol. Yuk tashuvchi robot A punktdan chiqib, (B, C, D) punktlarning har birida faqat bir martadan bo’lib, yana A punktga qaytib kelishi kerak. Punktlar orasidagi masofalar va marshrutlar sxemasi 6.3-rasmda keltirilgan. Marshrutni tanlash masalasi uchun HFda echimlarni izlash 6.4-rasmda keltirilgan [1]. 5 ADBCA

Похожие

Sun’iy Intellekt Tizimlari Regressiya
Sun’iy intellekt haqida umumiy ma’lumotlar.
Sun’iy intellekt va inson tafakkurining solishtirma taxlili
Sun’iy bazis vektor usuli va chiziqli programmalash masalalarini sonli yechishga qo’llash.
Mashinaviy o’qitish. Mashinaviy o’qitish turlari. Bilimlarni namoyish etish modellari