Samarqand davlat universiteti raqamli texnologiyalar fakulteti dasturiy injiniring yo


Prima algoritimining C++ dasturlash tilidagi kodi



Download 1,31 Mb.
bet5/8
Sana08.01.2022
Hajmi1,31 Mb.
#330314
1   2   3   4   5   6   7   8
Bog'liq
Asror Qobulov

Prima algoritimining C++ dasturlash tilidagi kodi

Quyida Primaning algoritimining C++ dasturlash tilida amalga oshirilganligini ko’rishimiz munkin. Grafni ko’rsatish uchun qo’shnilik matritsa ishlatilgan bulsada , ushbu algoritm samaradorligini oshirish uchun qo’shnilik ro’yxati yordamida ham alamga oshirilishi mumkin.

#include

#include

using namespace std;
#define INF 9999999

//grafdagi uchlar soni

#define V5

//qo’shnilik matritsasini ifodalash uchun

//5x5 o’lchamdagi ikki o’lchamli massiv yaratish

int G[V][V]={

{0, 9, 75, 0, 0 },

{9, 0, 95, 19, 42 },

{75, 95, 0, 51, 66 },

{0, 19, 51, 0, 31 },

{0, 42, 66, 31, 0 }

};

int main() {


int no_edge; // qirralar soni

// tanlangan uchni kuztish uchun massiv yaratish

int selected[V];

//dastlab false qiymat berish

memset ( selected, false, sizeof( selected) );

//qirralar soniga 0 berish

no_edge = 0;

selected[0] = true;

int x; //qator raqami

int y; //ustun raqami

//qirra va og’irlikni chop etish

cout<<”Qirra”<<”:”<<”Masofa”;

cout<

while(no_edge < V - 1) {


int min = INF;

x = 0;


y = 0;

for(int i = 0 ; i < V ; i++) {

if(selected[i])

{

for(int j = 0; j < V; j++)



{

if(!selected[j] && G[i][j])

{

if(min > G[i][j])



{

min = G[i][j];

x = i;

y = j;


}

}

}



}

}

cout << x << ” - ” << y <<” : “ <

cout << endl ;

selected[y] = true ;

no_edge++;

}

return 0;



}

18-rasm dastur natijasi

Bizning so'nggi grafik algoritmimiz uchun biz ko'pincha onlayn o'yinlarni ishlab chiquvchilar va Internet-radio provayderlari duch keladigan muammoni ko'rib chiqishni taklif qilamiz. Muammo shundaki, ular axborot paketlarini eshitishlari mumkin bo'lgan har bir kishiga va har kimga samarali ravishda etkazishlari kerak. Bu o'yinlarda muhim ahamiyatga ega, chunki barcha futbolchilar har birining so'nggi harakatini bilishlari kerak. Bu Internet-radio uchun juda muhimdir, chunki tinglovchilar tinglayotgan qo'shiqni qayta tiklashlari uchun barcha ma'lumotlarni olishlari kerak. Translyatsiya muammosi tasvirlangan


19-rasm.


Uni to'g'ridan-to'g'ri sanab chiqish yo'li bilan hal qilishning bir necha yo'li mavjud. Muammoni yaxshiroq tushunish uchun biz ulardan boshlaymiz. Shuningdek, bu sizga oxir-oqibat taklif qiladigan echimni baholashga yordam beradi. Dastlab, eshittirish stantsiyasida ba'zi tinglovchilarga etkazilishi kerak bo'lgan ba'zi ma'lumotlar mavjud. Eng oddiy echim - barcha tinglovchilar ro'yxatini saqlash va ularga shaxsiy xabarlarni yuborish. 9-rasmda transmitter va bir nechta tinglovchilarga ega bo'lgan kichik tarmoq ko'rsatilgan. Birinchi yondashuvdan foydalanib, har bir xabarning to'rt nusxasi yuborilishi kerak. Eng kam xarajatli yo'l ishlatilayotgan deb taxmin qilsak, keling, har bir yo'riqnoma bir xil xabarlarni yuborish uchun qancha vaqt ketishini ko'rib chiqaylik.

Teleradiokompaniyaning barcha xabarlari A routeridan o'tadi, shuning uchun har birining to'rt nusxasini "ko'radi". Router C allaqachon ulardan birini "ko'radi", ammo B va D uchun bu raqam uchta, chunki 1, 2 va 3 tinglovchilarning eng qisqa yo'llari ular orqali o'tadi. Bu juda katta miqdordagi trafikni keltirib chiqaradi.

Qattiq kuch ishlatish usuli shundan iboratki, radioeshittirish stantsiyasi xabarning bitta nusxasini yuboradi va marshrutizatorlarga o'zlarini yanada tahlil qilishga imkon beradi. Bunday holda, eng oddiy echim nazoratsiz toshqin deb nomlangan strategiya bo'ladi. Bu shunday ishlaydi. Har bir xabar efirga uzatiladigan stantsiya va eng uzoq tinglovchi orasidagi chekka sonidan kattaroq yoki teng qiymatga o'rnatiladigan tilt (ingliz vaqtidan tortib tarjimonning eslatmasi) bilan beriladi. Har bir yo'riqnoma xabarning nusxasini oladi va ttl-ni birma-bir kamaytirib, barcha qo'shnilariga yuboradi. O'z navbatida, ular ham shunday qilishadi. Bu ttl qiymati nolga teng bo'lguncha davom etadi. Nazorat qilinmagan suv toshqini bizning birinchi strategiyamizga qaraganda ko'proq keraksiz xabarlarni keltirib chiqarmoqda.

Muammoning yechimi minimal uzunlikdagi daraxt daraxtini yaratishda yotadi. G = (V, E) grafigi uchun minimal T daraxtining rasmiy ta'rifi quyidagicha: T - V ning barcha vertikallarini birlashtirgan E ning asiklik doirasi.

Rasmda translyatsiya grafigining soddalashtirilgan versiyasi ko'rsatilgan va uning minimal uzunlikdagi daraxtining qirralari ta'kidlangan. Endi translyatsiya muammosini hal qilish uchun stantsiya xabarning bitta nusxasini tarmoqqa yuboradi. Routerlarning har biri uni yuboradigan manbani hisobga olmaganda, daraxtning bir qismi bo'lgan qo'shnisiga yuboradi. Bizning misolimizda A B, B xabarni C ga va D. D ni E ga yuboradi, bu xabar F ga uzatiladi va G ga yuboriladi. Hech qanday yo'riqnoma xabarning bir nechta nusxasini "ko'rmaydi". , lekin hamma tinglovchilar buni eshitishlari mumkin.

20-rasm.


Ushbu muammoni hal qilishda foydalanadigan algoritmga Primning algoritmi deyiladi. Bu "Xasis algoritmlar" deb nomlangan oilaga tegishli, chunki har bir qadamda tavsiya etilgan yo'llarning eng arzoni tanlanadi. Bunday holda, bu eng kam og'irlik bilan chekka bo'ylab harakatlanish bo'ladi. Bizning yakuniy vazifamiz Primning algoritmini amalga oshirishdir.

Daraxt yaratish uchun asosiy g'oya quyidagicha:

Toki T - taralayotgan daraxt

Daraxtga xavfsiz tarzda qo'shilishi mumkin bo'lgan chekkani toping

T ga yangi chekka qo'shing

Qo'lga olish "xavfsiz tarzda qo'shish uchun chekka toping". Xavfsiz chekkani vertikalni uzaygan daraxtdan uning tashqarisidagi tepalikka bog'laydigan chekka deb belgilaymiz. Bu daraxt har doim daraxt bo'lib qolishini va tsikllarga ega bo'lmasligini ta'minlaydi.

Prima algoritmini amalga oshirish uchun Python kodi Listing 2 da ko'rsatilgan. Dijkstra algoritmiga o'xshaydi, chunki ular ikkalasi ham o'sib boruvchi grafaga qo'shilish uchun navbatdagi tepalikni tanlash uchun ustuvor navbatdan foydalanadilar.


Download 1,31 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish