Samarqand davlat universiteti raqamli texnologiyalar fakulteti dasturiy injiniring yo


Prima algoritimining C++ dasturlash tilidagi kodi



Download 1,33 Mb.
bet4/6
Sana26.02.2022
Hajmi1,33 Mb.
#471865
1   2   3   4   5   6
Bog'liq
kurs ishi namuna
Alphabet und erste Wörter, Elektrradio o lchashlar fanidan Davlat metro~, egri chiziqli integrallarning tadbiqi, ch8 0, 6sinf, tovar va pul munosabatlari, 1 dif amaliy, Учитель Юлдашева-WPS Office, Конструктивное расположение электрооборудование ДСП-100-19, Конструктивное расположение электрооборудование ДСП-100-19, 1.10-педиатрия-ва-болалар-гигиенаси, 1.10-педиатрия-ва-болалар-гигиенаси, 11-мавзу, pdf, ~$2.Тақдимот
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,33 Mb.

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




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

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
O’zbekiston respublikasi
guruh talabasi
nomidagi toshkent
o’rta maxsus
davlat pedagogika
texnologiyalari universiteti
toshkent axborot
xorazmiy nomidagi
Ўзбекистон республикаси
rivojlantirish vazirligi
pedagogika instituti
таълим вазирлиги
махсус таълим
haqida tushuncha
O'zbekiston respublikasi
tashkil etish
toshkent davlat
vazirligi muhammad
saqlash vazirligi
kommunikatsiyalarini rivojlantirish
respublikasi axborot
vazirligi toshkent
bilan ishlash
Toshkent davlat
uzbekistan coronavirus
sog'liqni saqlash
respublikasi sog'liqni
vazirligi koronavirus
koronavirus covid
coronavirus covid
risida sertifikat
qarshi emlanganlik
vaccination certificate
sertifikat ministry
covid vaccination
Ishdan maqsad
fanidan tayyorlagan
o’rta ta’lim
matematika fakulteti
haqida umumiy
fanidan mustaqil
moliya instituti
fanining predmeti
pedagogika universiteti
fanlar fakulteti
ta’limi vazirligi