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

Chuqurligi bo’yicha birma-bir izlash algoritmi[1, 5-7]. Chuqurligi bo’yicha birma-bir izlash algoritmini strukturalashgan holda qaraymiz:
1) Boshlang’ichtugunni «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;
5) vtugunniochish.vtugunning barcha ichki tugunlarini «ochiq» royxatining boshiga joylashtirish va barcha ichki tugunlardan vtugunga keladigan ko’rsatkichlarni qurish; Agar vtugun ichki tugunlarga ega bo’lmasa, u holda 2-qadamga o’tish;
6) Agar ushbu tugunlardan birortasi maqsadli yechimni hosil qilsa, u holda chiqishda yechimni hosil qilish, aks holda 2-qadamga o’tish.
Qaralganalgoritmda 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.Misolsifatidamarshrutni tanlash masalasi uchun HFda yechimlarni izlashda A, AD, ADC, ADCB, ADCBA optimal marshrutni keltirish mumkin(1.1, 1.2-rasmlar).
Ta’kidlash lozimki,yechimni chuqurligi bo’yicha izlashda eng chuqurlikga ega bo’lgan tugunlar bir nechta bo’lsa, u holda ular orasidan eng chapdagisi tanlanadi.
Agar yechimni izlash tupikli holatga kelib qolsa, ya’ni joriy tugun maqsadli yechimga olib kelmasa va uning chuqurroq tugunlar bilan aloqasi bo’lmasa, u holda oldingi tugunga qaytiladi va ushbu tugundan yechimni chuqurligi bo’yicha izlash davom ettiriladi.
Misol.1.3, а-rasmdaHFdayechimnichuqurligibo’yichaizlashdaqandaytugunlardanfoydalanishkerakligiko’rsatilgan. Bu erda a boshlang’ich, j vaf oxirgi holatlarga mos keladi.
Ajratilgan[a, b, e, j] va [a, c, f]yo’llar–butopilganhalqiluvchiyo’llar,[a, c, f]yo’lesa –halqiluvchiqisqayo’lhisoblanadi.
HFdayechimnichuqurligibo’yichaizlashko’p hollarda1.3, а-rasmdako’rsatilgandekyaxshiishlaydi. Ba’zihollardau to'xtash holatigahamtushibqolishimumkin, masalan, sikllanish holatiga tushishi mumkin. Masalan1.3, б –rasmdasikllanish holatlari [d, h, d] va [b, e, i, b] keltirilgan.



a)

b)

1.5-rasm.Chuqurligi bo’yicha izlash strategiyasi.