+6-маъруза

Misol. Qisqa yo’l haqudagi masala. Qisqa yo’l bilan grafning bir tugunidan boshqa tuguniga qanday borish mumkin? Ishlab
chiqarishni boshqarish masalalarida: qisqa 6.6-rasm. Kengligi bo’yicha yo’l bilan (masalan, eng kam yoqilg’i va vaqt, izlash strategiyasi.
ancha orzon) А punktdan Б 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 (6.7-rasm).

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

Boshlang’ich qiymatlarni 6.1-jadval ko’rinishda ham berish mumkin.
6.1-jadval. Qisqa yo’l haqudagi masalauchun boshlang’ich qiymatlar.

Yoyning boshi	Yoyning oxiri	Yo’ldagi vaqt
1	2	7
1	3	1
2	4	4
2	6	1
3	2	5
3	5	2
3	6	3
5	2	2
5	4	5
6	5	3

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.
6.7-rasmda va 6.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.

4. 
   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}. (6.1)

4. 
   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}. (6.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. (6.3)
(6.3) ni hisobga olsak
С(6) = min {4; С(2) +1}= min {4 ; 5+1}=4. (6.4)
(6.4) ni hisobga olsak, (6.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. (6.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: