1-amaliy ish. Holatlar fazosida yechimni chuqurligi bo’yicha izlash Sun’iy intellekt masalalarini yechishning umumiy uslublari

1-amaliy ish. Holatlar fazosida yechimni chuqurligi bo’yicha izlash
Sun’iy intellekt masalalarini yechishning 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.

M asalalarni 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).

B undan keyin faqat almashtirilgan reduksiyalash daraxtlarini qaraymiz.