logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR

GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

242.1513671875 KB
Ko'chirib olish
“GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR” mavzusida Mundarija Floyd Algoritmlari ........................................................................................................................................ 3 Haddan tashqari algoritmlar ........................................................................................................................ 5 Qaytish bilan qidirish. Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish bilan qidirish sinov va xato usuli hisoblanadi ("keling, bu yo'nalishda borishga harakat qilaylik – bu ishlamaydi - qaytib keling va boshqasiga harakat qilaylik"). Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi sababli, algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l suyakka hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami grafikaning vertikalari soniga mos keladi, bu har bir Vertex uchun dastlabki tepadan masofani saqlaydi. ............................................ 5 To'lqin algoritmi. Kenglik qidiruviga asoslangan bu ortiqcha algoritm ikki bosqichdan iborat: to'lqin tarqalishi; teskari harakat. To'lqinning tarqalishi va hujayralar tashrif buyuradigan usulning qadam raqami bilan belgilanadigan kenglikdagi qidiruv mavjud. Qaytish jarayonida, oxirgi tepadan boshlab, minimal belgilar bilan hujayralarni kiritish yo'li bilan unga kiritilgan yo'lni tiklash (misol 45.4). Muhim xususiyat shundaki, tiklanish oxiridan boshlanadi (boshidan bu ko'pincha mumkin emas). .................... 6 Graflar ustida amallar ............................................................................................................................ 19 Xulosa ........................................................................................................................................................ 22 Foydalanilgan adabiyotlar ......................................................................................................................... 23 Foydalanilgan Internet saytlar ................................................................................................................... 23 Kirish Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma- ketligi algoritm deb ataymiz. Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o’rganadigan maxsus “Algoritmlar nazariyasi” bo’limi xam mavjud. Algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o’rganish bilan shug’ullanadi. Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo’llanilish sohasini aniqlash mumkin. Graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. Uni hisoblash va echimlarni topish uchun bir qancha algoritmlari mavjud. Eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznlarining yig’indisi minimal qiymatga ega. Qisqa (oddiy) zanjir geodezik zanjir ham aytiladi. Ushbu masalani adabiyotlarda bir nechta boshqa nomlanishi ham uchratish mumkin: minimal masofa masalasi, dilijans masalasi, qisqa masofa masalasi va boshqalar. Grafda eng qisqa masofani topish masalasi yo’naltirilgan, yo’naltirilmagan va aralash graflarda echimini aniqlash mumkin. Floyd Algoritmlari Ushbu algoritm ba'zan Floyd-Warshell algoritmi deb ataladi. Floyd-Warshell algoritmi 1962da Robert Floyd va Stiven Uorchell tomonidan ishlab chiqilgan graflarda algoritmdir. Grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga xizmat qiladi. Floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. Ushbu algoritm Dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki har qanday ikki ustun o'rtasida eng qisqa yo'llarnitopadi. Floyd algoritmida eng qisqa yo'llarning uzunligi hisoblangan NxN matritsasi ishlatiladi. A[i,j] elementi, agar u erda chekka (i, j) bo'lsa,yakuniy qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning yuqori qismidan masofaga teng. Floyd Algoritmning asosiy g'oyasi. I, j, k ning uchta tepasi bor va ular orasidagi masofa belgilanadi. Agar tengsizlik a[i,k]+a[k,j]<a[i,j] bajarilsa, i->j yo'lini i->k->j bilan almashtirish tavsiya etiladi. Qadam 0. A0 masofasining dastlabki matritsasini va S0 vertexlarining ketma-ketligini aniqlang. Har ikkala matritsaning har bir diagonali elementi 0ga teng, shuning uchun bu elementlarning hisob-kitoblarda ishtirok etmasligini ko'rsatmoqda. K = 1 ga ishonamiz. Asosiy qadam k. k satrini va k ustunini etakchi satr va etakchi ustun sifatida belgilang. Yuqorida tavsiflangan AK-1 matritsasining barcha elementlariga[i, j] almashtirishni ko'rib chiqamiz. Agar tengsizlik a[i,k]+a[k,j]<a[i,j], (i\ne k, j\ne k, i\ ne j) bajarilsa, unda quyidagi harakatlar amalga oshiriladi: A[i,k]+a[k,j] miqdori uchun A[i,j] elementining Ak-1 matritsasini almashtirish orqali Ak matritsasini yarating] ; k g6a SK-1 element s[i,j] matritsasini almashtirish orqali Sk matritsasini yarating. Shunday qilib, Floyd algoritmi n yinelemelerini qiladi, a matritsasining i- yinelemesinden keyin, bu yo'llar birinchi dan i-chigacha bo'lgan tepaliklardan o'tishi sharti bilan, har qanday ikki juftlik orasidagi eng qisqa yo'llarning uzunligini o'z ichiga oladi. Har bir iteratsiya bo'ylab barcha juftlar ko'chib o'tadi va ularning orasidagi yo'l i-tepa yordamida kamayadi. Misol 45.2. Floyd algoritmini namoyish qilish // Floyd algoritm funktsiyasi tavsifi void Floyd(int n, int **Graph, int **ShortestPath) { int i, j, k; int Max_Sum = 0; for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ ) Max_Sum+= ShortestPath[i][j]; for ( i = 0 ; i < n ; i++) if ( ShortestPath[i][j] == 0 && i!=j) ShortestPath[i][j] = Max_Sum; for ( k = 0 ; k <n;k++) for ( i = 0 ; i < n; i++) if ((ShortestPath[i][k] + ShortestPath[k][j]) ShortestPath[i][j] = ShortestPath[i][k] ; Agar grafik yo'naltirilmagan bo'lsa, unda transformatsiyalar natijasida olingan barcha matritsalar nosimmetrik bo'lib, shuning uchun faqat asosiy diagonaldan yuqorida joylashgan elementlarni hisoblash kifoya. Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, unda bu algoritmning ishlash vaqti o(n3) buyrug'iga ega, chunki u bir-biriga biriktirilgan uchta tsiklni o'z ichiga oladi. Haddan tashqari algoritmlar Bulkhead algoritmlari, odatda, optimal yechim topish uchun qidiruv algoritmlari. Shu bilan birga, yechim asta-sekin ishlab chiqilgan. Bunday holda, odatda, daraxt variantlarining ustunlarini qidirish haqida gap boradi. Bunday ustunning tepalari oraliq yoki yakuniy variantlar bo'ladi va qovurg'alar variantlarni loyihalash yo'llarini ko'rsatadi.Labirintdagi eng qisqa yo'lni topish vazifasi misolida ustundagi qidiruv usullariga asoslangan juda ko'p algoritmlarni ko'rib chiqing. Muammo bayonoti. O'tish va o'tkazilmaydigan hujayralardan tashkil topgan labirint mxn o'lchamli a matritsasi bilan berilgan. Agar hujayra (i,j) o'tkazilsa, matritsaning elementi a[i,j]=0. Aks holda, a [i,j]=\infty.Hujayradagi (1, 1) hujayradagi (m, n) eng qisqa yo'lning uzunligini topish kerak.Aslida, qo'shni matritsa berilgan (faqat nollar abadiylik bilan almashtiriladi va birliklar nolga teng). Labirint-bu grafik.Ushbu vazifadagi variantlar daraxtining tepalari qafada boshlangan yo'llardir (1, 1). Qovurg'alar-bu yo'llarning dizayni yo'lini ko'rsatadi va k va k+1 uzunliklarining ikki yo'lini birlashtiradi, bu erda ikkinchi yo'l yana bir harakatning yo'lini birinchi marta qo'shib olinadi. Qaytish bilan qidirish. Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish bilan qidirish sinov va xato usuli hisoblanadi ("keling, bu yo'nalishda borishga harakat qilaylik – bu ishlamaydi - qaytib keling va boshqasiga harakat qilaylik"). Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi sababli, algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l suyakka hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami grafikaning vertikalari soniga mos keladi, bu har bir Vertex uchun dastlabki tepadan masofani saqlaydi. Hozirgi hujayra (algoritm boshida – hujayra (1, 1) ). Agar hozirgi hujayra uchun qo'shni qo'shni qo'shni bo'lsa, u yo'lda hali bormagan yo'lda yo'q bo'lsa, unda biz yo'lda qo'shni qo'shamiz va hozirgi hujayradan qo'shni tayinlaymiz, aks holda yo'lni olibtashlaymiz. Yuqoridagi tavsif, bu usulning nima uchun qaytib kelishi bilan busting deb atalishini aniq ko'rsatib beradi. Qaytish bu erda "Way out Way" operatsiyasi bilan mos keladi, bu esa yo'l uzunligini 1gakamaytiradi. Bulkhead bo'sh va orqaga qaytish uchun harakat qilganda tugaydi. Bunday holatda qaytib kelish uchun hech qanday joyyo'q. Way joriy yo'l, lekin ish jarayonida optimal yo'lni saqlash kerak. Algoritmni takomillashtirish quyidagicha amalga oshirilishi mumkin: yo'lning uzunligi OptimalWay uzunligidan kattaroq yoki teng bo'lishiga yo'l qo'ymang. Bunday holda, agar biror variant topilsa, u albatta maqbul bo'lmaydi. Umuman olganda, bunday takomillashtirish, hozirgi yo'l aniq bo'lmagan optimal holga kelganda, biz orqaga qaytishimiz kerak degan ma'noni anglatadi. Algoritmning bu yaxshilanishi ko'p hollarda bustni sezilarli darajada kamaytirishga imkon beradi. To'lqin algoritmi. Kenglik qidiruviga asoslangan bu ortiqcha algoritm ikki bosqichdan iborat: to'lqin tarqalishi; teskari harakat. To'lqinning tarqalishi va hujayralar tashrif buyuradigan usulning qadam raqami bilan belgilanadigan kenglikdagi qidiruv mavjud. Qaytish jarayonida, oxirgi tepadan boshlab, minimal belgilar bilan hujayralarni kiritish yo'li bilan unga kiritilgan yo'lni tiklash (misol 45.4). Muhim xususiyat shundaki, tiklanish oxiridan boshlanadi (boshidan bu ko'pincha mumkin emas). Misol 45.4. To'lqin algoritmini namoyish qilish Qidiruv usuli bilan kenglikda qidirish, odatda, ma'lumotni saqlash uchun zarur bo'lgan qo'shimcha xotirani talab qiladi, bu esa teskari yo'nalishda yo'lni qurish va tashrif buyurilgan tepaliklarni belgilash uchun zarurdir. Biroq, u tezroq ishlaydi, chunki u bir xil hujayradan bir martadan ko'proq tashrif buyurishdan butunlay chiqarib tashlanadi. Dijkstra algoritmi Dijkstra algoritmi eng qisqa yo’l algoritmi sifatida ham tanilgan. Bu grafning tugunlari orasidagi eng qisqa yo’lni topish uchun ishlatiladigan algoritm. Algoritm grafning barcha boshqa nuqtalaridan boshlang’ich manba cho’qqisidan eng qisqa yo’llar daraxtini yaratadi. U minimal kenglikdagi daraxtdan farq qiladi, chunki ikkita cho’qqi orasidagi eng qisqa masofa grafning barcha cho’qqilariga kiritilmasligi mumkin. Algoritm manbadan minimal masofaga ega bo’lgan tugunlar to’plamini qurish orqali ishlaydi. Bu erda Dijkstra algoritmi muammoni hal qilish va eng yaxshi echimni topish uchun greedy yondashuvdan foydalanadi. Grafdagi eng qisqa marshrutlar uchun ko’plab qidiruv algoritmlari bo’yicha, Habreda faqatgina Floyd-Worschall algoritmining ta’rifi topildi. Ushbu algoritm grafaning barcha vertikalari va ularning uzunligi o’rtasidagi eng qisqa yo’llarni topadi. Ushbu maqolada Dijkstra algoritmining ishlash printsipini tasvirlab beraman. Bu algoritm optimal yo’nalishlarni va ularning uzunligini ma’lum bir vertikal (manba) va grafning boshqa vertikalari orasida topadi. Dijkstra algoritmi faqat ijobiy og’irliklarga ega bo’lgan graf bilan ishlaydi. Algoritmni bajarayotganda, tugunlar orasidagi eng qisqa yo’lni topish uchun qirralarning og’irliklarini qo’shish kerak. Agar grafda salbiy og’irlik bo’lsa, algoritm ishlamay qoladi. Esda tutingki, tugunni "tashrif buyurilgan" deb belgilaganingizdan so’ng, tugunga boradigan joriy yo’l ushbu tugunga erishish uchun eng qisqa yo’ldir. Shuning uchun, agar sizda salbiy og’irliklar bo’lsa, umumiy og’irlik kamaytirilsa, bu bosqichni o’zgartirishi mumkin. Bundan tashqari, Dijkstra algoritmini tushunishda savol tug’iladi: bu BFSmi yoki DFSmi ? Xo’sh, u ham emas. Dijkstra algoritmi ustuvor birinchi algoritmdir. Biroq, BFS va DFS algoritmlari o’rtasida ustuvorlik DFS emas, balki BFS uchun ko’proq bo’ladi. Asosan, siz Dijkstra algoritmida BFS ning ba’zi muhim tuzilmalarini topishingiz mumkin, ammo rostini aytganda, bu BFS algoritmidan ancha ko’p. Deykstra algoritmini quydagi grafda ko’rib chiqsak. Algoritm bosqichma-bosqich ishlaydi - har bir bosqichda u bitta cho’qqiga "tashrif buyuradi" va teglarni qisqartirishga harakat qiladi. Algoritm barcha cho’qqilarga tashrif buyurilgandan so’ng tugaydi. Initializatsiya . A cho’qqi yorlig’ining o’zi 0 deb qabul qilinadi, boshqa cho’qqilarning teglari cheksizlikka o’rnatiladi. Bu a dan boshqa cho’qqilargacha bo’lgan masofalar hali ma’lum emasligini ko’rsatadi. Grafning barcha uchlari ko’rilmagan deb belgilangan. Algoritm bosqichi . Agar barcha cho’qqilarga tashrif buyurilgan bo’lsa, algoritm tugaydi. Aks holda, hali tashrif buyurmagan cho’qqilardan minimal yorlig’i bo’lgan u tepasi tanlanadi. Biz u oxirgi nuqta bo’lgan barcha mumkin bo’lgan marshrutlarni ko’rib chiqamiz. U dan chekkalari olib boradigan cho’qqilar bu cho’qqining qo’shnilari deyiladi. U ning har bir qo’shnisi uchun, tashrif buyurilgan deb belgilanganlardan tashqari, joriy u yorlig’i qiymatlari va u ni ushbu qo’shni bilan bog’laydigan chekka uzunligi yig’indisiga teng bo’lgan yangi yo’l uzunligini ko’rib chiqing. Qabul qilingan uzunlik qiymati qo’shnining yorlig’i qiymatidan kam bo’lsa, yorliq qiymatini qabul qilingan uzunlik qiymati bilan almashtiring. Barcha qo’shnilarni hisobga olib, biz tepalikni belgilaymiz u tashrif buyurgandek va algoritm qadamini takrorlang. Misol Rasmda ko’rsatilgan graf misolida algoritmning bajarilishini ko’rib chiqing. 1-cho’qqidan qolgan barcha nuqtalargacha bo’lgan eng qisqa masofalarni topish talab qilinsin. Doiralar cho’qqilarni, chiziqlar ular orasidagi yo’llarni (grafning qirralarini) ko’rsatadi. Doiralar cho’qqilarning raqamlarini ko’rsatadi, qirralarning tepasida ularning "narxi" - yo’lning uzunligi ko’rsatilgan. Har bir cho’qqi yonida qizil yorliq belgilanadi - bu cho’qqiga 1-cho’qqigacha bo’lgan eng qisqa yo’lning uzunligi. Birinchi qadam . Bizning misolimiz uchun Dijkstra algoritmidagi qadamni ko’rib chiqing. 1-vertex minimal yorlig’iga ega.2, 3 va 6 cho’qqilari uning qo’shnilaridir. 1- cho ’ qqining birinchi qo ’ shnisi o ’ z navbatida 2- cho ’ qqidir , chunki unga boradigan yo ’ lning uzunligi minimaldir . 1-cho’qqi orqali unga boradigan yo’l uzunligi 1- cho’qqi yorlig’i qiymati va 1-dan 2-gacha bo’lgan chekka uzunligi yig’indisiga teng, ya’ni 0 + 7 = 7. 2-cho’qqining joriy yorlig’i, cheksizlik, shuning uchun 2-cho’qqining yangi yorlig’i 7 ga teng. Biz shunga o’xshash operatsiyani 1-vertexning boshqa ikkita qo’shnisi - 3 va 6-chi bilan bajaramiz. 1-tugunning barcha qo’shnilari tekshiriladi. 1-cho’qqigacha bo’lgan joriy minimal masofa yakuniy hisoblanadi va qayta ko’rib chiqilmaydi (bu haqiqatan ham shunday ekanligi birinchi marta E. Dijkstra tomonidan isbotlangan ). Ushbu tepaga tashrif buyurilganligini belgilash uchun uni grafdan kesib o’ting. Ikkinchi qadam . Algoritm bosqichi takrorlanadi. Yana biz ko’rilmagan cho’qqilarning "eng yaqinini" topamiz. Bu 7 deb belgilangan 2-cho’qqi. Yana biz tanlangan cho’qqining qo’shnilarining teglarini kamaytirishga harakat qilamiz, ular orqali 2-cho’qqi orqali o’tishga harakat qilamiz. Vertex 2 ning qo’shnilari 1, 3 va 4 uchlaridir. 2 cho’qqisining birinchi (tartibda) qo’shnisi 1 cho’qqidir. Lekin u allaqachon tashrif buyurilgan, shuning uchun biz 1-cho’qqi bilan hech narsa qilmaymiz. 2-cho’qqining keyingi qo’shnisi 3-vertexdir, chunki u kirmagan deb belgilangan cho’qqilarning minimal yorlig’iga ega. Agar siz unga 2 dan o’tsangiz, unda bunday yo’lning uzunligi 17 ga teng bo’ladi (7 + 10 = 17). Ammo uchinchi cho’qqining joriy yorlig’i 9 ni tashkil etadi, bu 17 dan kichik, shuning uchun yorliq o’zgarmaydi. 2-cho’qqining yana bir qo’shnisi 4-cho’qqidir. Agar siz unga 2-chi orqali o’tsangiz, unda bunday yo’lning uzunligi 2-cho’qqigacha bo’lgan eng qisqa masofa va 2 va 4 cho’qqilar orasidagi masofa yig’indisiga teng bo’ladi, ya’ni , 22 (7 + 15 = 22) . 22<<math>\infty</math> bo’lgani uchun 4-cho’qqining yorlig’ini 22 ga o’rnatdik. 2-vertexning barcha qo’shnilari ko’rib chiqildi, biz unga bo’lgan masofani muzlatib qo’yamiz va tashrif buyurilgan deb belgilaymiz. Uchinchi qadam . Algoritmning qadamini 3-cho’qqini tanlab takrorlaymiz. Uni “qayta ishlash”dan so’ng biz quyidagi natijalarni olamiz: Keyingi qadamlar . Qolgan cho’qqilar uchun algoritmning qadamini takrorlaymiz. Bular mos ravishda 6, 4 va 5 uchlari bo’ladi. Algoritmning bajarilishini yakunlash . Algoritm boshqa cho’qqilarni qayta ishlash mumkin bo’lmaganda tugaydi. Bu misolda barcha cho’qqilar chizilgan, lekin har qanday misolda shunday bo’ladi deb o’ylash xatodir - agar ularga etib bo’lmasa, ya’ni graf uzilgan bo’lsa, ba’zi cho’qqilar chizilmagan holda qolishi mumkin. Algoritmning natijasi oxirgi rasmda ko’rinadi: 1 cho’qqidan 2 gacha bo’lgan eng qisqa yo’l 7, 3 gacha - 9, 4 - 20, 5 - 20, 6 – 11 bo ’ lishini ko ’ rishimiz mumkin . Grafdagi ma ’ lum bir manba tuguniga ega bo ’ lgan algoritm bu tugun bilan har bir boshqa o ’ rtasidagi eng qisqa yo ’ lni topadi . Bundan tashqari , bitta tugunning eng qisqa yo ’ llarini to ’ xtatish yo ’ li bilan bitta maqsadli tugunga maqsad tuguniga eng qisqa yo ’ l aniqlanganidan keyin algoritm aniqlandi . Masalan , agar graf tugunlari shaharlarni ifodalasa va chekka xarajatlari to ’ g ’ ridan - to ’ g ’ ri yo ’ l bilan bog ’ langan shaharlarning juftliklari o ’ rtasidagi masofani ifodalaydi ( oddiylik uchun , qizil chiroqlar , ishlamaydigan belgilar , pullik yo ’ llar va boshqa to ’ siqlarni e ’ tiborsiz qoldirish uchun ), Dijkstra algoritmi ishlatilishi mumkin Bir shahar va boshqa shaharlarning eng qisqa yo ’ lini topish . Qisqa yo ’ l algoritmining keng tarqalgan qo ’ llanilishi tarmoqni boshqarish protokollaridir , Shuningdek , Jonson kabi boshqa algoritmlarda ham subroutin sifatida qo ’ llaniladi . Dijkstra algoritmida musbat tamsay yoki haqiqiy sonlar bo’lgan etiketlar ishlatiladi, bu aniq zaif tartibga solingan. Qiziqarli tomoni shundaki, Dijkstra aniq belgilangan qisman tartibga ega bo’lgan va keyingi teglar (bir chekkadan o’tib ketganda keyingi yorliq) monotonik ravishda kamaymaslik sharti bilan aniqlangan teglardan foydalanish uchun umumlashtirilishi mumkin. Ushbu umumlashma umumiy Dijkstra qisqa yo’l algoritmi deb ataladi. Dijkstra algoritmini C++ dasturlash tilida ifodalanishi #include<iostream> #include<climits> using namespace std; int miniDist( int distance[], bool Tset[]) // minimal masofani topish { int minimum = INT_MAX,ind; for ( int k = 0 ;k < 6 ;k ++ ) { if (Tset[k] == false && distance[k] <= minimum) { minimum = distance[k]; ind = k; } } return ind; } void DijkstraAlgo( int graph[ 6 ][ 6 ], int src) // qo’shnilik matritsasi { int distance [ 6 ]; // har bir tugun uchun minimal masofani hisoblash uchun massiv bool Tset[ 6 ]; // Har bir tugun uchun tashrif buyurilgan va tashrif buyurilmagan belgilash uchun mantiqiy massiv for ( int k = 0 ; k < 6 ; k ++ ) { distance[k] = INT_MAX; Tset[k] = false; } distance[src] = 0 ; // Manba tepasi masofasi 0 ga o’rnatiladi for ( int k = 0 ; k < 6 ; k ++ ) { int m = miniDist(distance,Tset); Tset[m] = true; for ( int k = 0 ; k < 6 ; k ++ ) { // qo’shni vertex masofasini yangilash If ( ! Tset [k] && graph[m][k] && distance[m] != INT_MAX && distance[m] + graph[m][k] < distance[k]) distance[k] = distance[m] + graph[m][k]; } } cout << " Vertex\t\tManba cho’qqisidan masofa " << endl; for ( int k = 0 ; k < 6 ; k ++ ) { char str = 65 + k; cout << str << " \t\t\t " << distance[k] << endl; } } int main() { int graph[ 6 ][ 6 ] = { { 0 , 1 , 2 , 0 , 0 , 0 }, { 1 , 0 , 0 , 5 , 1 , 0 }, { 2 , 0 , 0 , 2 , 3 , 0 }, { 0 , 5 , 2 , 0 , 2 , 2 }, { 0 , 1 , 3 , 2 , 0 , 1 }, { 0 , 0 , 0 , 2 , 1 , 0 }}; DijkstraAlgo(graph, 0 ); return 0 ; } Chiqish Vertex Manbadan masofa A 0 B 1 C 2 D 4 E 2 F 3 Vaqtning murakkabligi Dijkstra algoritmining vaqt murakkabligi O(V^2) ga teng, bu erda V - grafdagi cho’qqilar soni. Biroq, agar kirish grafigi qo’shnilik ro’yxati (grafni ko’rsatish usuli) yordamida tasvirlangan bo’lsa, unda vaqt murakkabligini ikkilik to’p yordamida O(E log V) ga kamaytirish mumkin. Dijkstra algoritmining fazoviy murakkabligi O(V) ga teng, bu erda V - grafning umumiy cho’qqilari soni. Buning sababi shundaki, biz ushbu barcha uchlarni ro’yxatda chiqish sifatida saqlashimiz kerak. Graflar ustida amallar Graflar ustida sodda amallar. Graflar ustida turli amallar bajarish mumkin, masalan, graflarni birlashtirish, biriktirish, ko‘paytirish, grafni qismlarga ajratish vahokazo. Eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini keltirsa bo‘ladi. Bu amalni qo‘llash berilgan grafning uchlari to‘plamidan birorta element yo‘qotishni (olib tashlashni) anglatadi. Natijada uchlari soni bittaga kamaygan yangi graf hosil bo‘ladi. Albatta, bu amalni uchlari soni ikkitadan kam bo‘lmagan graflar uchun qo‘llash mumkin bo‘lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga insident bo‘lgan barcha qirralar (yoylar) ham olib tashlanadi. Eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini ham kiritish mumkin. Bu amalga ko‘ra berilgan grafning qirralari (yoylari) to‘plamidan birorta element yo‘qotiladi (olib tashlanadi). Berilgan grafdan qirrani (yoyni) olib tashlayotganda shu qirraga (yoyga) insident uchlarni grafda qoldirish ham yo‘qotish ham mumkin. Bu yerda vaziyatga qarab ish yuritiladi. Agar G graf karrali qirralarga ega bo‘lmasa, u holda uchlari G grafning barcha uchlaridan iborat bo‘lgan shunday yagona G graf mavjudki, G grafdagi barcha juft uchlar faqat va faqat G grafda qo‘shni bo‘lmagandagina qo‘shnidir. Bunday G graf berilgan G grafning to‘ldiruvchi grafi deb ataladi. Berilgan graf uchuun to’ldiruvchi grafni qurish jarayoni ham graflar ustida bajariladigan amallar qatoriga kiritish mumkin. G garf uchun to’ldiruvchi grafni qurish amalini qo’llash natijasida G graf hosil bo’ladi. Isbotlash mumkinki, G munosabat o’rinlidir. Ggarflar ustida shunday amallarni bajarish mumkinki, ular elementlari soni berilgan grafdagidan ko’proq bo’lgan boshqa garfalarning hosil bo’lishiga olib keladi. Bunday amallar qatoriga uchni qo‘shish amali yoki qirrani (yoyni) qo‘shish amalini kiritish mumkin. Grafga yangi uchni qo‘shish turlicha usul bilan amalga oshirilishi mumkin. Masalan, yangi v uchni berilgan grafga qo‘shish shu grafning v1 va v2 uchlariga insedent bo’lgan qandaydir u qirrasiga qo’shish orqaliquyidagicha ikki bosqichda bajarilishi mumkin: 1). U qirra berilgan grafdan olib tashlanadi; 2).hosil bo’lgan grafga ikkita qirralar: v va v1 uchlariga insedent u1 qirra hamda v va v2 uchlariga insedent qirra qo’shiladi. Teorema.Agargrafdagiharbiruchninglokaldarajasiikkidankichik bo‘lmasa, u holda bu graf siklgaega. Grafning bog‘lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari a va b uchlardan iborat marshrut topilsa, bu a vab uchlar bog‘langan deb, marshrutning o‘zi esa a va b uchlarni bog‘lovchi marshrut deb ataladi. Tabiiyki, agar qandaydir uchlarni bog‘lovchimarshrutbirorai uchdanbir Necha marta o‘tsa,uholdamarshrutningsiklikqisminiolibtashlab(bundasiklik qismning o‘rniga marshrutda faqat ai uch qoldiriladi) yana o‘shauchlarni bog‘lovchi oddiy zanjir ko‘rinishdagi marshrutni hosil qilish mumkin. Shuning uchun, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bo‘glangan bo‘ladi degan xulosagakelamiz. Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo‘lsa, u holda bu ikkita uch ekvivalent (bog‘langan) deyiladi. Bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentalari (qisqacha, komponentalari) deb ataluvchi bog‘lamli qismlarning birlashmasi deb qarash mumkin. Bu yerda berilgan graf bog‘lamlilik komponentalariga bo‘laklandi (ajratildi) deb aytish mumkin. Isbotlash mumkinki, har qanday graf o‘zining bog‘lamlilik komponentalarining diz’yunktiv birlashmasi sifatida ifodalanishi mumkin, bunda grafning bog‘lamlilik komponentalariga bo‘laklanishi bir qiymatli aniqlanadi. Keyingi ma’lumotlarni bayon etish uchun yoq tushunchasi zarur bo‘ladi. Tekislikda geometrik ifodalanuvchi grafni qaraymiz. Bu grafga tegishli bo‘lmagan (ya’ni grafning hech qaysi uchi bilan ustma-ust tushmaydigan va uning hech qaysi qirrasida yotmaydigan) biror A nuqtani hech qaysi nuqtasi grafga tegishli bo‘lmagan uzluksiz chiziq bilan tutashtirish mumkin bo‘lgan barcha nuqtalar to‘plami grafning Yoq tushunchasiga berilgan ta’rifga ko‘ra yoq grafning geometrik ifodalanishi yordamida tekislikning “qirqib” olinadigan qismidan iboratdir. Tekislikda geometrik ifodalanuvchi ixtiyoriy grafning hech bo‘lmaganda bitta yoqi bo‘lishi va uning bitta yoqi chegaraga ega emasligi (cheksizligi) o‘z-o‘zidan ravshandir. Eyler teoremasidan bir qator natijalar kelib chiqadi. Masalan, bu teoremadan foydalanib uni osonlik bilan bog‘lamli bo‘lmagan graflar uchun quyidagicha umumlashtirish mumkin. Tabiiyki, bog‘lamli grafdan qirrani yoki bir necha qirralarni olib tashlash natijasida hosil bo‘lgan graf bog‘lamli bo‘lishi ham bo‘lmasligi ham mumkin. Agar bog‘lamli grafdan qirrani olib tashlash amali grafning bog‘lamlilik xususiyatini buzsa, u holda bunday qirrani ajratuvchi qirra debataymiz. Ravshanki, berilgan bog‘lamli grafda ajratuvchi qirralar ko‘p bo‘lishlari mumkin. Ajratuvchi qirralar to‘plamining hech qaysi qism to‘plami elementlari ajratuvchi qirralar bo‘lmasa, bu qirralar to‘plamini kesim deb ataymiz. Grafdan kesimga tegishli qirralar olib tashlansa, natijada ikki bog‘lamli komponentalari bo‘lgan graf hosil bo‘lishi ravshandir. Agar kesim yagona qirradan iborat bo‘lsa, u holda bu qirra ko‘prik deb ataladi. Xulosa Xulosa qilib aytganda A lgoritm bilan ishlash barcha turdagi dasturlash tillarida ishlash uchun kerak b o' ladi . Algoritmsiz biror bir dasturlash tilida dastur yaratib bulmaydi . H ar bir dasturning dastlab algoritmini yaratib olish zarur . A gar biz dasturimizning ketma - ketligini bilmasak , u dastur biz uylagandan kuproq xajmni egallashi mumkin ekan . C ++ dasturlash tilida malumotlarni izlash , saralash, qayta ishlash kabi amallarni yuqorida kursatib utilganidagidek bir va ikki ulchovli massivlarda bajarilganini kurib bilim va kunikmalarga ega bo’ldiz. C++ dasturi strukturasi xaqida, belgilar bayoni, algoritm va dastur tushunchasi, malumotlarni kiritish va chiqarish operatorlari xamda dasturda ishlatiladigan toifalar, ifodalar va kunikmalarini ko’rib chiqdiz . Algoritmlash va dasturlash tillari buyicha yozilgan bir nechta kitoblar bilan tanishib chiqdiz va ulardan kerakli malumotlarni oldiz .Bu kurs ishida Graflarda eng qisqa masofani topish algoritmlarini bir nechtasini ko’rib chiqdik asosan Floyd va Dijkstra algoritmlari haqida malumotlar keltirildi. Graflar elementlarni, odamlarni va ob’ektlarni bog’lash uchun ishlatiladi va Dijkstra algoritmi grafdagi ikkita nuqta orasidagi eng qisqa masofani aniqlashda sizga yordam beradi. Deykstra algoritmi haqiqiy dunyoda juda muhim bo’lgani uchun uni to’g’ri o’rganish va tushunish yaxshiroqdir. Foydalanilgan adabiyotlar 1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV, “ALGORITMLAR” , «Fan va texnologiya» nashriyoti, 2018. 2. H.To’rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009 , 3. Akbaraliyev B.B., Yusupova Z.Dj. , “MA LUMOTLAR TUZILMASI‟ VA ALGORITMLAR”, Toshkent 2013 4. Toirov Sh.A., Raximov R.T., Karimov M.M ,” “ALGORITMGA KIRISH” fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY KO’RSATMA”, Samarqand 2015. 5. Avnindra Kanaujia “Heap Sort Algorithms: Full Explanation of Heap Sort Algorithm” November 17, 2017. Foydalanilgan Internet saytlar 1. www.codingeek.com 2. www.geeksforgeeks.org 3. www.wikipedia.org 4. www.programiz.com 5. www.tutorialspoint.com 6. www.educba.com 7. www.btechsmartclass.com 8. www.commonlounge.com 9. www.brilliant.org 10. www.medium.com 11. www.researchgate.net 12. www.upgrad.com 13. www.quora.com

“GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR” mavzusida Mundarija Floyd Algoritmlari ........................................................................................................................................ 3 Haddan tashqari algoritmlar ........................................................................................................................ 5 Qaytish bilan qidirish. Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish bilan qidirish sinov va xato usuli hisoblanadi ("keling, bu yo'nalishda borishga harakat qilaylik – bu ishlamaydi - qaytib keling va boshqasiga harakat qilaylik"). Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi sababli, algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l suyakka hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami grafikaning vertikalari soniga mos keladi, bu har bir Vertex uchun dastlabki tepadan masofani saqlaydi. ............................................ 5 To'lqin algoritmi. Kenglik qidiruviga asoslangan bu ortiqcha algoritm ikki bosqichdan iborat: to'lqin tarqalishi; teskari harakat. To'lqinning tarqalishi va hujayralar tashrif buyuradigan usulning qadam raqami bilan belgilanadigan kenglikdagi qidiruv mavjud. Qaytish jarayonida, oxirgi tepadan boshlab, minimal belgilar bilan hujayralarni kiritish yo'li bilan unga kiritilgan yo'lni tiklash (misol 45.4). Muhim xususiyat shundaki, tiklanish oxiridan boshlanadi (boshidan bu ko'pincha mumkin emas). .................... 6 Graflar ustida amallar ............................................................................................................................ 19 Xulosa ........................................................................................................................................................ 22 Foydalanilgan adabiyotlar ......................................................................................................................... 23 Foydalanilgan Internet saytlar ................................................................................................................... 23

Kirish Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma- ketligi algoritm deb ataymiz. Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o’rganadigan maxsus “Algoritmlar nazariyasi” bo’limi xam mavjud. Algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o’rganish bilan shug’ullanadi. Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo’llanilish sohasini aniqlash mumkin. Graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. Uni hisoblash va echimlarni topish uchun bir qancha algoritmlari mavjud. Eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznlarining yig’indisi minimal qiymatga ega. Qisqa (oddiy) zanjir geodezik zanjir ham aytiladi. Ushbu masalani adabiyotlarda bir nechta boshqa nomlanishi ham uchratish mumkin: minimal masofa masalasi, dilijans masalasi, qisqa masofa masalasi va boshqalar. Grafda eng qisqa masofani topish masalasi yo’naltirilgan, yo’naltirilmagan va aralash graflarda echimini aniqlash mumkin.

Floyd Algoritmlari Ushbu algoritm ba'zan Floyd-Warshell algoritmi deb ataladi. Floyd-Warshell algoritmi 1962da Robert Floyd va Stiven Uorchell tomonidan ishlab chiqilgan graflarda algoritmdir. Grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga xizmat qiladi. Floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. Ushbu algoritm Dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki har qanday ikki ustun o'rtasida eng qisqa yo'llarnitopadi. Floyd algoritmida eng qisqa yo'llarning uzunligi hisoblangan NxN matritsasi ishlatiladi. A[i,j] elementi, agar u erda chekka (i, j) bo'lsa,yakuniy qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning yuqori qismidan masofaga teng. Floyd Algoritmning asosiy g'oyasi. I, j, k ning uchta tepasi bor va ular orasidagi masofa belgilanadi. Agar tengsizlik a[i,k]+a[k,j]<a[i,j] bajarilsa, i->j yo'lini i->k->j bilan almashtirish tavsiya etiladi. Qadam 0. A0 masofasining dastlabki matritsasini va S0 vertexlarining ketma-ketligini aniqlang. Har ikkala matritsaning har bir diagonali elementi 0ga teng, shuning uchun bu elementlarning hisob-kitoblarda ishtirok etmasligini ko'rsatmoqda. K = 1 ga ishonamiz. Asosiy qadam k. k satrini va k ustunini etakchi satr va etakchi ustun sifatida belgilang. Yuqorida tavsiflangan AK-1 matritsasining barcha elementlariga[i, j] almashtirishni ko'rib chiqamiz. Agar tengsizlik a[i,k]+a[k,j]<a[i,j], (i\ne k, j\ne k, i\ ne j) bajarilsa, unda quyidagi harakatlar amalga oshiriladi: A[i,k]+a[k,j] miqdori uchun A[i,j] elementining Ak-1 matritsasini almashtirish orqali Ak matritsasini yarating] ; k g6a SK-1 element s[i,j] matritsasini almashtirish orqali Sk matritsasini yarating. Shunday qilib, Floyd algoritmi n yinelemelerini qiladi, a matritsasining i- yinelemesinden keyin, bu yo'llar birinchi dan i-chigacha bo'lgan tepaliklardan o'tishi sharti bilan, har qanday ikki juftlik orasidagi eng qisqa yo'llarning uzunligini o'z ichiga oladi. Har bir iteratsiya bo'ylab barcha juftlar ko'chib o'tadi va ularning orasidagi yo'l i-tepa yordamida kamayadi.

Misol 45.2. Floyd algoritmini namoyish qilish // Floyd algoritm funktsiyasi tavsifi void Floyd(int n, int **Graph, int **ShortestPath) { int i, j, k; int Max_Sum = 0; for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ ) Max_Sum+= ShortestPath[i][j]; for ( i = 0 ; i < n ; i++) if ( ShortestPath[i][j] == 0 && i!=j) ShortestPath[i][j] = Max_Sum; for ( k = 0 ; k <n;k++) for ( i = 0 ; i < n; i++) if ((ShortestPath[i][k] + ShortestPath[k][j]) ShortestPath[i][j] = ShortestPath[i][k] ; Agar grafik yo'naltirilmagan bo'lsa, unda transformatsiyalar natijasida olingan barcha matritsalar nosimmetrik bo'lib, shuning uchun faqat asosiy diagonaldan yuqorida joylashgan elementlarni hisoblash kifoya. Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, unda bu algoritmning ishlash vaqti o(n3) buyrug'iga ega, chunki u bir-biriga biriktirilgan uchta tsiklni o'z ichiga oladi.

Haddan tashqari algoritmlar Bulkhead algoritmlari, odatda, optimal yechim topish uchun qidiruv algoritmlari. Shu bilan birga, yechim asta-sekin ishlab chiqilgan. Bunday holda, odatda, daraxt variantlarining ustunlarini qidirish haqida gap boradi. Bunday ustunning tepalari oraliq yoki yakuniy variantlar bo'ladi va qovurg'alar variantlarni loyihalash yo'llarini ko'rsatadi.Labirintdagi eng qisqa yo'lni topish vazifasi misolida ustundagi qidiruv usullariga asoslangan juda ko'p algoritmlarni ko'rib chiqing. Muammo bayonoti. O'tish va o'tkazilmaydigan hujayralardan tashkil topgan labirint mxn o'lchamli a matritsasi bilan berilgan. Agar hujayra (i,j) o'tkazilsa, matritsaning elementi a[i,j]=0. Aks holda, a [i,j]=\infty.Hujayradagi (1, 1) hujayradagi (m, n) eng qisqa yo'lning uzunligini topish kerak.Aslida, qo'shni matritsa berilgan (faqat nollar abadiylik bilan almashtiriladi va birliklar nolga teng). Labirint-bu grafik.Ushbu vazifadagi variantlar daraxtining tepalari qafada boshlangan yo'llardir (1, 1). Qovurg'alar-bu yo'llarning dizayni yo'lini ko'rsatadi va k va k+1 uzunliklarining ikki yo'lini birlashtiradi, bu erda ikkinchi yo'l yana bir harakatning yo'lini birinchi marta qo'shib olinadi. Qaytish bilan qidirish. Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish bilan qidirish sinov va xato usuli hisoblanadi ("keling, bu yo'nalishda borishga harakat qilaylik – bu ishlamaydi - qaytib keling va boshqasiga harakat qilaylik"). Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi sababli, algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l suyakka hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami grafikaning vertikalari soniga mos keladi, bu har bir Vertex uchun dastlabki tepadan masofani saqlaydi.

O'xshashlar

Graflarda eng qisqa masofani topish algoritmlari
Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.
Panjaraning eng kichik vektorini va berilgan vektorga eng yaqin vektorini topish masalasining algoritmik jihatlari
Graflar ustida amallar
Deykstra Algoritmi