Qisqa masofani aniqlashning deykstra algoritmi. Reja eng qisqa yo’llar masalalarining turlari

QISQA MASOFANI ANIQLASHNING DEYKSTRA ALGORITMI.

REJA

1. Eng qisqa yo’llar masalalarining turlari.

1. Sozli algoritmni tuzish.

3. Algoritmni psevdokodda ishlab chiqish

4. Algoritmni baholash.

Yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan A va B nuqtalar orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “Eng yahshi” marshrutni ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar.

Biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. Masalaning modeli turlar yordamida tuziladi. Uzluksiz G turni har bir qirrasiga uning uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. Bunday turda masofa irralar yig’indisiga teng bo’ladi. Masalaning maqsadi ikkita berilgan uchlar orasidagi eng qisqa marshrutni topishdir.
Umuman, eng qisqa yo’llar masalalari kombinator optimallashtirishning fundamental muammolaridandir. Ularning bir necha turlari mavjud, masalan, ikkita berilgan uchlar orasida, berilgan va qolgan barcha uchlar orasida, turdagi har bir uchlar juftliklari orasida va boshqalar.
Deykstra algoritmning so’zli tavsifi
Shunday masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan.
Algoritm quyidagi qadamlardan iborat:

1. Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi.

   
   

2. Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi).

   
   

3. Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi.

   
   

4. Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi.

   
   
5. 
   
   BVa uchi, eng qisqa masofa aniqlangan uch sifatida, ruyhatdan o’chiriladi. Ruyhatga boshqa uch qo’yiladi, masalan, Roa. Bva o’z navbatida, boshqa, izlanayotgan ruyhatga qo’yiladi.
   

Keyingi eng qisqa masofani topish uchun butun jarayon qayta bajariladi. BVa dan keyin yana bir uch ruyhatga qo’yiladi. Dastlabkisi esa ruyhatdan o’chiriladi. Sikl Bed va Lex uchlarini bog’lash uchun belgilangan qirralar aniqlanishi bilan to’xtatiladi.

Rasm bo’yicha ikkinchi iteratsiyada Nbr uchi aniqlanadi va Roa gacha masofa 41 deb qabul qilinadi. Uchinchi iteratsiyada Gla uchigacha masofa eng qisqa va 27 deb qabul qilinadi. Quyidagi rasmda eng qisqa yo’llar daraxti ko’rinishida ularning natijaviy to’plami keltirilgan.
Aylanalar ichidagi sonlar algoritm bo’yicha qirralar tanlanish tartibini ko’rsatadilar. Bu daraxt bo’yicha biz Lex uchidan ixtiyoriy bizni qiziqtirayotgan uchgacha eng qisqa yo’lni topishimiz mumkin.
Ko’rilgan misolda Bed uchi Lex dan boshlab eng oxirgi bo’lib chiqdi, ya’ni Lex dan Bed gacha eng qisqa masofani topish uchun biz Lex dan barcha qolgan uchlargacha eng qisqa yo’llarni topishga majbur bo’ldik.
Demak, eng yomon holatda 2 ta berilgan uchlar orasidagi eng qisqa yo’lni topish, bir berilgan nuqtadan qolgan barcha nuqtalargacha eng qisqa yo’l topish masalasi bilan murakkabligi bir xil bo’ladi.

Algoritmni psevdokodda ishlab chiqish

1. 
   
   Masala qo’yilishi.
   

M ta uch va N ta qirralardan iborat uzluksiz grafda V₀ uchidan W uchigacha Dist(W) masofani topish kerak. Qirralar uzunliklari A matrisa bilan berilgan deb hisoblaymiz.

Qadam 0. [uchlarni belgilash] – bu yerda V₀ uchini “aniqlangan” deb belgilaymiz, qolgan barcha uchlarini “aniqlanmagan” deb hisoblaymiz.

Qadam 1. [o’zgaruvchilarni inetsiallashtirish] – bu yerda

Dist(U):=A(V₀ ,U) – barcha G ga tegishli U uchlari uchun;

Dist(V₀):=0; Next:=V₀;

Qadam 2. [sikl]. While NEXT<>W do

Begin

Qadam 3. [“aniqlanmagan” uchgacha eng qisqa yo’lni yangilash]. Har bir “aniqlanmagan” U uchi uchun

Dist(U):=min(Dist(U):Dist(Next)+A(Next, U)).

Qadam 4. [“aniqlanmagan” uchgacha eng qisqa yo’lni tanlash]. Agar U barcha “aniqlanmagan” uchlari orasida Dist(U) masofasi eng kichik bo’lsa, uni “aniqlangan” deb belgilaymiz va NEXT:=U.

end.
Bu algoritmning va dasturning murakkabligini O(M²) ekanligini ko’rsatish mumkin.