Dastlabki qadam - Mustaqil ish mavzu: Marshurutlar va ularning vazifalari Qabullagan: Bajargan: nukus-2024

Dastlabki qadam. Manbaga (1 belgili uchga)
1 0
qiymatni mos
qo‘yib, bu uchni dastlab
R
deb qabul qilingan R to‘plamga kiritamiz:
R {1} .
R V \ R
Deb olamiz.
Umumiy qadam. Boshlangʻich uchi R to‘plamga, oxirgi uchi esa
R to‘plamga tegishli bo‘lgan barcha yoylar to‘plami
(R, R )
bo‘lsin. Har
bir
(i, j) (R, R )
yoy uchun
hij i cij
miqdorni aniqlaymiz, bu yerda i
deb
i R
uchga mos qo‘yilgan qiymat (grafning 1 belgili uchidan chiqib i
belgili uchigacha eng qisqa yo‘l uzunligi) belgilangan.
j
min
(i, j )( R,R )
hij
qiymatni aniqlaymiz.
(R, R )
to‘plamning oxirgi
tenglikda minimum qiymat beruvchi barcha elementlarini, ya’ni
(i, j)
yoylarni ajratamiz. Ajratilgan yoylarning har biridagi
j R
belgili uchga
j qiymatni mos qo‘yamiz. j qiymat mos qo‘yilgan barcha j uchlarni
R to‘plamdan chiqarib R to‘plamga kiritamiz.
Ikkala uchi ham R to‘plamga tegishli bo‘lgan barcha
(i, j)
yoylar
uchun
i cij j
tengsizlikning bajarilishini tekshiramiz.
Tekshirilayotgan tengsizlik o‘rinli bo‘lmagan (ja’ni
i cij
bo‘lgan)
j
*
*
barcha
j* belgili uchlarning har biriga mos qo‘yilgan eski
qiymat
j
*
o‘rniga yangi
i cij
qiymatni mos qo‘yamiz va
(i, j* )
yoyni ajratamiz.
*
j
*
Bunda eski qiymat aniqlangan paytda ajratilgan yoyni ajratilmagan
deb hisoblaymiz.
Minimal uzunlikka ega yo‘l haqidagi masalani hal etish usullari orasida Deykstra6 tomonidan taklif etilgan algoritm ko‘p qo‘llaniladi. Quyida grafning 1 belgili uchidan chiqib (bu uchni manba deb qabul qilamiz) grafdagi ixtiyoriy k uchgacha (bu uchni oxirgi uch deb hisoblaymiz) eng qisqa uzunlikka ega yo‘lni topish imkonini beruvchi Deykstra algoritmi keltirilgan.
Uchlarga qiymat mos qo‘yish jarayonini oxirgi ( k belgili) uchga qiymat mos qo‘yilguncha davom ettiramiz. Grafning 1 belgili uchidan (manbadan) chiqib uning ixtiyoriy k uchigacha (oxirgi uchigacha) eng
qisqa yo‘l uzunligi k bo‘ladi.
Oxirgi qadam. Grafning oxirgi uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda uning 1 belgili uchiga kelguncha harakatlanib, natijada grafdagi 1 belgili uchdan ixtiyoriy k uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topamiz. ■
m i sol. 2- shaklda tasvirlangan orgrafda oltita uch ( V {1, 2, 3, 4, 5, 6} ) va o‘n bitta yoy bo‘lib, har bir yoy uzunligi uning yoniga yozilgan. Ko‘rinib turibdiki, berilgan grafda manfiy uzunlikka
ega
(5,3)
yoy ham bor. Isbotlash mumkinki, bu grafda umumiy uzunligi
manfiy bo‘lgan sikl mavjud emas.
Yuqorida bayon qilingan Deykstra algoritmini berilgan grafga qo‘llab, eng qisqa uzunlikka ega yo‘lni topish bilan shugʻullanamiz.
Dastlabki qadam. Manbaga (1 belgili uchga)
1 0
qiymatni mos
qo‘yamiz va
R {1}
to‘plamga ega bo‘lamiz. Shuning uchun,
R V \ R {2, 3, 4, 5, 6}
bo‘ladi.
Umumiy qadam. 1- iteratsiya.
R {1} va
R {2,3,4,5,6}
bo‘lgani
uchun boshlangʻich uchi R to‘plamga tegishli, oxirgi uchi esa R to‘plam
elementi bo‘lgan barcha yoylar to‘plami (R, R ) {(1, 2),(1, 3),(1, 4)}ga ega
bo‘lamiz.
(R, R )
to‘plamga tegishli bo‘lgan har bir yoy uchun
Bu h12 ,
h13 va
h14
miqdorlar orasida eng kichigi
h12
bo‘lgani uchun
(1, 2)
yoyni ajratamiz (3- shaklda bu yoy qalin chiziq bilan belgilangan) va 2
belgili uchga
2 2
qiymatni mos qo‘yamiz. Algoritmga ko‘ra 2 uchni R
to‘plamdan chiqarib, R to‘plamga kiritamiz. Natijada7 R {1, 2} va
R {3, 4, 5, 6}
to‘plamlarga ega bo‘lamiz.
Ikkala uchi ham R to‘plamga tegishli bo‘lgan bitta
(1, 2)
yoy
bo‘lgani uchun faqat bitta
1 c12 2
tengsizlikning bajarilishini
tekshirish kifoya. Bu tengsizlik
0 2 2
ko‘rinishdagi to‘gʻri
munosabatdan iborat bo‘lgani uchun 2- iteratsiyaga o‘tamiz.
iteratsiya.
( R,R ) {(1 , 3) ,(1 , 4) ,(2 , 3) ,(2 , 5)}
bo‘lgani sababli
h13 10 ,
h14 13,
h23 7
va h25 11
qiymatlarni va
min{h13 , h14 , h23 , h25} h23 7
ekanligini
aniqlaymiz. Bu yerda eng kichik qiymat
(2, 3)
yoyga mos keladi.
Shuning uchun,
(2, 3)
yoyni ajratamiz va
3 7
qiymatni 3 belgili uchga
mos qo‘yamiz. 3 belgili uchni R to‘plamdan chiqarib, R to‘plamga
kiritgandan so‘ng
R {1, 2, 3} va
R {4, 5, 6}
to‘plamlar hosil bo‘ladi.
Ikkala uchi ham R to‘plamga tegishli bo‘lgan uchta
(1, 2) ,
(1, 3) va
(2, 3)
yoylardan birinchisi uchun
1 c12 2
tengsizlikning bajarilishi 1-
iteratsiyada tekshirilganligi va
1 , 2
qiymatlarning o‘zgarmaganligi
sababli faqat ikkinchi va uchinchi yoylarga mos
1 c13 3
va 2 c23 3
munosabatlarni tekshirish kifoya. Bu munosabatlar
0 10 7 va
2 5 7
ko‘rinishda bajariladi. Shuning uchun 3- iteratsiyaga o‘tamiz.
iteratsiya. Boshlangʻich uchi
R {1, 2, 3}
to‘plamga tegishli, oxiri
esa
R {4, 5, 6}
to‘plamga tegishli bo‘lgan yoylar to‘rtta:
(1, 4) ,
(2, 5) ,
(3, 4)
va (3, 5) . Shu yoylarga mos
hij ning qiymatlari
h14 13,
h25 11,
h34 15 ,
h35 13
va, shuning uchun,
min{h14 , h25 , h34 , h35} h25 11
bo‘ladi. Demak, bu
iteratsiyada
(2, 5)
yoyni ajratamiz va
5 11
deb olamiz. Endi, algoritmga
ko‘ra,
R {1, 2, 3, 5} va
R {4, 6}
to‘plamlarni hosil qilamiz.
Ikkala uchi ham R to‘plamga tegishli bo‘lgan yoylar oltita: (1, 2) ,
(2, 3) ,
(1, 3) ,
(2, 5) ,
(3, 5)
va (5, 3) . Bu yoylarning har biri uchun
i cij j
tengsizlikning bajarilishini tekshirishimiz kerak.
Minimal uzunlikka ega yo‘l haqidagi masalani hal etish usullari orasida Deykstra6 tomonidan taklif etilgan algoritm ko‘p qo‘llaniladi. Quyida grafning 1 belgili uchidan chiqib (bu uchni manba deb qabul qilamiz) grafdagi ixtiyoriy k uchgacha (bu uchni oxirgi uch deb hisoblaymiz) eng qisqa uzunlikka ega yo‘lni topish imkonini beruvchi Deykstra algoritmi keltirilgan.
iteratsiyalarda
(1, 2) ,
(2, 3) va
(1, 3)
yoylar uchun bu ish bajarilganligi
sababli tekshirishni tarkibida 5 belgili uch qatnashgan
(2, 5) ,
(3, 5) va
(5, 3)
yoylar uchun amalga oshirib, quyidagilarga ega bo‘lamiz:
(2, 5)
yoy
uchun
2 c25 5
munosabat to‘gʻri ( 2 9 11),
(3, 5)
yoy uchun
3 c35 5
munosabat to‘gʻri ( 7 6 11), lekin
(5, 3)
yoy uchun
5 c53 3
munosabat
noto‘gʻri (11 (6) 5 7 ). Oxirgi munosabatni hisobga olib, algoritmga
ko‘ra
3 7
o‘rniga
3 5
deb olamiz va
(5, 3)
yoyni ajratilgan deb, ilgari
ajratilgan
(2, 3)
yoyni esa ajratilmagan deb hisoblaymiz (3- shaklda
3 7
yozuvning va
(2, 3)
yoyning qalin chiziq’i ustiga ajratilganlikni inkor
qiluvchi belgisi qo‘yilgan).
iteratsiya.
R {1 , 2, 3, 5},
R {4, 6}
bo‘lgani uchun
(R, R ) {(1, 4),(3, 4),(3, 6),(5, 6)} va
h14 13,
h34 13 ,
h36 17 ,
h56 18
hamda
min{h14 , h34 , h36 , h56} h14 h34 13
bo‘ladi. Demak,
(1, 4)
va (3, 4)
yoylarni
ajratamiz hamda 4 belgili uchga
4 13
qiymatni mos qo‘yamiz. Natijada
R {1, 2, 3, 5, 4}, R {6} to‘plamlarga ega bo‘lamiz.
i cij j
munosabatning to‘gʻriligi
(1, 3) ,
(1, 4) ,
(2, 3) ,
(3, 5) ,
(5, 3) va
(3, 4)
yoylar uchun tekshirilib ko‘rilganda, uning barcha yoylar uchun
bajarilishi ma’lum bo‘ladi.
iteratsiya. Endi
( R, R ) {(3, 6),(4, 6),(5, 6)}
bo‘lgani uchun
h36 17 ,
h46 14,
h56 18 va
min{h36 , h46 , h56} h46 14
bo‘ladi. Bu yerda minimum
(4, 6)
yoyda erishilgani uchun uni ajratib, orgrafning oxirgi 6 belgili uchiga
6 14 qiymatni mos qo‘yamiz.
|