Axborot texnologiyalari va kommunikatsiyalarni rivojlantirish vazirligi

Yo‘naltirilgan graf

Graflarda eng qisqa yo‘lni aniqlash (shortest path problem) algoritmlari va dasturlari ma’lumotlar tarmoqida eng qisqa yo‘lni topish uchun ishlatiladi. Bu algoritm va dasturlar, aloqadorliklarni tahlil qilish, tarmoqni tuzish, va boshqalar kabi turli sabablarni muvaffaqiyatli yechish uchun ishlatiladi. Quyidagi ikkita eng mashhur yo‘lni aniqlash algoritmi bilan tanishasiz:

1. Dijkstra algoritmi:
Dijkstra algoritmi grafdagi eng qisqa yo‘lni aniqlash uchun ishlatiladi. Bu algoritm aloqadorliklar va ularga bo‘lgan masofalarni hisoblash orqali eng qisqa yo‘lni topadi. Algoritm boshlanishi tug‘ilgan tug‘ilgan nuqta va qo‘ng‘iroqning saqlanishi yoki uni qiyoslash bilan boshlanadi. Algoritmi dasturiy til bilan tuzish mumkin.
2. Bellman-Ford algoritmi:
Bellman-Ford algoritmi ham grafdagi eng qisqa yo‘lni aniqlash uchun ishlatiladi. Bu algoritm negativ massivlarga (masofalarga) ega bo‘lgan graflarni ham qo‘llaydi. Bu algoritm odatda negativ massivlarga ega graflar uchun ishlatiladi.
Amaliy mashg’ulot ishlari uchun topshiriqlar.


Nazorat savollari:
1. Dijkstra algoritmi va Bellman-Ford algoritmi orasidagi farq nima?
2. Graflar qanday turlarda aniqlanadi?
3. Graflarni tasvirlash va yaratish uchun qanday dastur tuzish mumkin?
1. Eng qisqa yo'l algoritmlari kompyuter tarmoqlaridan logistika va transportgacha bo'lgan turli xil ilovalarda asosiy hisoblanadi. Grafikdagi ikkita nuqta orasidagi eng qisqa yo'lni topishga kelsak, ikkita mashhur algoritm Bellman-Ford algoritmi va Dijkstra algoritmidir. Ikkala algoritm ham bir xil muammoni hal qilishga qaratilgan bo'lsa-da, ularning yondashuvi va qo'llanilishi sohasida sezilarli farqlar mavjud.

Ushbu maqola haqiqiy muammodan foydalanib, ikkalasi o'rtasidagi farqni soddalashtirishga qaratilgan.

Bellman-Ford algoritmi manfiy chekka og'irliklari bo'lgan grafiklarda ishlaydigan dinamik dasturlash algoritmidir. Bundan farqli o'laroq, Dijkstraning ochko'z algoritmi faqat manfiy bo'lmagan chekka og'irliklari bo'lgan grafiklarda ishlaydi. Boshqacha qilib aytganda, agar grafik salbiy qirralarga ega bo'lsa, Dijkstra algoritmi o'rniga Bellman-Ford algoritmidan foydalanish kerak.

Bellman-Ford algoritmi grafikning har bir chetini qayta-qayta bo'shatish, bo'shashtirish orqali ishlaydi, ya'ni joriy chekkadan o'tish orqali oldindan hisoblangan masofani yaxshilash mumkinligini tekshirish. Ushbu jarayon grafikdagi har bir cho'qqi uchun takrorlanadi, jami V-1 o'tishlari, bu erda V - cho'qqilar soni. Keyin algoritm boshqa gevşeme o'tishini amalga oshirish orqali grafikdagi salbiy davrlarni tekshiradi. Agar salbiy tsikl mavjud bo'lsa, Algoritm eng qisqa yo'l yo'qligini ko'rsatadigan xabarni qaytaradi.

Boshqa tomondan, Dijkstra algoritmi manba cho'qqisidan boshlanadi va iterativ ravishda hali tashrif buyurilmagan manbadan eng kichik masofaga ega cho'qqini topadi. Bu jarayon barcha uchlari ziyorat qilinmaguncha takrorlanadi. Dijkstra algoritmi cho'qqilarning ustuvor navbatini saqlaydi, bu erda ustuvorlik manba cho'qqisidan masofa hisoblanadi. Har bir cho'qqiga tashrif buyurilganda, qisqaroq yo'l topilsa, uning manbagacha bo'lgan masofasi yangilanadi.

2. Ko'p bosqichli grafik - bu yo'naltirilgan, vaznli grafik bo'lib, unda tugunlarni bosqichlar to'plamiga bo'lish mumkin, shunda barcha qirralar faqat bosqichdan keyingi bosqichga (boshqacha qilib aytganda, bir xil bosqichning cho'qqilari va cho'qqilari orasida hech qanday chekka yo'q). joriy bosqichdan oldingi bosqichga).

Ko'p bosqichli grafikning cho'qqilari n ta ajratilgan kichik to'plamlarga bo'linadi S = { S1 , S2 , S3 ……….. Sn }, bu erda S1 - manba va Sn - cho'kish ( mo'ljal ). S1 va Sn ning kardinalligi 1 ga teng, ya'ni |S1| = |Sn| = 1.

Bizga ko'p bosqichli grafik, manba va maqsad berilgan, biz manbadan manzilga eng qisqa yo'lni topishimiz kerak. An'anaga ko'ra, biz 1-bosqichdagi manba va oxirgi bosqich deb hisoblaymiz.
Quyida biz ushbu maqolada ko'rib chiqamiz misol grafik

Endi biz qo'llashimiz mumkin bo'lgan turli strategiyalar mavjud: -

Manba va maqsad o'rtasidagi barcha mumkin bo'lgan yo'llarni topish va keyin minimalni topish uchun qo'pol kuch usuli. Bu mumkin bo'lgan eng yomon strategiya.

Dijkstraning yagona manbali eng qisqa yo'llar algoritmi. Ushbu usul manbadan boshqa barcha tugunlarga eng qisqa yo'llarni topadi, bu holda talab qilinmaydi. Shunday qilib, bu juda ko'p vaqtni oladi va bu MULTI-STAGE grafikdagi MAXSUS xususiyatdan ham foydalanmaydi.
Oddiy ochko'zlik usuli - har bir tugunda eng qisqa chiqish yo'lini tanlang. Agar biz yuqorida keltirilgan grafik misoliga ushbu yondashuvni qo'llasak, biz yechimni 1 + 4 + 18 = 23 deb olamiz. Ammo grafikni tez ko'rib chiqish 23 ga qaraganda ancha qisqaroq yo'llarni ko'rsatadi. Shunday qilib, ochko'z usul muvaffaqiyatsizlikka uchraydi!
Eng yaxshi variant - dinamik dasturlash. Shunday qilib, biz optimal quyi tuzilmani, rekursiv tenglamalarni va bir-biriga mos keladigan kichik muammolarni topishimiz kerak.
Optimal quyi tuzilma va rekursiv tenglama: -
B iz belgilaymiz: - M(x, y) x bosqich, y tugunidan T(maqsadli tugun) uchun minimal xarajat sifatida.

3.Endi biz qo'llashimiz mumkin bo'lgan turli strategiyalar mavjud:

Manba va maqsad o'rtasidagi barcha mumkin bo'lgan yo'llarni topish va keyin minimalni topish uchun qo'pol kuch usuli. Bu mumkin bo'lgan eng yomon strategiya.
Dijkstraning yagona manbali eng qisqa yo'llar algoritmi. Ushbu usul manbadan boshqa barcha tugunlarga eng qisqa yo'llarni topadi, bu holda talab qilinmaydi. Shunday qilib, bu juda ko'p vaqtni oladi va bu MULTI-STAGE grafikdagi MAXSUS xususiyatdan ham foydalanmaydi.
Oddiy ochko'zlik usuli - har bir tugunda eng qisqa chiqish yo'lini tanlang. Agar biz yuqorida keltirilgan grafik misoliga ushbu yondashuvni qo'llasak, biz yechimni 1 + 4 + 18 = 23 deb olamiz. Ammo grafikni tez ko'rib chiqish 23 ga qaraganda ancha qisqaroq yo'llarni ko'rsatadi. Shunday qilib, ochko'z usul muvaffaqiyatsizlikka uchraydi!
Eng yaxshi variant - dinamik dasturlash. Shunday qilib, biz optimal quyi tuzilmani, rekursiv tenglamalarni va bir-biriga mos keladigan kichik muammolarni topishimiz kerak.
Optimal quyi tuzilma va rekursiv tenglama: -
Biz belgilaymiz: - M(x, y) x bosqich, y tugunidan T(maqsadli tugun) uchun minimal xarajat sifatida. Oldingi maqolalarda biz har xil turdagi grafiklar va ularga ta'riflangan algoritmlarni ko'rib chiqdik. Biz ikkita algoritmni aniqladik: Prim va Kruskal algoritmlari. Ularning ikkalasi ham bir xil maqsadda qo'llaniladi - vaznli grafikning minimal chegara daraxtini topish, lekin ikki xil usulni taklif qiladi. Ushbu maqolada biz Dijkstra algoritmini ko'rib chiqamiz. U berilgan grafikdagi tanlangan ildizdan barcha cho'qqilargacha bo'lgan eng qisqa yo'llarni topish uchun ishlatiladi. Biz ushbu maqolada algoritm qanday ishlashini ko'rib chiqamiz va uni avvalgi ikkita usul bilan taqqoslaymiz. Birinchidan, biz vaznli grafiklar va minimal oraliq daraxtlar deganda nimani anglatishini tezda qayta ko'rib chiqamiz, chunki algoritmni tushunish uchun kerak bo'ladi.

Og'irlangan grafiklar va minimal kenglikdagi daraxtlar

Biz grafik nima ekanligini bilamiz - bu cho'qqilar va qirralarning to'plami. Shunda savol tug'ildi - chekka shunchaki chekkami? Javob, albatta, yo'q. Chet har doim ham chekka emas, balki unga og'irlik ham bog'langan bo'lishi mumkin - aniqrog'i, o'ziga xos qirrani olish uchun narx. Biz misolni qayta ishlatishimiz mumkin:

Tasavvur qilaylik, biz kichik yo'l sayohatiga ketyapmiz - biz ikkita yo'ldan birini tanlashimiz mumkin: uzoq yo'l yoki ko'prikdan o'tamiz. Biroq, ko'prik bizning manzilimizga uzoq yo'lni bosib o'tishdan ko'ra ancha qimmat.

Bizda faqat ikkita cho'qqi bor - hozirgi joylashuvingiz va boradigan joyingiz, shuning uchun eng arzon yo'lni tanlash ham minimal kenglikdagi daraxtga olib keladi.

Deykstra algoritmi

Endi biz vaznli grafiklar va minimal masofali daraxtlar tushunchasini tushunganimizdan so'ng, Dijkstra algoritmi haqida gapirishni boshlashimiz mumkin. Yuqorida aytib o'tilganidek, Dijkstra algoritmi berilgan ildizdan grafikdagi barcha cho'qqilarga eng qisqa yo'llarni topish uchun ishlatiladi. Qadamlar oddiy: Biz ikkita to'plamni saqlaymiz, bir to'plam eng qisqa yo'l daraxtiga kiritilgan cho'qqilarni o'z ichiga oladi, boshqa to'plam hali eng qisqa yo'l daraxtiga kiritilmagan cho'qqilarni o'z ichiga oladi. Algoritmning har bir bosqichida biz hali daraxtga kiritilmagan va manbadan minimal masofaga ega bo'lgan cho'qqini topamiz. Bu barcha tepaliklar eng qisqa yo'l daraxtiga kiritilgunga qadar amalga oshiriladi. Uning qanday ishlashini ko'rsatish uchun biz misol keltirishimiz mumkin - keling, bizda quyidagi grafik borligini tasavvur qilaylik: