Tekshirdi: Begimov O’ktam Toshkent 2023 Mavzu: Prima Deykstra algoritmi. Uni vaqt bo'yicha baholasho. Reja
Download 0.5 Mb.
|
- Bu sahifa navigatsiya:
- Foydalanilgan adabiyotlar.
|
#include #include #define V 9 int minDistance(int dist[], bool sptSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } void printSolution(int dist[]) { printf("Vertex \t\t Distance from Source\n"); for (int i = 0; i < V; i++) printf("%d \t\t %d\n", i, dist[i]); } void dijkstra(int graph[V][V], int src) { int dist[V]; bool sptSet[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; dist[src] = 0; for (int count = 0; count < V - 1; count++) { int u = minDistance(dist, sptSet); sptSet[u] = true; for (int v = 0; v < V; v++) if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } printSolution(dist); } int main() { int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; dijkstra(graph, 0); return 0; } Chiqish natijasi: Vertex manbadan masofa 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14 Ishlash vaqti Qirralari E va uchlari V bo'lgan grafikda Deykstra algoritmining ishlash vaqti chegaralari cheklar sonining funksiyasi sifatida ifodalanishi mumkin. |E|, va uchlari soni, belgilangan |V|, katta O belgisi yordamida. Murakkablik chegarasi asosan Q to'plamini ifodalash uchun foydalaniladigan ma'lumotlar strukturasiga bog'liq. Quyida yuqori chegaralarni soddalashtirish mumkin, chunki | | |E| har qanday grafik uchun bo‘ladi, lekin bu soddalashtirish ba’zi masalalarda boshqa yuqori chegaralar mavjudligini hisobga olmaydi |E| tutishi mumkin. Q cho'qqisining har qanday ma'lumotlar strukturasi uchun ish vaqtida bo'ladi. Qayerda va mos ravishda Q dagi pasaytirish tugmasi va minimal chiqarish operatsiyalarining murakkabliklari. Dijkstra algoritmining eng oddiy versiyasi Q cho'qqi to'plamini bog'langan ro'yxat yoki massiv sifatida, qirralari esa qo'shni ro'yxat yoki matritsa sifatida saqlaydi. Bunday holda, minimal ekstrakt Q ning barcha uchlari bo'ylab chiziqli qidiruvdir, shuning uchun ish vaqti Izohlar: 1) Kod eng qisqa masofani hisoblaydi, ammo yo'l to'g'risidagi ma'lumotni hisoblamaydi. Ota-onalar massivini yaratamiz, masofa yangilanganida ota-ona massivini yangilaymiz (masalan, primning bajarilishi kabi) va undan foydalanib, manbadan turli balandliklargacha eng qisqa yo'lni ko'rsatamiz. 2) Kod yo'naltirilmagan grafik uchun, xuddi shu dijkstra funktsiyasi yo'naltirilgan grafikalar uchun ham ishlatilishi mumkin. 3) Kod manbadan barcha vertikallarga eng qisqa masofani topadi. Agar bizni manbadan bitta maqsadgacha bo'lgan qisqa masofaga qiziqish bildirsa, tanlangan minimal masofa uchi nishonga teng bo'lganda biz halqa sindirishimiz mumkin (algoritmning 3.a qadam). 4) Amalga oshirishning vaqt murakkabligi - O (V ^ 2). Agar kirish grafigi qo'shni ro'yxat yordamida taqdim etilsa, uni ikkilik to'plash yordamida O (E log V) ga kamaytirish mumkin. Qarang qo'shnilik ro'yxati vakolatxonasi uchun Dijkstra ning Algoritm batafsil ma'lumot uchun. 5) Dijkstraning algoritmi og'irligi qirralari salbiy bo'lgan grafikalar uchun ishlamaydi. Salbiy vazn qirralariga ega grafikalar uchun Bellman-Ford algoritmidan foydalanish mumkin, yaqin orada biz uni alohida post sifatida ko'rib chiqamiz. Prim algoritmi grafika uchun barcha tugunlarni bog'laydigan va barcha tugunlarni bog'laydigan daraxtlar orasida eng kam xarajat keltiradigan daraxt bo'lgan minimal grafik daraxtini quradi . Biroq, MSTdagi har qanday ikkita tugun orasidagi yo'lning uzunligi asl grafikdagi ushbu ikki tugun orasidagi eng qisqa yo'l bo'lmasligi mumkin. MSTlar foydali bo'ladi, masalan, agar siz grafikadagi tugunlarni elektr energiyasini eng kam xarajat bilan ta'minlash uchun jismonan o'tkazmoqchi bo'lsangiz. Ikkala tugun orasidagi yo'l uzunligi eng maqbul bo'lmasligi muhim emas, chunki siz ularni bog'lab qo'yishingizni istaysiz. Dijkstra algoritmi ba'zi bir manbali tugunlardan boshlab eng qisqa yo'l daraxtini quradi. Qisqa yo'l daraxti - bu grafikadagi barcha tugunlarni qaytariladigan manba tuguniga bog'laydigan va har qanday yo'lning grafikadagi boshqa tugungacha bo'lgan uzunligi minimallashtirilgan xususiyatdir. Bu foydalidir, masalan, agar siz biron bir muhim muhim joyga etib borishga imkon beradigan darajada yo'l tarmog'ini qurmoqchi bo'lsangiz. Biroq, eng qisqa yo'l daraxti minimal daraxt bo'lishi kafolatlanmaydi va eng qisqa yo'lli daraxtning chekkalari xarajatlari MST narxidan ancha katta bo'lishi mumkin. Yana bir muhim farq algoritmlarning qaysi grafik turlari ustida ishlashiga bog'liq. Prim algoritmi faqat yo'naltirilmagan grafiklar ustida ishlaydi, chunki MST tushunchasi grafiklarning yo'naltirilmaganligini anglatadi. (Yo'naltirilgan grafikalar uchun "minimal tejamkorlik" deb nomlangan narsa bor, ammo ularni topish algoritmlari ancha murakkab). Dijkstraning algoritmi yo'naltirilgan grafikalarda yaxshi ishlaydi, chunki eng qisqa daraxt daraxtlarini chindan ham yo'naltirish mumkin. Bunga qo'shimcha ravishda, Dijkstra algoritmi salbiy qirralarni o'z ichiga olgan grafiklarda to'g'ri echimni ta'minlamaydi , Prim esa algoritmi bunga qodir. Men ko'rgan yagona farq shundaki, Prim algoritmi minimal xarajatlar chegarasini saqlaydi, Dijkstra algoritmi esa manba uchidan hozirgi verteksgacha bo'lgan umumiy xarajatlarni saqlaydi. Dijkstra sizga xarajatlar minimal bo'lishi uchun manba tugunidan maqsad tuguniga yo'l beradi. Ammo Prim algoritmi sizga barcha tugunlar ulanishi va umumiy xarajat minimal bo'lishi uchun minimal daraxtni beradi. Oddiy so'zlar bilan: Shunday qilib, agar siz bir nechta shaharlarni ulash uchun poezdni joylashtirmoqchi bo'lsangiz, siz Prim algosidan foydalanasiz. Ammo agar siz bir shahardan ikkinchisiga imkon qadar ko'proq vaqt tejashni istasangiz, Dijkstra algidan foydalangan bo'lar edingiz. Ikkalasi ham xuddi shunday umumiy algoritm yordamida bajarilishi mumkin: Inputs:
s: Starting vertex (any for Prim, source for Dijkstra) f: a function that takes vertices u and v, returns a number Generic(G, s, f) Q = Enqueue all V with key = infinity, parent = null s.key = 0 While Q is not empty u = dequeue Q For each v in adj(u) if v is in Q and v.key > f(u,v) v.key = f(u,v) v.parent = u Prim, pass f = w(u, v)va Dijkstra dovoni uchun f = u.key + w(u, v). Yana bir qiziq tomoni shundaki, Generic-dan yuqorida "Bread" birinchi qidirishni (BFS) amalga oshirishi mumkin, ammo bu haddan tashqari ko'p bo'lishi mumkin, chunki qimmat ustunlik navbati aslida talab qilinmaydi. Yuqoridagi umumiy algoritmni BFS-ga o'tkazish uchun, f = u.key + 1barcha og'irliklarni 1 ga bog'lash bilan bir xil (masalan, BFS A nuqtadan B ga o'tish uchun zarur bo'lgan minimal qirralarni beradi).
A = = (0,0,0,368,346,202)
min (368: 6, 346: 9, 202: 9) = 224/9
min (2331/3 : 11/3 , 144 : 5 , 224/9 : 4/9 ) = 284/5
min (19414/15 : 4 , - , 929/45 : 2/3 ) = 147/15
x1 = 28.8, x2 = 14.46, x3 = 0 F(X) = 65*28.8 + 66*14.46 + 81*0 = 2826 Xulosa Men bu mustaqil ishni bajarish jarayonida bir nechta maqolalarni ko’rib chiqdim. Prima-Deykstra algoritmi, grafikni bir-biriga ulashishni topishda ishlatiladi va juftliklar orqali o'tkaziladigan masofalar orqali yolg'iz birlashmalardan foydalanmayapti. Bu algoritm, yagona juftliklamaga ega bo'lgan minimum elementni ishlatadi. Prima-Deykstra algoritmi, juftliklari bitimlarni bir-biriga ulashishni topishda ham ishlatiladi. Prima-Deykstra algoritmi, grafikning kompleksligi bilan bog'liq bo'lgan ishlar uchun yaxshi natija bermaydi va bazi boshqa algoritmlardan yuqori tekshiruvlar ro'yxatida joy olmaydi. Bular, Prima-Deykstra algoritmi katta bo'lakorli grafiklarda tez-tez ishlatiladi. Masalan, temir yo'llar yoki kommunikatsiya tarmoqlari uchun juda qulay bo'lishi mumkin. Yuqorida aytib o'tganimizdek, ushbu algoritmlar o'zining katta ishbor bo'yicha bir necha juftliklar o'rnatilgan xohlaganlug'iga muvofiq yaxshi natijalarni topishga imkon beradi. Foydalanilgan adabiyotlar. Pro-prof.com Habr.com Studfile.net Ziyonet http://moodle32.lms.tpu.ru https://gptgo.ai Download 0.5 Mb. Do'stlaringiz bilan baham: 
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||