Algoritmlarni loyihalash



Download 442,57 Kb.
bet1/4
Sana13.04.2020
Hajmi442,57 Kb.
#44223
  1   2   3   4
Bog'liq
AL 6-hafta MTopshiriq javobi
umumiy geologiya, 9 amaliy, faoliyat va motivatsiya mavzusida re, Aholi 7-mavzu, Теор материал, Теор материал, russkiy 8, Boshlang’ich maktablarda tabiatshunoslik fan , yorugʻlik diodlar, yorugʻlik diodlar, @idum uz 9 sinflar uchun imtihon, @idum uz 9 sinflar uchun imtihon, xalqaro diplomatik munosabatlar, Мавзу №2 -1
O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI

UNIVERSITETI SAMARQAND FILIALI

"Telekominikatsion injiniring" fakulteti

" ALGORITMLARNI LOYIHALASH " fanidan



Guruh: 205

Bajardi: Berdiqulov Bexruz

Qabul qildi: Iskandarova Feruza

Samarqand – 2020

  1. Quyidagi nazariy savollarga javob bering

  1. Prim algoritmi ni tushuntirib bering

Ушбу алгоритм Роберт Прим томонидан 1957 йили ишлаб чиқилган. Унгача 1930 йили чех математиги Войтек Ярник (Vojtěch Jarník) томонидан, кеийнроқ 1959 йилда Эдгар Дейкстра (Edsger Dijkstra) томонидан ишлаб чикилган.

Минимал нархли дарахтлар склетини қуришнинг иккита кенг тарқалган усули мавжуд. Улардан бири Прим алгоритми. Бу алгоритмда дарахтлар склети «ўсадиган» ("вырастает") U қирралар тўплами қурилади. V={1, 2,..., n} бўлсин. Аввал U={1} бўлади. Алгоритмнинг ҳар бир қадамида минимал нархли қирра топилади, ундан кейин v қирра V\U тўпламдан U тўпламга ўтказилади. Бу жараён U тўплам V тўпламга тенг бўлгунча такрорланади.

Misol:

Мисол





Танланган тугунлар тўплами

(u,v) қирра

V/U

танланмаган тугунлар тўплами



Изоҳ



{ }




{A,B,C,D,E,F,G}

Бошланғич граф




{D}

(D,A)=5 V
(D,B) = 9
(D,E)= 15
(D,F) = 6

{A,B,C,E,F,G}

D тугундан бошлаймиз ABE и F лар D билан боқланган. A тугун — D га энг яқин бўлганлиги учун шу тугун олинади.



{A,D}

(D,B) = 9
(D,E)= 15
(D,F) = 6 
(A,B) = 7 V

{B,C,E,F,G}

D ёки A га энг яқин бўлган тугунни топамиз.  B - D  9,  A —D 7. E гача масофа 15, F —гача 6. F энг яқин тугун.



{A,B,D,F}

(B,C) = 8
(B,E)=7 V 
(D,B) = 9 цикл
(D,E)= 15
(F,E) = 8
(F,G)= 11

{C,E,G}






{A,B,D,E,F}

(B,C) = 8
(D,B) = 9 цикл
(D,E) = 15 цикл
(E,C) = 5 V
(E,G) = 9
(F,E) = 8 цикл
(F,G) = 11

{C,G}






{A,B,C,D,E,F}

(B,C) = 8 цикл
(D,B) = 9 цикл
(D,E) = 15 цикл
(E,G) = 9 V
(F,E) = 8 цикл
(F,G) = 11

{G}






{A,B,C,D,E,F,G}

(B,C) = 8 цикл
(D,B) = 9 цикл
(D,E) = 15 цикл
(F,E) = 8 цикл
(F,G) = 11 цикл

{ }

Минимал нархли дарахтлар склети қурилди. Бунда оғирлиги 39 бўлди.

Қуйида Прим алгоритми келтирилган.

1-дастур. Прим алгоритми

procedure Prim ( G: граф; var T: қирралар тўплами );

var


U: қирралар тўплами;

u, v: қирра;

begin

T:= ø;


U:= {1};

while U ≠ V do begin

энг кам нархли ва uU ва vV\U бўлган (u, v) қиррани топиш;

Т:= Т{u, V));

U:= U{v}

end


end; { Prim }

Юқоридаги граф учун қўшнилик матрицаси

A B C D E F G

0 7 0 5 0 0 0

7 0 8 9 7 0 0

0 8 0 0 5 0 0

5 9 0 0 15 6 0

0 7 5 15 0 8 9

0 0 0 6 8 0 11

0 0 0 0 9 11 0

Дастур

#include

using namespace std;

int main()

{

int a,b,u,v,n,i,j,ne=1;



int visited[10]={0}, min, mincost=0,cost[10][10];

int path[100]={0}; //ushbu massivda yulni tashkil qiladigan tugunlar yoziladi

int path_index=0;

cout<<"Tugunlar sonini kiriting "; cin>>n;

cout<<"Qushnilik matritsasini kiriting\n";

for(i=0;i

for(j=0;j

{

cin>>cost[i][j];



if(cost[i][j]==0)

cost[i][j]=999; // 999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе

}

visited[0]=1;



cout<<"\n";

while(ne < n)

{

for(i=0, min=999; i

for(j=0;j

if(cost[i][j]< min)

if(visited[i]!=0)

{

min=cost[i][j];



a=u=i;

b=v=j;


}

if(visited[u]==0 || visited[v]==0)

{

path[path_index]=b;



path_index++;

ne++;


mincost+=min;

visited[b]=1;

}

cost[a][b]=cost[b][a]=999;



}

cout<<"\n";

cout<<1<<" --> ";

for (int i=0;i

{

cout<


if (i ";

}

cout<<"\n Minimal narx "<

return 0;

}


Download 442,57 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




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

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