Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti Fan: Algrotimlarni loyihalash
Yüklə 455,21 Kb.
|
1 2
Otabek|
edgeCount=1
while edgeCount<=Е and includedCount<=N-1 do parent1=FindRoot(edge[edgeCount].start) parent2=FindRoot(edge[edgeCount].end) if parent1/parent2 then edge[edgeCount] ni MOD ga qo’shish includedCount= includedCount=1 Union(parent1,parent2) Enf if edgeCount= edgeCount+1 end while Algoritmning asosiy sikli edgeCount o’zgaruvchisining qiymati grafdagi tomonlar soni bilan tеnglashishi yoki includedCount o’zgaruvchisining qiymati MOD ni shakllantirish uchun еtarlicha tomonlar qo’shilganini ko’rsatgunga qadar ishlaydi (N tugunli garfning MOD i N-1 ta tomonga ega bo’lishi kеrak) . Bog'langan og'irlikdagi yo'naltirilmagan grafikdagi minimal kengayuvchi daraxt (yoki minimal oraliq daraxt ) bu grafikning mumkin bo'lgan minimal og'irlikka ega bo'lgan kengayuvchi daraxti bo'lib, bu erda daraxtning og'irligi uning qirralari og'irliklarining yig'indisidir. Kruskal algoritmi og'irlikdagi bog'langan yo'naltirilmagan grafikning minimal oraliq daraxtini qurish uchun samarali algoritmdir . Shuningdek, algoritm Shtayner muammosi uchun ba'zi bir taxminlarni topish uchun ishlatiladi [1] . Algoritm 1956 yilda Jozef Kraskal ( ing. ) tomonidan tasvirlangan , bu algoritm 1926 yilda Otakar Boruvka [en] tomonidan taklif qilingan Boruvka algoritmi bilan deyarli bir xil . Dastlab, joriy qirralar to'plami bo'sh qilib o'rnatiladi. Keyin, iloji bo'lsa, quyidagi operatsiya amalga oshiriladi: mavjud to'plamga qo'shilishi unda tsikl paydo bo'lishiga olib kelmaydigan barcha qirralardan minimal og'irlikning chekkasi tanlanadi va allaqachon mavjud to'plamga qo'shiladi. . Bunday chekkalar qolmaganda, algoritm tugallanadi. Berilgan grafikning barcha cho'qqilari va topilgan qirralari to'plamini o'z ichiga olgan pastki grafigi uning minimal og'irligi bo'lgan daraxtdir . Algoritmning batafsil tavsifini adabiyotlarda topish mumkin Kruskal algoritmi haqiqatan ham minimal vaznli daraxtni topadi, chunki bu grafik matroid uchun Rado-Edmonds algoritmining [3] alohida holati bo'lib , mustaqil to'plamlar qirralarning asiklik to'plamidir. C++ dasturlash tilida Kruskal xasis algoritmining kodi #include #include #include using namespace std; // class representing an Edge of a graph class Edge { public: int from; int to; int weight; Edge(int f, int t, int w) { from = f; to = t; weight = w; } }; // Subset class is used to detect cycle while adding an edge class Subset { public: int parent; int rank; }; // Function to find the set of element i int find(Subset subsets[], int i) { // Path compression if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } // Function to perform union of two sets of x and y void Union(Subset subsets[], int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); // Union by Rank if (subsets[xroot].rank < subsets[yroot].rank) { subsets[xroot].parent = yroot; } else if (subsets[xroot].rank > subsets[yroot].rank) { subsets[yroot].parent = xroot; } else { // If ranks are same, then make one as root and // increment its rank by one subsets[yroot].parent = xroot; subsets[xroot].rank++; } } void findPrintMST(vector // Sort the edges in ascending order of their weights sort(edges.begin(), edges.end(), [](const Edge& lhs, const Edge& rhs) { return lhs.weight < rhs.weight; }); // Stores the mst vector int e = 0; // Number of edges included in mst // Create v subsets, v is the number of vertices Subset *subsets = new Subset[(v * sizeof(Subset))]; // Initialise parent of all as itself and rank as 0 for (int i = 0; i < v; i++) { subsets[i].parent = i; subsets[i].rank = 0; } // One by one traverse all the edges for (int i = 0; i < edges.size(); i++) { // Find the set of vertices present on this edge int x = find(subsets, edges[i].from); int y = find(subsets, edges[i].to); // If the set is not same(that is, no cycle is formed) // Add this edge to mst if (x != y) { Edge curr(edges[i].from, edges[i].to, edges[i].weight); mst.push_back(curr); Union(subsets, x, y); e++; } else { // Discard the edge } // If all the vertices are included in MST, stop here if (e == v - 1) { break; } } // Print the mst for (int i = 0; i < mst.size(); i++) { cout<<"From "< } int main() { vector vector // Make the graph in given example Edge e1(0, 1, 5); Edge e2(0, 2, 8); Edge e3(1, 0, 5); Edge e4(1, 2, 10); Edge e5(1, 3, 15); Edge e6(2, 0, 8); Edge e7(2, 1, 10); Edge e8(2, 3, 20); Edge e9(3, 1, 15); Edge e10(3, 2, 20); graph[0].push_back(e1); graph[0].push_back(e2); graph[1].push_back(e3); graph[1].push_back(e4); graph[1].push_back(e5); graph[2].push_back(e6); graph[2].push_back(e7); graph[2].push_back(e8); graph[3].push_back(e9); graph[3].push_back(e10); // Edges in the graph edges.push_back(e1); edges.push_back(e2); edges.push_back(e4); edges.push_back(e5); edges.push_back(e8); // Find MST using Kruskal's Algorithm and print it findPrintMST(graph, edges, 4); return 0; } Foydalanilgan adabiyotlar https://dasturchi.uz/algorithm/algoritm-haqida-tushuncha2/ https://dasturchi.uz/algorithm/algoritm-algoritm-haqida-tushuncha/ https://ilyarm.ru/uz/lineinyi-vid-algoritma-tipy-algoritmov-lineinye-razvetvlyayushchiesya-ciklicheskie.html https://fayllar.org/1-mavzu-algoritm-tushunchasi-va-ulardan-foydalanish.html?page=2 https://arxiv.uz/ru/documents/slaydlar/informatika-va-at/algoritm-turlari-xossalari-berilish-usullari-algoritm-blok-sxema-shaklida-berilish-usuli Ustun asos elementlari (B) Dastlabki bosqichda biz aniqlagan asosiy elementlarni jadvalga o'tkazamiz: B1 = x4; B2 = x 5; B3 = x 6; Cb ustun elementlari Ushbu ustundagi har bir katak mos keladigan qatordagi asosiy o'zgaruvchiga mos keladigan koeffitsientga teng. Cb1 = 0; Cb2 = 0; Cb3 = 0; Maqsad funksiyasi qiymati Maqsad funksiyasining qiymatini elementlar bo'yicha Cb ustunini P ustuniga ko'paytirib, mahsulotlarning natijalarini qo'shib hisoblaymiz. Maksimal qiymat P = (Cb1 * P01) + (Cb11 * P2 + (Cb21 * P3 = (0 * 149) + (0 * 194) + (0 * 531) = 0; Har bir boshqariladigan o‘zgaruvchi bo‘yicha ballarni o‘zgaruvchi ustunidagi qiymatni Cb ustunidagi qiymatga elementlar bo‘yicha ko‘paytirish, mahsulotlar natijalarini yig‘ish va shu o‘zgaruvchi yordamida ularning yig‘indisidan maqsad funksiya koeffitsientini ayirish yo‘li bilan hisoblaymiz. Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) ) - kx1 = ((0 * 3) + (0 * 4) + (0 * 9) ) - 110 = -110; Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) ) - kx2 = ((0 * 3) + (0 * 4) + (0 * 9) ) - 110 = -110; Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) ) - kx3 = ((0 * 1) + (0 * 1) + (0 * 9) ) - 82 = -82; Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) ) - kx4 = ((0 * 1) + (0 * 0) + (0 * 0) ) - 0 = 0; Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) ) - kx5 = ((0 * 0) + (0 * 1) + (0 * 0) ) - 0 = 0; Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) ) - kx6 = ((0 * 0) + (0 * 0) + (0 * 1) ) - 0 = 0; Ustun asos elementlari (B) Oldingi iteratsiyaning hisob-kitoblari natijalari uchun biz o'zgaruvchini x5 bazasidan olib tashlaymiz va uning o'rniga x1 ni qo'yamiz. Boshqa barcha hujayralar o'zgarishsiz qoladi. Cb ustun elementlari Ushbu ustundagi har bir katak mos keladigan qatordagi asosiy o'zgaruvchiga mos keladigan koeffitsientga teng. Cb1 = 0; Cb2 = 110; Cb3 = 0; O'zgaruvchan o'zgaruvchilarning qiymatlari va P ustuni (Oldingi iteratsiya ma'lumotlari dastlabki ma'lumotlar sifatida olinadi) Barcha kataklarni faqat asosga kiritilgan o'zgaruvchiga mos keladigan nol bilan to'ldiring: (Ruxsat elementi o'zgarishsiz qoladi) x1,1 = 0; x3.1 = 0; Biz ruxsat beruvchi elementi bo'lgan qatorni oldingi jadvaldan joriy jadvalga o'tkazamiz, uning qiymatlarini ruxsat beruvchi elementga elementlar bo'yicha ajratamiz: Р2 = Р2 / х 2,1 = 194/ 4 = 48,5; х2,1 = х2,1 / х2,1 = 4/4 = 1; х2,2 = х2,2 / х2,1 = 4/4 = 1; х2,3 = х2,3 / х2,1 = 1/4 = 0,25; х2,4 = х2,4 / х2,1 = 0/4 = 0; х2,5 = х2,5 / х2,1 = 1/4 = 0,25; х2,6 = х2,6 / х2,1 = 0/4 = 0; Qolgan bo'sh katakchalar, ballar qatori va Q ustunidan tashqari, ruxsat elementiga nisbatan to'rtburchaklar usuli yordamida hisoblanadi: P1 = (P1 * x2,1) - (x1,1 *P2) / x2,1 = ((149 * 4) - (3 * 194)) / 4 = 3.5; Р3 = (Р3 * х2,1) - (х 3,1 * Р2) / х2,1 = ((531 * 4) - (9 * 194)) / 4 = 94.5; x1,1 = ((x1,1 * x2,1) - (x1,1 * x2,1)) / x2,1 = ((3 * 4) - (3 * 4)) / 4 = 0; х1,3 = ((х1,3 * х2,1) - (х1,1* х2,3)) / х2,1 = ((1 * 4) - (3 * 1)) / 4 = 0.25; х1,4 = ((х1,4* х2,1) - (х1,1* х2,4)) / х2,1 = ((1 * 4) - (3 * 0)) / 4 = 1; х1,5 = ((х1,5* х2,1) - (х1,1* х2,5)) / х2,1 = ((0 * 4) - (3 * 1)) / 4 = -0.75; х1,6 = ((х1,6 * х2,1) - (х1,1* х2,6)) / х2,1 = ((0 * 4) - (3 * 0)) / 4 = 0; х3,1 = ((х3,1 * х2,1) - (х3,1* х2,1)) / х2,1 = ((9 * 4) - (9 * 4)) / 4 = 0; х3,3 = ((х3,3 * х2,1) - (х3,1* х2,3)) / х2,1 = ((9 * 4) - (9 * 1)) / 4 = 6.75; х3,4 = ((х3,4 * х2,1) - (х3,1* х2,4)) / х2,1 = ((0 * 4) - (9 * 0)) / 4 = 0; х3,5 = ((х3,5* х2,1) - (х3,1* х2,5)) / х2,1 = ((0 * 4) - (9 * 1)) / 4 = -2.25; х3,6 = ((х3,6 * х2,1) - (х3,1* х2,6)) / х2,1 = ((1 * 4) - (9 * 0)) / 4 = 1; Maqsad funksiyasi qiymati Maqsad funksiyasining qiymatini elementlar bo'yicha Cb ustunini P ustuniga ko'paytirib, mahsulotlarning natijalarini qo'shib hisoblaymiz. maksimal qiymat P = (Cb1 * P01) + (Cb11 * P2 + (Cb21 * P3 = (0 * 3.5) + (110 * 48.5) + (0 * 94.5) = 5335; Cb1 = 82; Cb2 = 110; Cb3 = 0; х2,3 = 0; х3,3 = 0; Р1 =Р1 / х1,3 = 3,5 / 0,25 = 14; х1,1 = х1,1 / х1,3 = 0 / 0,25 = 0; х1,2 = х1,2 / х1,3 = 0 / 0,25 = 0; х1,3 = х1,3 / х1,3 = 0,25 / 0,25 = 1; х1,4 = х1,4 / х1,3 = 1 / 0,25 = 4; х1,5 = х1,5 / х1,3 = -0,75 / 0,25 = -3; х1,6 = х1,6 / х1,3 = 0 / 0,25 = 0; Qolgan bo'sh katakchalar, ballar qatori va Q ustunidan tashqari, ruxsat elementiga nisbatan to'rtburchaklar usuli yordamida hisoblanadi: P2 = (P2 * x1,3) - (x 2,3 * P1) / x1,3 = ((48.5 * 0.25) - (0.25 * 3.5)) / 0.25 = 45; Р3 = (Р3 * х1,3) - (х3,3 * Р1) / х1,3 = ((94.5 * 0.25) - (6.75 * 3.5)) / 0.25 = 0; х2,1 = ((х2,1 * х1,3) - (х2,3* х1,1)) / х1,3 = ((1 * 0.25) - (0.25 * 0)) / 0.25 = 1; х2,2 = ((х2,2 * х1,3) - (х2,3*х1,2)) / х1,3 = ((1 * 0.25) - (0.25 * 0)) / 0.25 = 1; х2,3 = ((х2,3 * х1,3) - (х2,3* х1,3)) / х1,3 = ((0.25 * 0.25) - (0.25 * 0.25)) / 0.25 = 0; х2,5 = ((х2,5 * х1,3) - (х2,3* х1,5)) / х1,3 = ((0.25 * 0.25) - (0.25 * -0.75)) / 0.25 = 1; х2,6 = ((х2,6 * х1,3) - (х2,3* х1,6)) / х1,3 = ((0 * 0.25) - (0.25 * 0)) / 0.25 = 0; х3,1 = ((х3,1 * х1,3) - (х3,3* х1,1)) / х1,3 = ((0 * 0.25) - (6.75 * 0)) / 0.25 = 0; х3,2 = ((х3,2 * х1,3) - (х3,3*х1,2)) / х1,3 = ((0 * 0.25) - (6.75 * 0)) / 0.25 = 0; х3,3 = ((х3,3 * х1,3) - (х3,3* х1,3)) / х1,3 = ((6.75 * 0.25) - (6.75 * 0.25)) / 0.25 = 0; х3,5 = ((х3,5 * х1,3) - (х3,3* х1,5)) / х1,3 = ((-2.25 * 0.25) - (6.75 * -0.75)) / 0.25 = 18; х3,6 = ((х3,6 * х1,3) - (х3,3* х1,6)) / х1,3 = ((1 * 0.25) - (6.75 * 0)) / 0.25 = 1; maksimal qiymat P = (Cb1 * P01) + (Cb11 * P2 + (Cb21 * P3 = (82 * 14) + (110 * 45) + (0 * 0) = 6098; Har bir boshqariladigan o‘zgaruvchi bo‘yicha ballarni o‘zgaruvchi ustunidagi qiymatni Cb ustunidagi qiymatga elementlar bo‘yicha ko‘paytirish, mahsulotlar natijalarini yig‘ish va shu o‘zgaruvchi yordamida ularning yig‘indisidan maqsad funksiya koeffitsientini ayirish yo‘li bilan hisoblaymiz. Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) ) - kx1 = ((82 * 0) + (110 * 1) + (0 * 0) ) - 110 = 0; Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) ) - kx2 = ((82 * 0) + (110 * 1) + (0 * 0) ) - 110 = 0; Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) ) - kx3 = ((82 * 1) + (110 * 0) + (0 * 0) ) - 82 = 0; Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) ) - kx4 = ((82 * 4) + (110 * -1) + (0 * -27) ) - 0 = 218; Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) ) - kx5 = ((82 * -3) + (110 * 1) + (0 * 18) ) - 0 = -136; Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) ) - kx6 = ((82 * 0) + (110 * 0) + (0 * 1) ) - 0 = 0; Boshqariladigan o'zgaruvchilarning baholari orasida salbiy qiymatlar mavjud bo'lganligi sababli, joriy jadval hali optimal echimga ega emas. Shuning uchun biz bazaga eng kichik salbiy bahoga ega o'zgaruvchini kiritamiz. Bazisdagi o'zgaruvchilar soni doimo doimiy bo'ladi, shuning uchun qaysi o'zgaruvchini bazadan olib tashlashni tanlash kerak, buning uchun biz Q ni hisoblaymiz. Q ustunining elementlari P ustunidagi qiymatlarni asosga kiritilgan o'zgaruvchiga mos keladigan ustunning qiymatiga bo'lish yo'li bilan hisoblanadi: Q1 = P1 / x1,5 = 14 / -3 = -4,67; Q2= P2 / x 2,5 = 45/1 = 45; Q3 = P3 / x 3,5 = 0 / 18 = 0; Javob:
X* = (0; 0; 149) Foydalanilgan Adabiyotlar Исроилов М.И. «Ҳисоблаш методлари»: -Т:Ўқитувчи, 2000 й. Самарский А.А. «Введение в численные методы»: –М: Наука, 1987 й. Бахвалов Н.С. «Численные методы»: -М: Наука.1987 й. https://kompy.info/algoritmlar.html?page=95 Yüklə 455,21 Kb. Dostları ilə paylaş:
|
1 2