Raqamli texnologiyalar

Deykstra algoritmi
Gollandiyalik olim Edsger Deykstra algoritmi dastlabki o'rnatilgan grafik tepasidan barcha eng qisqa yo'llarni topadi. Shu bilan birga, barcha kerakli ma'lumotlarga ega bo'lgan holda, masalan, bir shahardan boshqa har biriga yoki qaysi mamlakatlarga neft va shunga o'xshash narsalarni eksport qilish uchun qanday yo'llar ketma-ketligini yaxshiroq bilish mumkin

Ushbu algoritmning salbiy tomoni, ya'ni salbiy vaznli uchlar mavjud bo'lgan grafiklarni qayta ishlashning mumkin emasligi, masalan, ba'zi tizim sizning kompaniyangiz uchun foydasiz yo’llarni taqdim etsa, u bilan ishlash uchun siz Deykstra algoritmidan farqli usuldan foydalanishingiz kerak.

Algoritmning dasturiy ta'minotini amalga oshirish uchun ikkita qator kerak: mantiqiy visited-tashrif buyurilgan uchlar va raqamli distance haqida ma'lumotni saqlash uchun, topilgan eng qisqa yo'llar kiritiladi. Shunday qilib, G=(V, E) grafigi mavjud. Ko'p V kiritilgan uchi har bir, dastlab emas, balki tashrif buyurdi sifatida belgilangan, ya'ni.
Eng foydali yo'llar topilganligi sababli, distance grafning har bir elementida har qanday qisqa yo'ldan kattaroq raqam yoziladi (odatda bu raqam ckeksiz masofa deb ataladi, lekin dasturda, masalan, ma'lum bir ma'lumot turining maksimal qiymati ishlatiladi). Boshlang'ich nuqtasi sifatida s graf tanlanadi va unga nol yo'l beriladi: distance[s]=0, chunki s dan s ga hech qanday yo’l yo'q.
Bundan tashqari, barcha qo'shni uchlar (s ning qirralari mavjud) [ular t va u bo'lsin] va navbat bilan tekshiriladi, ya'ni marshrut masofasi s dan har biriga navbat bilan hisoblab chiqiladi:

distance [t]=distance [s]+ (s va t uchi orasidagi masofa)

distance[u] = distance[s]+ (s va u uchi orasidagi masofa)

Lekin u s bir yoki boshqa uchi bir necha yo'llari bor, deb ehtimol, shuning uchun distance massivi bunday uchiga yo'l o’zunligini qayta ko'rib chiqilishi kerak, keyin eng katta (optimal) qiymati e'tiborsiz va eng kichik uchiga mos tushadi.

S bilan bog'liq vertikallarni qayta ishlagandan so'ng, u tashrif buyurilgan deb belgilanadi: tashrif buyurilgan visited[s]=true, va eng uzun yo'l s dan minimal bo'lgani bilan urin almashadi. Endi, s dan u gacha bo'lgan yo'l s dan t ga qaraganda qisqaroq, shuning uchun u yuqori qismi o’rni almashadi, yuqorida tavsiflangan tarzda qo'shnilari s uchidan tashqari, barcha uchlar tekshiriladi. Bundan tashqari, u o'tgan deb belgilanadi: visited[u]=true, t ning yuqori qismi faol bo'lib qoladi va butun qirralar va uchlar uchun takrorlanadi. Deykstra algoritmi s tepasidan mavjud bo'lgan barcha uchlar tekshirilgunga qadar davom etadi.
Endi ma'lum bir ustunda biz algoritm ishini kuzatamiz, manba va boshqa barcha uchlar orasidagi eng qisqa yo'llarni topamiz. Quyidagi grafikning o'lchami (qirralari soni) 7 (|e|=7) va tartib (uchlar soni) 6 (|V|=6). Bu grafik, uning har bir qirrasi ma'lum bir raqamli qiymatga mos keladi, shuning uchun grafning qiymati bir juft uchlar orasida joylashgan qirralari soni bilan aniqlanmaydi.

V majmuasiga kiritilgan barcha uchlardan biz eng qisqa yo'llarni boshqa uchlarga topishimiz kerak bo'lgan birini tanlaymiz. 1 ning yuqori qismi bo'lsin. Birinchidan tashqari, barcha uchlarga dastlabki yo'l uzunligi cheksizlika teng va undan oldin-0,

1 va 3, 2 va 3, 1 va 5 (nol bilan) birinchi Uch qiymati: aniq 3 qo'shni yuqori (Uch 2, 3, 5), va ularga yo'l uzunligini hisoblash uchun, siz Uchlar orasidagi yotgan yoy uzunligni kiritish kerak:

2←1+0
3←4+0
5←2+0
Yuqorida aytib o'tilganidek, olingan qiymatlar faqat hozirgi vaqtda paydo bo'lgan "yaxshiroq" (kamroq) bo'lsa, uchlarga beriladi. Va uchta raqamning har biri cheksiz masofadan kam bo'lgani uchun, ular 1 uchidan 2, 3 va 5 uchlariga yo'lning uzunligini belgilaydigan yangi qiymatlarga ega bo’ladi.

Bundan tashqari, tashruf buyurgan uchni tashrif buyurilganidek belgilanadi, "tashrif buyurgan uchni" (qizil doira) bilan belgilab olamiz qo'shnilaridan biriga, ya'ni 2-uch yuqori qismiga o'tadi, chunki u ilgari tashrif buyurgan uchga eng yaqin.

2-uchning faqat bitta uch qo'shni emas (top 1-tashrif buyurdingizmi deb belgilangan), undan masofa 9 ga teng bo'lgan, lekin biz u yuqori 2 uchun undan bir yoy uzunligi bilan yuqori 4 tegishli qiymatini kiritish uchun zarur bo'lgan manba sammitida, yo'l uzunligini hisoblash kerak
4←1+9
"Qisqa" holatda (10 <∞) shart bajarilib 4-uchgacha bulgan masofa yangi qiymat oladi.

2-Uchga tashrif buyurishni to'xtatadi, shuningdek, top 1-tashrif buyurmaganlar ro'yxatidan olib tashlanadi. Endi 5-uchning yuqori qo'shnilari xuddi shu tarzda tekshiriladi va ularga masofa hisoblab chiqiladi.

3- uchning qo'shnilarini tekshirish haqida gap ketganda, xato qilish muhim emas, chunki 4-uch allaqachon tashruf buyirilgan va manbadan mumkin bo'lgan yo'llardan birining masofasi hisoblab chiqilgan. Agar siz 3-uchdan o'tib ketsangiz, yo'l 4+7=11 va 11>10 bo'ladi, shuning uchun yangi qiymat e'tibordan chetda qoladi, eslab qolainadi.

6-uch bilan o'xshash vaziyat. 1-uchidan unga eng yaqin yo'lning qiymati 10ga teng va u faqat 5-uchidan o'tib ketgan taqdirda olinadi.

Grafning barcha uchlari yoki manbadan mavjud bo'lgan barcha uchlarga tashrif buyurilgan deb belgilansa, Deykstra algoritmining ishi tugaydi va topilgan barcha yo'llar eng qisqa bo'ladi. Misol uchun, 1-uchi va boshqa barcha uchlarilar orasidagi eng maqbul masofalar ro'yxati ko'rib chiqiladi:
1→1=0
1→2=1
1→3=4
1→4=10
1→5=2
1→6=10
Deykstra algoritimi yordamida graf uchlari orasidagi eng yaqin yo'llarni topadigan dasturda grafigi ikki tomonlama bo'lmagan matritsa shaklida taqdim etiladi. Birliklarning o'rniga uchlar orasidagi masofa ko'rsatiladi, nol funksiyasi bir xil bo'ladi: qaysi uchlar orasida qirra yo'q yoki ular bor, lekin salbiy yo'naltirilgan.

C++ tilida dastur kodi

#include
using namespace std;
const int V=6;
//Deykstra algoritmi
void Deykstra( int GR[V][V], int st)
{
int distance[V], //Qushni uchlar orasidagi masofa
count, index, i, u, m=st+1;
bool visited[V];//Tashrif buyirilgan uch
for (i=0; i{
distance[i]=INT_MAX;
visited[i]=false;
}
distance[st]=0;
for (count=0; count{
int min=INT_MAX;
for (i=0; iif ( !visited[i] && distance[i]<=min)
{
min=distance[i]; index=i;
}
u=index;
visited[u]=true;
for (i=0; iif ( !visited[i] && GR[u][i] && distance[u]!=INT_MAX &&
distance[u]+GR[u][i] distance[i]=distance[u]+GR[u][i];
}
cout<<"\nBoshlang'ich uchdan, boshqa uchlargacha bo'lgan eng qisqa masofa:\t\n";
for (i=0; icout< "<else cout< "<}
//asosiy funksiya
int main()
{
int start, GR[V][V]={
{0, 1, 4, 0, 2, 0},
{0, 0, 0, 9, 0, 0},
{4, 0, 0, 7, 0, 0},
{0, 9, 7, 0, 0, 2},
{0, 0, 0, 0, 0, 8},
{0, 0, 0, 0, 0, 0}};
cout<<"\nBoshlang'ich uchni kiriting >> "; cin>>start;
Deykstra( GR, start-1);
return 0;
}

Dastur kodi tuzilgndan keyin men boshlang’ich grafning uchini birinchi uch deb oldim. Dastur testlab natijalarni oldim. Birinchi uchdan boshqa uchlargacha bulgan eng qisqa masofalarni natijasini chiqardi.



Dstur kodiga testlah natijaida Graf uchiga teng bulmagan uchni kirgizilsa. Natija yo’l mavjud emas deb kursatildi.


XULOSA
Xulosa qilib aytganda Algoritm bilan ishlash barcha turdagi dasturlash tillarida ishlash uchun kerak buladi. Algoritmsiz biror bir dasturlash tilida dastur yaratib bulmaydi. Xar bir dasturning dastlab algoritmini yaratib olish zarur. Agar biz dasturimizning ketma-ketligini bilmasak , u dastur biz uylagandan kuproq xajmni egallashi mumkin ekan. Men C++ dasturlash tilida malumotlarni izlash , saralash, qayta ishlash kabi amallarni yuqorida kursatib utilganidagidek bir va ikki ulchovli massivlarda bajarilganini kurib bilim va kunikmalarga ega buldim. Men C++ dasturi strukturasi xaqida, belgilar bayoni, algoritm va dastur tushunchasi, malumotlarni kiritish va chiqarish operatorlari xamda dasturda ishlatiladigan toifalar, ifodalar va kunikmalarga ega buldim. Algoritmlash va dasturlash tillari buyicha yozilgan bir nechta kitoblar bilan tanishib chiqdim va ulardan uzimga kerakli malumotlarni oldim. Men ushbu kurs ishni bajarib eng katta daraxt, eng qisqa va eng uzun yo‘l haqida tushunchaga ega bo‘ldim. Agar grafning markazidan boshqa biron uchigacha bo‘lgan oddiy zanjir eng uzun masofaga ega bo‘lsa, u holda bu zanjir radial oddiy zanjir, deb ataladi. Tabiiyki, grafning radiusi uning diametridan katta emas va graf bittadan ko’p markazga ega bo’lishi ham mumkin. Bundan tashqari, grafning barcha uchlari uning markaziy uchlari bo’lishi ham mumkin. Grafning markaziy uchlarini topish bilan bog’liq masalalar aholiga xizmat ko’rsatadigan qandaydir obyektning (kasalxona, maktab va shu kabilaming) joylashish о‘mini aniqlash bilan bog‘liq muammolami hal qilishda qo‘llanilishi mumkin. Ta’kidlash kerakki, muayyan vaziyatlarda, ko‘pincha, boshqa holatlami, jumladan, obyektgacha borish vaqti, punktlar orasidagi masofa va shu kabilami hisobga olishga to‘g‘ri keladi. Bunday vaziyatlarda joylashtirishning minimaks masalalari, deb ataluvchi masalalar vujudga keladi. Kurs ishimda Deyskra algoritmining ishlash prinsplarini ko’rib uning ishlashini dasturlarda amaliy ko’rib chiqdim.