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

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
h_ij  _i  c_ij
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  c_ij   _j
tengsizlikning bajarilishini tekshiramiz.

Tekshirilayotgan tengsizlik o‘rinli bo‘lmagan (ja’ni
  _i  c_ij
bo‘lgan)

j

*

*
barcha
j_* belgili uchlarning har biriga mos qo‘yilgan eski 
qiymat

j

*
o‘rniga yangi
_i  c_ij
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 Deykstra⁶ 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.

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)
₁  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 h₁₂ ,
h₁₃ 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
qiymatni mos qo‘yamiz. Algoritmga ko‘ra 2 uchni R

to‘plamdan chiqarib, R to‘plamga kiritamiz. Natijada⁷ 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
₁  c₁₂  ₂
tengsizlikning bajarilishini

tekshirish kifoya. Bu tengsizlik
0  2  2
ko‘rinishdagi to‘gʻri

munosabatdan iborat bo‘lgani uchun 2- iteratsiyaga o‘tamiz.

2. iteratsiya.

(R,R )  {(1, 3),(1, 4),(2, 3),(2, 5)}
bo‘lgani sababli
h₁₃  10 ,

h₁₄  13,
h₂₃  7
va h₂₅  11
qiymatlarni va
min{h₁₃ , h₁₄ , h₂₃ , h₂₅}  h₂₃  7
ekanligini

aniqlaymiz. Bu yerda eng kichik qiymat
(2, 3)
yoyga mos keladi.

Shuning uchun,
(2, 3)
yoyni ajratamiz va
₃  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
₁  c₁₂  ₂
tengsizlikning bajarilishi 1-

iteratsiyada tekshirilganligi va
₁ , ₂
qiymatlarning o‘zgarmaganligi

sababli faqat ikkinchi va uchinchi yoylarga mos
₁  c₁₃  ₃
va  ₂  c₂₃  ₃

munosabatlarni tekshirish kifoya. Bu munosabatlar
0 10  7 va
2  5  7

ko‘rinishda bajariladi. Shuning uchun 3- iteratsiyaga o‘tamiz.

3. 
   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
h_ij ning qiymatlari
h₁₄  13,
h₂₅  11,
h₃₄  15 ,

h₃₅  13
va, shuning uchun,
min{h₁₄ , h₂₅ , h₃₄ , h₃₅}  h₂₅  11
bo‘ladi. Demak, bu

iteratsiyada
(2, 5)
yoyni ajratamiz va
₅  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  c_ij   _j

tengsizlikning bajarilishini tekshirishimiz kerak.
Minimal uzunlikka ega yo‘l haqidagi masalani hal etish usullari orasida Deykstra⁶ 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
 ₂  c₂₅  ₅
^{munosabat to‘gʻri (} 2  9 11^),
(3, 5)
yoy uchun
₃  c₃₅  ₅

^{munosabat to‘gʻri (} 7  6 11^{), lekin}
(5, 3)
yoy uchun
₅  c₅₃  ₃
munosabat

noto‘gʻri (11 (6)  5  7 ). Oxirgi munosabatni hisobga olib, algoritmga

ko‘ra
₃  7
o‘rniga
₃  5
deb olamiz va
(5, 3)
yoyni ajratilgan deb, ilgari

ajratilgan
(2, 3)
yoyni esa ajratilmagan deb hisoblaymiz (3- shaklda
₃  7

yozuvning va
(2, 3)
yoyning qalin chiziq’i ustiga ajratilganlikni inkor

qiluvchi  belgisi qo‘yilgan).

4. iteratsiya.

R  {1, 2, 3, 5},


R  {4, 6}
bo‘lgani uchun

(R, R )  {(1, 4),(3, 4),(3, 6),(5, 6)} va
h₁₄  13,
h₃₄  13 ,
h₃₆  17 ,
h₅₆  18
hamda

min{h₁₄ , h₃₄ , h₃₆ , h₅₆}  h₁₄  h₃₄  13
bo‘ladi. Demak,
(1, 4)
va (3, 4)
yoylarni

ajratamiz hamda 4 belgili uchga
₄  13
qiymatni mos qo‘yamiz. Natijada

R  {1, 2, 3, 5, 4}, R  {6} to‘plamlarga ega bo‘lamiz.

_i  c_ij   _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.

4. 
   iteratsiya. Endi
   

(R, R )  {(3, 6),(4, 6),(5, 6)}
bo‘lgani uchun
^h₃₆ ^{ 17} ,

^h₄₆ ^{ 14},
^h₅₆ ^{ 18} va
min{h₃₆ , h₄₆ , h₅₆}  h₄₆  14
bo‘ladi. Bu yerda minimum
(4, 6)

yoyda erishilgani uchun uni ajratib, orgrafning oxirgi 6 belgili uchiga
^{6  14} qiymatni mos qo‘yamiz.

Download 254,53 Kb.