2-amaliy mashg’ulot. Holatlar fazosida yechimni kengligi bo’yicha izlash

2-amaliy mashg’ulot. Holatlar fazosida yechimni kengligi bo’yicha izlash


Kengligi bo’yicha izlash 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.
Misol. 2.1-rasmda HFda echimni kengligi bo’yicha izlashda qanday tugunlardan foydalanish kerakligi ko’rsatilgan. Bu erda a boshlang’ich, j va f oxirgi holatlarga mos keladi.

2.1-rasm. Kengligi bo’yicha izlash strategiyasi.

Ajratilgan [a, c, f] – bu birinch topilgan hal qiluvchi yo’l bo’lib, u qisqa yo’l hisoblanadi. Ikkinchi hal qiluvchi yo’l [a, b, e, j] bo’lib, u to’liq birma-bir tekshirish orqali hosil qilinadi.
Misol. Qisqa yo’l haqudagi masala. Qisqa yo’l bilan grafning bir tugunidan boshqa tuguniga qanday borish mumkin? Ishlab chiqarishni boshqarish masalalarida: qisqa yo’l (masalan, eng kam yoqilg’i va vaqt, ancha orzon) bilan А punktdan B punktga qanday borish mumkin? Bu masalani echish uchun yo’naltirilgan grafning boshlang’ich tugunidan oxirgi tugunigacha bo’lgan har bir yoyiga harakat vaqtini ifodalovchi son mos qo’yiladi (2.2-rasm).

2.2-rasm. Qisqa yo’l haqudagi masalauchun boshlang’ich qiymatlar.

Talab qilinadi: qanday qisqa yo’l bilan 1–tugundan 4 – tugunga borish mumkin?
Echimi. Quyidagi belgilashni kiritamiz: С(Т) – 1- tugundan T- tugungacha qisqa yo’lning uzunligi. Qaralayotgan masalada 1- tugundan 4- tugungacha bo’lgan С(4) qisqa yo’lni hisoblash talab etiladi.
2.2-rasmda va 2.1-jadvalda keltirilgan boshlang’ich qiymatlarni hisobga olsak, u holda 1-tugundan 3-tugunga uning uzunligi 1 ga teng bo’lgan faqat bitta yo’naltirilgan yoy chiqayapti, shuning uchun С(3)=1. Bundan tashqari, ko’rinib turibdiki С(1)=0.
4-tugunga uzunligi 4 ga teng bo’lgan 2-tugundan yoki uzunligi 5 ga teng bo’lgan 5-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli
С(4) = min {С(2) + 4; С(5) + 5}.
Demak, С(4) ni topish uchun avval С(2) va С(5) ni topish talab etiladi.
5-tugunga uzunligi 2 ga teng bo’lgan 3-tugundan yoki uzunligi 3 ga teng bo’lgan 6-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli
С(5) = min {С(3) + 2; С(6) + 3}.
Bilamizki, С(3) = 1. Shuning uchun
С(5) = min {1+2; С(6) + 3}= min {3 ; С(6) + 3}. (2.1)
6-tugunga uzunligi 3 ga teng bo’lgan 3-tugundan yoki uzunligi 1 ga teng bo’lgan 2-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli
С(6) = min { С(3)+3; С(2) +1}= min {4 ; С(2) +1}. (2.2)
2-tugunga uzunligi 7 ga teng bo’lgan 1-tugundan yoki uzunligi 5 ga teng bo’lgan 3-tugundan yoki uzunligi 2 ga teng bo’lgan 5-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli
С(2) = min {С(1) + 7; С(3) + 5 ; С(5) + 2}.
Bizga ma’lumki С(1) = 0, С(3) = 1, С(5) = 3. Shuning uchun
С(2) = min {0 + 7; 1 + 5 ; 3 + 2} = 5. (2.3)
(2.3) ni hisobga olsak
С(6) = min {4; С(2) +1}= min {4 ; 5+1}=4. (2.4)
(2.4) ni hisobga olsak, (2.1) dan
С(5) = min {3; С(6) + 3}= min {3 ; 4+ 3}=3.
Endi С(4) ni topish mumkin:
С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8. (2.4)
Shunday qilib, 1-tugundan 4-tugungacha bo’lgan qisqa yo’lning uzunligi 8. (6.5) munosabatdan ma’lumki, 4-tugunga 5-tugundan borish kerak. 5-tugunga 3-tugundan borish kerak. 3-yugunga esa faqat 1-tugundan birish mumkin. Demak, qisqa yo’l: