|
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.
Do'stlaringiz bilan baham: |
