1-amaliy mashg’ulot. Holatlar fazosida yechimni chuqurligi bo’yicha izlash Sun’iy intellekt masalalarini echishning umumiy uslublari

1-amaliy mashg’ulot. Holatlar fazosida yechimni chuqurligi bo’yicha izlash

Sun’iy intellekt masalalarini echishning umumiy uslublari. 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.

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 bitta yoki bir nechta yoyning boshi bo’ladi.

Daraxtda V tugundan tugunlar hosil bo’ladi. Bunda V- bosh tugun, - 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 (1.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 (1.2-rasm).

Bundan keyin faqat almashtirilgan reduksiyalash daraxtlarini qaraymiz.

1.2-rasm. Almashtirilgan reduksiyalash daraxti. кции
Holatlar fazosida yechimni izlash usullari. HFda yechimni izlash usullari odatda quyidagilarga bo’linadi [1-4]:

1) Chuqurligi bo’yicha izlash;

2) Kengligi bo’yicha izlash;

3) Evristikli izlash.

Umumiy holda holatlar daraxtini (,F,G) uchlik ko’rinishda berish mumkin. Bu erda bitta elementdan iborat to’plam, F- operatorlar to’plami, G-maqsadli holatlar to’plami.

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 1.3-rasmda keltirilgan.

Marshrutni tanlash masalasi uchun HFda yechimlarni izlash 1.4-rasmda keltirilgan [1].

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.