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’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 yechimni hosil qilsa, u holda chiqishda yechimni 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 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.