1-amaliy mashg’ulot. Holatlar fazosida echimni 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’ich tugunni «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) v tugunni ochish. v tugunning barcha ichki tugunlarini «ochiq» royxatining boshiga joylashtirish va barcha ichki tugunlardan v tugunga keladigan ko’rsatkichlarni qurish; Agar v tugun ichki tugunlarga ega bo’lmasa, u holda 2-qadamga o’tish;
6) Agar ushbu tugunlardan birortasi maqsadli echimni hosil qilsa, u holda chiqishda echimni hosil qilish, aks holda 2-qadamga o’tish.
Qaralgan algoritmda 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. Misol sifatida marshrutni tanlash masalasi uchun HFda echimlarni izlashda A, AD, ADC, ADCB, ADCBA optimal marshrutni keltirish mumkin ( 1.1, 1.2-rasmlar).
Ta’kidlash lozimki, echimni chuqurligi bo’yicha izlashda eng chuqurlikga ega bo’lgan tugunlar bir nechta bo’lsa, u holda ular orasidan eng chapdagisi tanlanadi.
Agar echimni izlash tupikli holatga kelib qolsa, ya’ni joriy tugun maqsadli echimga olib kelmasa va uning chuqurroq tugunlar bilan aloqasi bo’lmasa, u holda oldingi tugunga qaytiladi va ushbu tugundan echimni chuqurligi bo’yicha izlash davom ettiriladi.
Misol. 1.3, а-rasmda HFda echimni chuqurligi bo’yicha izlashda qanday tugunlardan foydalanish kerakligi ko’rsatilgan. Bu erda a boshlang’ich, j va f oxirgi holatlarga mos keladi.
Ajratilgan [a, b, e, j] va [a, c, f] yo’llar – bu topilgan hal qiluvchi yo’llar, [a, c, f] yo’l esa – hal qiluvchi qisqa yo’l hisoblanadi.
HFda echimni chuqurligi bo’yicha izlash ko’p hollarda 1.3, а-rasmda ko’rsatilgandek yaxshi ishlaydi. Ba’zi hollarda u to'xtash holatiga ham tushib qolishi mumkin, masalan, sikllanish holatiga tushishi mumkin. Masalan 1.3, б –rasmda sikllanish holatlari [d, h, d] va [b, e, i, b] keltirilgan.



a)

b)



1.5-rasm. Chuqurligi bo’yicha izlash strategiyasi.