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



Download 317,69 Kb.
bet1/2
Sana19.03.2022
Hajmi317,69 Kb.
#501577
  1   2
Bog'liq
2-машгулот-18.04.18. (Kengligi 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:

Download 317,69 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish