Grafada quyidagilar mavjud

Dijkstraning algoritmi (yoki Dijkstra-ning eng qisqa yo'lining birinchi algoritmi, SPF algoritmi), masalan, yo'l tarmoqlarini aks ettirishi mumkin bo'lgan grafikadagi tugunlar orasidagi eng qisqa yo'llarni topish algoritmi. Algoritm boshlang'ich tepadan, manbadan tortib, grafikadagi barcha boshqa nuqtalarga qadar eng qisqa yo'llar daraxtini yaratadi.

Dijkstraning algoritmi manbadan minimal masofaga ega bo'lgan tugunlar to'plamini qurish orqali bitta manbali tugundan eng qisqa yo'l daraxtini topadi.

Grafada quyidagilar mavjud:

algoritmda v yoki u bilan belgilanadigan uchlari yoki tugunlari.

ikkita tugunni bog'laydigan vaznli qirralar: (u, v) chekkani, w (u, v) esa uning og'irligini bildiradi. O'ngdagi diagrammada har bir qirraning og'irligi kul rang bilan yozilgan.

Algoritm bosqichlari

Manba uchidan tashqari barcha uchlik masofalarini = cheksizlikni o'rnating, manba masofasini = 0 o'rnating.

Manba uchini minimallashtirilgan navbatga (masofa, vertex) joylashtiring, chunki minimal ustunlikdagi navbatdagi taqqoslash uchlari masofalarga qarab bo'ladi.

Ustunlik satridan minimal masofada joylashgan verteksni pop (avval paydo bo'lgan vertex = manba).

"Hozirgi vertex masofa + chekka og'irligi

Agar paydo bo'lgan tepaga oldinroq tashrif buyurilgan bo'lsa, uni ishlatmasdan davom eting.

Xuddi shu algoritmni ustuvor navbat bo'sh bo'lmaguncha takrorlang.

Grafikadagi manba va vertexni berilgan holda, berilgan grafikdagi manbadan vertikalgacha bo'lgan eng qisqa yo'llarni toping. Berilgan G [] [] grafik massasining matritsasi, n grafikda uchlari yo'q, u boshlang'ich tugmasi.

Input

G[max][max]={{0,1,0,3,10},

   {1,0,5,0,0},

   {0,5,0,2,1},

   {3,0,2,0,6},

   {10,0,1,6,0}}

n=5

u=0

Output

Distance of node1=1

Path=1<-0

Distance of node2=5

Path=2<-3<-0

Distance of node3=3

Path=3<-0

Distance of node4=6

Path=4<-2<-3<-0

Izoh

[[[]] Qo'shni matritsadan C [] [] qiymat matritsasini yarating. C [i] [j] - bu i vertex j nuqtadan j tekisligiga o'tish xarajatlari. Agar i va j vertikal chiziqlar o'rtasida hech qanday chekka bo'lmasa, C [i] [j] cheksizlikdir.

Tashrif buyurilgan qator nolga tenglashtirildi.

for(i=0;i

   visited[i]=0;

Dastlab, manba uchining masofasi 0 deb qabul qilinadi. masofa [0] = 0;

for(i=1;i

visited[i]=0;

W balandligini tanlang, shunda masofa [w] minimal va tashrif buyurilgan [w] 0 bo'ladi. Tashrifni [w] ga 1 deb belgilang.

Qolgan uchlari manbadan eng qisqa masofani qayta hisoblang.

Faqat masofani qayta hisoblash uchun [] tashrif buyurilgan massivda 1 deb belgilanmagan uchlari hisobga olinishi kerak. ya'ni v har bir vertex uchun

if(visited[v]==0)

   distance[v]=min(distance[v],

   distance[w]+cost[w][v])

Example

#include

#include

using namespace std;

#define INFINITY 9999

#define max 5

void dijkstra(int G[max][max],int n,int startnode);

int main() {

   int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};

   int n=5;

   int u=0;

   dijkstra(G,n,u);

   return 0;

}

void dijkstra(int G[max][max],int n,int startnode) {

   int cost[max][max],distance[max],pred[max];

   int visited[max],count,mindistance,nextnode,i,j;

   for(i=0;i

      for(j=0;j

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

      cost[i][j]=INFINITY;

   else

      cost[i][j]=G[i][j];

   for(i=0;i

      distance[i]=cost[startnode][i];

      pred[i]=startnode;

      visited[i]=0;

   }

   distance[startnode]=0;

   visited[startnode]=1;

   count=1;

   while(count

      mindistance=INFINITY;

      for(i=0;i

         if(distance[i]

         mindistance=distance[i];

         nextnode=i;

      }

      visited[nextnode]=1;

      for(i=0;i

         if(!visited[i])

      if(mindistance+cost[nextnode][i]

         distance[i]=mindistance+cost[nextnode][i];

         pred[i]=nextnode;

      }

      count++;

   }

   for(i=0;i   if(i!=startnode) {

      cout<<"\nDistance of node"<

      cout<<"\nPath="<

      j=i;

      do {

         j=pred[j];

         cout<<"<-"<

      }while(j!=startnode);

   }

}

2- Savol

*Pragrammer Irisboyev Asadbek

*Dastur yozilgan vaqti: 03.06.2020

* Maqsad: Ikki o'lchovli massiv - CRAMER QO'LLANIShidan foydalanib chiziqli tenglama tizimi

Chiziqli algebrada Kramer qoidasi chiziqli tenglamalar sistemasini yechish uchun ifoda beradigan teoremadir.

noyob echimlar mavjud bo'lgan hollarda noma'lum bo'lgan ko'plab tenglamalar. Yechim, bilan ifodalanadi

(kvadrat) koeffitsientli matritsani va undan ustunlarni o'ng vektorga almashtirish orqali olingan matritsalarni aniqlovchi

tenglamalarning qo'l tomonlari

C ++ dasturini yarating, bu foydalanuvchiga tanlovni CRAMER QOIDALARI yoki QUIT (faqat) ni kiritishni taklif qiladi. Agar foydalanuvchi tanlov1-ni tanlasa,

dastur foydalanuvchidan 2 o'lchovli massivdan foydalanib Cramer tenglamasi uchun qiymat kiritishni va aniqlovchilarni ishlov berishni so'raydi

quyida foydalanuvchi tomonidan belgilangan funktsiyadan foydalangan holda koeffitsient matritsasi.

#include
	#include
	#include
	using namespace std;
	const int row=2;
	const int col=3;
	int deter1(int list[][col],int size);
	// jarayon aniqlovchi D, aniqlovchi D ni qaytaradi va D koeffitsientli matritsani ko'rsatadi
	int deter2(int list[][col],int size);
	// jarayon aniqlovchi Dx, aniqlovchi Dxni qaytaradi va Dx koeffitsient matritsasini namoyish etadi
	int deter3(int list[][col],int size);
	// jarayon aniqlovchi Dy, Dy determinantini qaytaradi va Dy koeffitsient matritsasini namoyish etadi
	void equation1(int list[][col],int rsize);
	// 2 o'lchovli massivdagi jarayon qiymati va kremmerlar tenglamasi
	void choiceMenu(int ch);// 1 yoki 2 jarayonni tanlash, switch case bayonidan foydalanib
	void cramer(int d,int dx,int dy);// ishlov berish va displey kremining eritmasi
	void Menu();// asosiy menyuni namoyish etish
	char fexit();// belgi qiymatini qaytaradigan chiqib ketish
	void tryAgain();// foydalanuvchidan yana urinib ko'rishni so'rang
	void main()
	{
	int ans;
	do{
	Menu();
	cin>>ans;
	}while(ans<1||ans>2);
	choiceMenu(ans);
	tryAgain();
	cout<
	}//end main
	////////////////////////////////////////////////////////////////////
	// Menyu displeyi FUNCTION
	////////////////////////////////////////////////////////////////////
	void Menu()
	{
	cout << "==========MENU==========" << endl;
	cout << "[1] Cramer's Rule" << endl;
	cout << "[2] Exit" << endl;
	cout << "=========================" << endl;
	cout << " Tanlovingizni kiriting : ";
	}
	////////////////////////////////////////////////////////////////////
	// Menyuni tanlashga ishlov berish FUNCTION
	////////////////////////////////////////////////////////////////////
	void choiceMenu(int ch)
	{
	int eq[row][col];
	int size = row;
	switch (ch)
	{
	case 1:
	equation1(eq,size);
	break;
	case 2:
	fexit();
	break;
	}
	}
	////////////////////////////////////////////////////////////////////
	// FUNCTIOn chiqish
	////////////////////////////////////////////////////////////////////
	char fexit()
	{
	char choice;
	do
	{
	cout << " Haqiqatan ham chiqib ketmoqchisiz [y/n]? ";
	cin >> choice;
	if (toupper(choice)=='Y')
	cout << " To'xtatish dasturi ..." << endl;
	exit(0);
	else if(toupper(choice)=='N')
	main();
	}
	while(!(toupper(choice)=='Y'||toupper(choice)=='N'));
	}
	////////////////////////////////////////////////////////////////////
	// FUNCTION tenglamasini qayta ishlash
	////////////////////////////////////////////////////////////////////
	void equation1(int list[][col], int rsize)
	{
	int d, dx, dy, r, c;
	system("cls");
	cout << " Ushbu dastur 2-darajali Determinantlarni echishda Kramer qoidalaridan foydalanadi ." << endl
	<< " D, Dx va Dy uchta aniqlovchi vositalarni o'rnatish va baholashdan boshlaymiz ." << endl << endl
	<< "Misol uchun, x - 2y = 4 sifatida kiritilishi kerak 1 -2 4" << endl << endl;
	system("pause");
	system("cls");
	cout << " Yana x - 2y = 4, 1 -2 4 sifatida kiritilishi kerak" << endl;
	// Kirish uchun pastadir
	for(r = 0; r < rsize; r++)
	{
	cout << " Tenglamani kiriting " << r+1 << ": ";
	for (c = 0; c < col; c++)
	{
	cin>>list[r][c];
	}
	}
	cout << endl;
	// Ko'rsatish (2 o'lchovli shakl) )
	cout << " Siz kiritdingiz (2 o'lchovli qatordan foydalangan holda) )" << endl;
	for(r = 0; r < rsize; r++)
	{
	for (c = 0; c < col; c++)
	{
	cout << setw(5) << list[r][c];
	}
	cout << endl;
	}
	cout << endl;
	// Kramer tenglamasini ko'rsating
	// x + y = k ( y ijobiy bo'lsa)
	// x - y = k ( agar manfiy bo'lsa )
	cout << " Kramer tenglamasi : " << endl;
	for(r = 0; r < rsize; r++)
	{
	if(list[r][1]>=0)
	cout << setw(5) << list[r][0] << "x + " << list[r][1] << "y = " << list[r][2] << endl;
	else
	cout << setw(5) << list[r][0] << "x - " << (list[r][1]) * -1 << "y = " << list[r][2] << endl;
	}
	cout << endl;
	// Determinantni hisoblang
	// Agar d == 0 bo'lsa, Kramer qoidasini bajarmaydi .
	// Aks holda, Dx va Dy determinantlarini hisoblab chiqadi, so'ng eritmani namoyish etadi.
	d = deter1(list,rsize);
	cout << "Determinant D = " << d << endl << endl;
	if (d==0)
	cout << " Kramer qoidasi bajarilmaydi ." << endl;
	else
	{
	dx = deter2(list, rsize);
	cout << "Determinant Dx = " << dx << endl << endl;
	dy = deter3(list, rsize);
	cout << "Determinant Dy = " << dy << endl << endl;
	cramer(d,dx,dy);
	}
	}
	////////////////////////////////////////////////////////////////////
	// D aniqlovchi vosita FUNCTION
	////////////////////////////////////////////////////////////////////
	int deter1(int list[][col],int size)
	{
	int v1 = list[0][0] * list[1][1];
	int v2 = list[1][0] * list[0][1];
	cout << "D is: " << endl;
	for (int r = 0; r < size; r++)
	cout << setw(5) << list[r][0] << setw(5) << list[r][1] << endl;
	return (v1 - v2);
	}
	////////////////////////////////////////////////////////////////////
	// Dx Determinant funktsiyasi FUNCTION
	////////////////////////////////////////////////////////////////////
	int deter2(int list[][col],int size)
	{
	int v1 = list[0][1] * list[1][2];
	int v2 = list[1][1] * list[0][2];
	cout << "Dx is: " << endl;
	for (int r = 0; r < size; r++)
	cout << setw(5) << list[r][1] << setw(5) << list[r][2] << endl;
	return (v1 - v2);
	}
	////////////////////////////////////////////////////////////////////
	// Dyeterminant bo'yoqqa ishlov berish funktsiyasi
	////////////////////////////////////////////////////////////////////
	int deter3(int list[][col],int size)
	{
	int v1 = list[0][0] * list[1][2];
	int v2 = list[1][0] * list[0][2];
	cout << "Dy is: " << endl;
	for (int r = 0; r < size; r++)
	cout << setw(5) << list[r][0] << setw(5) << list[r][2] << endl;
	return (v1 - v2);
	}
	////////////////////////////////////////////////////////////////////
	// Kramer qoidalarini ko'rsatish funktsiyasi
	////////////////////////////////////////////////////////////////////
	void cramer(int d,int dx,int dy)
	{
	double x, y;
	x = (double)dx/(double)d;
	y = (double)dy/(double)d;
	cout << "x = " << dx << "/" << d << " = " << x << endl;
	cout << "y = " << dy << "/" << d << " = " << y << endl;
	cout << "The solution is (" << x << "," << y << ")" << endl;
	}
	////////////////////////////////////////////////////////////////////
	// Qayta urinib ko'ring FUNCTION
	////////////////////////////////////////////////////////////////////
	void tryAgain()
	{
	char c;
	do
	{
	cout << "Would you like to try again [y/n]? ";
	cin >> c;
	if (toupper(c)=='Y')
	main();
	else if (toupper(c)=='N')
	fexit();
	else
	cout << "Invalid value." << endl;
	}
	while(!(toupper(c)=='Y'||toupper(c)=='N'));
	}

Teorema 1.1. (Bellmanning optimizm printsipi)

Har bir t = 0, 1, 2,. . .

Bu printsipial jihatdan cheksiz davr optimallashtirish muammosini ikki davrli optimallashtirish muammosiga qisqartiradi. Ammo bu butun hikoya emasmi? Biz aslida optimizatsiyani qanday hal qilamiz?

Bellman tenglamasidan qo'limizdan kelganini siqib chiqaring.

Biz qisman derivativlarni pastki skriptlardan foydalangan holda belgilaymiz. Yulduz ustuni eng maqbulini bildiradi.

Keyin o'qilgan birinchi buyurtma sharti

Optimallik printsipi