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

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.
U mumiy 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 echimlarni 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.
Chuqurligi bo’yicha izlash strategiyasi. Tugunlarning chuqurligi deganda tugunlarning pog’onalari tartib raqamiga teng bo’lgan son tushuniladi.
Chuqurligi bo’yicha izlash strategiyasini faqat tugunlar N = {n₁, n₂, …, n_r} ro’yxati va yoylar L = {l₁, l₂, …, 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.