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

H
1.2-rasm. Almashtirilgan reduksiyalash daraxti. кции
olatlar fazosida yechimni izlash usullari. HFdayechimniizlashusullariodatdaquyidagilarga bo’linadi [1-4]:
1) Chuqurligi bo’yicha izlash;
2) Kengligi bo’yicha izlash;
3) Evristikli izlash.
U mumiyholdaholatlardaraxtini (_{ },F,G)uchlik ko’rinishda berish mumkin. Bu erda _{ }bitta elementdan iborat to’plam, F-operatorlar to’plami, G-maqsadli holatlar to’plami.
Misol.YuktashuvchirobotApunktdanchiqib, (B, C, D) punktlarning har birida faqatbirmartadanbo’lib, yanaApunktgaqaytibkelishikerak.Punktlar orasidagi masofalar va marshrutlar sxemasi 1.3-rasmda keltirilgan.
Marshrutni tanlash masalasi uchun HFda yechimlarni izlash1.4-rasmda keltirilgan [1].
Ushbu grafda boshlang’ich tugunga Aholat mos keladi. AtugunAB, AC, ADholatlarga mos keluvchi uhta 1-pog’onali ichki tugunlarni hosil qiladi. 1-pog’onali AB, AC, ADichki tugunlar 2-pog’onali ichki tugunlarnihosil qiladiva h.k.
Grafdatugunlarning ochilish tartibi izlash strategiyasi deb ataladi.
Chuqurligi bo’yicha izlashstrategiyasi. Tugunlarning chuqurligideganda tugunlarning pog’onalari tartib raqamiga teng bo’lgan son tushuniladi.
Chuqurligi bo’yichaizlashstrategiyasinifaqat tugunlar N = {n₁, n₂, …, n_r} ro’yxati va yoylar L = {l₁, l₂, …, l_s} ro’yxatidan iborat HFberilganda qo’llash maqsadga muvofiq.Buerdal_k= (n_ik, n_jk) qirralar bo’lib, n_ik tugundan n_jk tugunga yo’naltirilgan bo’ladi.



Chuqurligi bo’yicha izlash algoritmining g’oyasiquyidagidan 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.