Holatlar fazosida yechimni kengligi va chuqurligi bo’yicha izlashning dasturiy ta’minoti

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI

"Kompyuter injiniring" fakulteti

"Dasturiy injiniringi” yo’nalishi

Labaratoriya-№1

Mavzu: Holatlar fazosida yechimni kengligi va chuqurligi bo’yicha izlashning dasturiy ta’minoti.
Bajardi: Bakhtiyor Elboyev
Qabul qildi: Narkulov A. S


SAMARQAND – 2023
Mavzu:Holatlar fazosida yechimni kengligi va chuqurligi bo’yicha izlashning dasturiy ta’minoti.
Holatlar fazosida echimni kengligi va chuqurligi bo’yicha izlash strategiyasida faqat tugunlar N = {n1, n2, …, nr} ro’yxati va yoylar L = {l1, l2, …, ls} ro’yxatidan iborat holatlar fazosi (HF) berilganda qo’llash maqsadga muvofiq. Bu erda lk= (nik, njk) qirralar bo’lib, nik tugundan njk tugunga yo’naltirilgan bo’ladi. Kengligi bo’yicha izlash algoritmi. Bu 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 tugunga yaqin (uzunligi bo’yicha) joylashgan tugun tanlanadi. Navbatdagi tugunlararni tanlash, xuddi boshlang’ich tugundagidek, o’zidan oldingi tugunga nisbatan eng yaqin joylashgan tugunni tanlash bilan davom ettiriladi. Tugunlarni tanlash algoritm bo’yicha maqsadli echimga erishuvchi yo’lni topishgacha davom ettiriladi [1]. Ta’kidlash lozimki, echimni kenglik bo’yicha izlashda boshlang’ich tugunga yaqin 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 kengligi bo’yicha izlash davom ettiriladi. Chuqurligi bo’yicha izlash algoritmi.
Tugunlarning chuqurligi deganda tugunlarning pog’onalari tartib raqamiga teng bo’lgan son tushuniladi. Bu 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. Chuqurligi bo’yicha birma-bir izlash algoritmi [1-4]. 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; 3 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. 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.

Variant: