Mustqil ishi

Kruskal algoritmi

Kruskal algoritmi. Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan. Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi. Vazni 6 ga tеng bo’lgan to’rtta tomondan ikkitasini qoldiramiz. Natijada qaysi ikki tomonning qoldirilishiga bo?liq holda J yoki Z rasmlarda ifodalangan MOD lardan biriga ega bo’lamiz.

a) b)
v) g)

d) e)
j) z)

Quyida ushbu algoritm matnini kеltiramiz. Bunda Е bilan grafdagi tomonlar soni, N bilan tugunlar soni ifoddalangan:
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 graph[], vector &edges, int v) {
// 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 mst;
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 graph[4];
vector edges;
// 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:
F* = 12218

X* = (0; 0; 149)

Foydalanilgan Adabiyotlar

Исроилов М.И. «Ҳисоблаш методлари»: -Т:Ўқитувчи, 2000 й.
Самарский А.А. «Введение в численные методы»: –М: Наука, 1987 й.
Бахвалов Н.С. «Численные методы»: -М: Наука.1987 й.
https://kompy.info/algoritmlar.html?page=95