|
Tolali optik aloqa tzimlarini ishonchlilik ko’rsatkichlarini oshirish usullarinining algoritmini ishlab chqish
Graf G=(v,A) berilgan bo‘lsin. Graf tuzilmasini ifodalashning ikki xil usuli mavjud: kvadrat matrisalar va qo‘shnichilik matrisa usullari. Graf tugunlari orasidagi bog‘lanishlar soni kam hollarda qo‘shnichilik matrsasidan foydalaniladi, natijada texnik jihoz xotira hajmi tejaladi[3].
Mashrutni aniqlashda zarur bo‘lgan Lta zaxira yo‘l va M ta bog‘lanish v1,v2, C, V , t statik o‘zgaruvchilar quyidagicha ifodalangan bo‘lsin:
1). v1 va v2lar tugunlar; 2). C – v1 va v2 tugunlar orasidagi sig‘im koeffisienti; 3). V- tugunlar orasidagi tezlik; 4). t -tugunlar orasidagi kanaldan ma’lumotlar oqimining o‘tish vaqti.
Tugunlararo bog‘lanish qarshilik koeffisienti qilib quyidagi kattalikni kiritib olamiz.
. (2.8)
Ushbu, koeffisient qanchalik kichik bo‘lsa i va j tugunlar orasidan ma’lumotlar oqimini o‘tishiga qarshilik shunchalik kam bo‘ladi.
Kirish parametrlaridan yana biri dinamik o‘zgaruvchi bo‘lib, ikki tugun orasidagi yuklanishlar sonini ifodalovchi kattalik nogM orqali belgilansin. Tugunlararo yuklanishni va yuklanishni davom etish vaqtini orqali ifodalaylik.
Yuqorida ifoda etilgan ma’lumotlar asosida marshrutni
aniqlashning qisman tanlov algoritmi quyidagi modulli algoritmlar majmuasi ko‘rinishida tasvirlanadi.
|
Бoшлaш
йyԕ
L > 0
ԟa
Taмoм
2.1 – rasm (Qisman tanlov algoritmini modulli ko‘rinishi).
Ushbu 2.1 – rasmda keltirilgan qisman tanlov algoritmi modullari quyidagicha ta’riflanadi:
Boshlang‘ich parametrlarni kiritish moduli – bu modulda algoritm boshlang‘ich ma’lumotlarni graf - qo‘shnichilik matrisasidan foydalanilgan holda shakllantiradi;
Xotirani taxsimlash moduli – bu modulda o‘zgaruvchilarga boshlang‘ich qiymatlar beriladi va o‘zgaruvchilarni dinamik tuzilmali saqlashning yangi xotiradan foydalanish tuzilmasi ishlab chiqiladi. Demak, texnik jihoz xotira faoliyati shu asosda shakllantiriladi;
V. L ta yo‘lni tanlash moduli – bu modulda yaratilgan dinamik tuzilmaga yangi qiymatlarni yozish va mashrutlarni tanlash usuli ishlab chiqildi. Mashrutlarni topish jarayonida Deykstra algoritimini ishlash g‘oyasidan foydalanildi va uning modifikatsiyasi yaratildi. Dekstra algoritmi faqat bitta “minimum” yo‘lni topishga mo‘ljallangan, yaratilgan modifikatsiya algoritmi esa “minimum” yo‘l bilan birgalikda unga yaqin bo‘lgan boshqa zaxira yo‘llarni ham aniqlab beradi.Shunday qilib, ushbu modulda L ta yo‘l shakllantiriladi;
G. Natijalar (yo‘l, qarshilik,yuklanish va vaqt) –ushbu modulda
|
|
A.Бoшлaнfич пapaмetpлapни kиpиtиш
|
|
|
Б. Динaмиk xotиpaни taxcимлaш
|
|
|
B. L ta энг яxши йyлни taнлaш
|
|
|
Г. Hatижaлap (йyл,
ԕapшилиk,юkлaниш ba baԕt)
|
|
quyidagi natijalar olinadi:
Tugunlararo qarshilik koeffisenti aniqlanadi;
L ta yo‘l ro‘yxati shakllantiriladi;
Yuklanish va yuklanish vaqtlari aniqlanadi;
Yo‘llar yaroqli yoki yaroqsiz ekanligi tanlanadi;
Tugunlararo ma’lumotlar o‘tish geografiyasi shakllantiriladi.
A. Boshlang‘ich parametrlarni kiritish algoritmi
– qadam.N, M, Lsonlar kiritiladi.N – grafdagi tugunlar soni, M – grafdagi bog‘lanishlar soni, L – topilishi lozimbo‘lgan zaxira yo‘llar soni.
– qadam. 1 dan M gacha sikl tashkil qilinadi vav1, v2, C, V, t o‘zgaruvchilar kiritiladi. Har bir siql bajarilishi davomida K qarshilik koeffisenti hisoblanadi vaAges tuzilmasiga nuqta ko‘rinishida saqlab boriladi. Bu yerda K = ](t/(CV))* 100%[ formula bilan hisoblanadi.
Demak, v1, v2, C, V, t o‘zgaruvchilar, K koeffisient orqali ifodalanadi. Ages - bog‘lanishlarning qo‘shnichilik matrisasi.
3– qadam. Yuklanishlarning bog‘lanishlari soninogM kiritiladi.
4 –qadam. 1 dan nogM gacha sikl tashkil qilinadi va x, y, PP, TT o‘zgaruvchilar yuklanadi.Bu yerda x tugundan, u tugunga borishdagi PP yuklanish va TT yuklanish vaqti davomiyligi. Har bir sikl bajarilishi davomida nog va vaqt matrisalarga qiymatlar joylashtirilib boriladi.Bu yerda nog[x][y] = PP, nog[y][x] = PP va vaqt[x][y] = TT, vaqt[y][x] = TT ko‘rinishida ifodalanadi.
B. Dinamik xotirani taxsimlash algoritmi
– qadam.D[1][1] = 0 boshlang‘ichqiymatberiladi.
– qadam. inf = > maxNumber, -. inf o‘zgaruvchisiga maxsimal qiymat beriladi.
– qadam. D[N][L]matrisani har bir elementini inf o‘zgaruvchisi
|
bilan to‘ldiriladi. D matrisa minimum qarshilikli yo‘lni topishda ishlatiladi.
– qadam. Used[N][L] matrisasini har bir elementini false qiymat bilan to‘ldiriladi. Used matrisasi minimum yo‘lni topishda tugunlardan foydalanilgan yoki foydalanilmaganlikni bilish uchun ishlatiladi. Agar biror tugundan foydalanilsa shu tugunga mos bo‘lgan used o‘zgaruvchisining qiymati true orqali belgilanadi.
– qadam.List tuzulmasini e’lon qilamiz. List tuzilmasi bitta tugundan boshqasiga boradigan minimal va minimalga yaqin bo‘lgan L ta yo‘lni saqlash uchun ishlatiladi.
D. L ta eng yaxshi yo‘lni tanlash algoritmi
E ta eng yaxshi yo‘lni tanlash moduli algoritmning eng asosiy moduli hisoblanadi. Modul Deykstra algoritmini ishlash g‘oyasiga asoslangan bo‘lib, har bir tugunda minimum yo‘lni emas, balki minimumga yaqin bo‘lgan Lta yo‘lni saqlashi keltirilgan.
1 – qadam. List matrisaning birinchi satir vabirinchi ustun elementiga tugunning birinchi elementni mos qo‘yamiz, ya’ni List[1][1] =
1. Bu bashlang‘ich tugun hisoblanadi.
2 – qadam. Birinchidanboshlab barcha elementlarni ko‘rish uchun 1 dan L gacha sikl ochiladi.
for (i ->1, n*L){
v -> 0, k -> 0
for (j -> 1, n) {
for (j2 = 1, L) {
if (not used[j][j2] va (v=0 yoki d[j][j2] < d[v][k]))
{
v -> j;
k -> j2;
}
|
}
}
Bu yerda v = 0, k = 0 qilib belgilab olinadi. Indekslar v va k qaralayotgan nuqtadan qo‘shni foydalanilmagan nuqtalarga o‘tishni belgilash uchun ishlatiladi. Ikkita sikl ochilib, barcha elementlar tekshirib chiqiladi. Agar, not used[i][j2], j – tugundan j2 – tugunga boradigan yo‘l tekshirilmagan bo‘lsa va v = 0, yoki d[j][j2] < d[v][k] -qaralayotgan nuqtadan yangi o‘tish nuqtasigacha bo‘lgan masofa kichik bo‘lsa, u holda topilgan tugun saqlab qolinadi hamda qaralayotgan nuqta tekshirildi deb belgilab qo‘yiladi. Ya’ni
used[v][k] = true; bo‘ladi.
3 – qadam. Tugun v - ning barcha qo‘shni yo‘llari kiritish modulida saqlanilgan. Bu yerdaages matrisasining v ustuni bo‘ylab j = 1 dan L gacha sikl tashkil qilinadi. Bu siklni tashkil qilishdan maqsad:
Agar, topilgan yangi yo‘l oldin saqlangan yo‘llardan yaxshi bo‘lsa (ya’ni, qarshiligi biror bir boshqa oldingi L tani ichidagi yo‘lga nisbatan kam bo‘lsa),u holda topilgan yangi yo‘lL ta yo‘l ichiga kiritilib, qaytadan saralanadi;
Agar topilgan yangi yo‘l, L ta yo‘l ichida mavjud bo‘lmasa, u holda uni to‘g‘ridan - to‘g‘ri L ta yo‘l tarkibiga qo‘shib qo‘yiladi.
Bu yo‘llarni tanlashda masofalar ham inobatga olib boriladi. Qaralayotgan tugundan qo‘shni tugunga o‘tiladigan, o‘sish tartibida saralangan L ta yo‘l aniqlangandan so‘ng jarayon to‘xtatiladi.Bu jarayon har bir tugun uchun bajariladi.
for (Point to : ages[v]) { for (j -> 1, L) {
if (d[v][k]+to.y< d[to.x][j] va !(to.xichida
List[v][k])){
|
for (j2 ->L,j;) {
d[to.x][j2] -> d[to.x][j2-1]; List[to.x][j2] ->tozalaymiz List[to.x][j2] -> List[to.x][j2-1]
topilgan hamma
yo‘llarni qo‘shib olamiz
}
d[to.x][j] -> d[v][k]+to.y; List[to.x][j]->tozalaymiz
List[to.x][j] ->topilgan hamma yo‘llarni
qo‘shib olamiz
List[to.x][j] ->to.xelementni qo‘shib olamiz Siklni tugatamiz
}
}
}
}
4 – qadam. Qisman tanlash algoritimining V moduli ishlashi natijasida List tuzilmasi tarkibidatanlangan L ta yo‘l saqlab qo‘yiladi.
F. Natijalar (yo‘l, qarshilik,yuklanish,vaqt) moduli algoritmi 1–qadam. Siql 1 dan L gacha tashkil qilinadi. Saralangan L ta yo‘l
chop qilinadi, qarshilik koeffisienti aniqlanadi, yuklanish va yuklanish vaqtlari davomiyligi hisoblanadi.
for (i -> 1,L) {
2–qadam. Agar List[n][i] element bo‘sh bo‘lsa unda yo‘l qolmaganligini bildiradi va sikl tugatiladi.
if (List[n][i]bo‘sh bulsa ) {
println(i+"-danboshlabqisqayolyok");
|
Siklni tugatish;
}
3–qadam. Bunda i - eng qisqa yo‘l,qarshilik koeffisenti va o‘tish yo‘llari soni hamda o‘tish yo‘llari keltiriladi.
print(i+"-qisqayol : Qarshilikkoff="+d[n][i]+", Uchlar soni="+len(List[n][i])+", Royxat: ");
for (j -> 0,Len(List[n][i])-1) {
print(Len(List[n][i])+"->");
}
print(List[n][i].get(Len(List[n][i])-1)+" Nogruzkasi: "); 4–qadam. Bunda i - eng qisqa yo‘l, yuklanish koeffisenti keltiriladi.
nogSum-> 0;
for (j = 0,Len(List[n][i])-2) {
x -> List[n][i].get(j);
y -> List[n][i].get(j+1); nogSum->nogSum +nog[x][y];
}
x -> List[n][i].get(Len(List[n][i])-2);
y -> List[n][i].get((List[n][i])-1); nogSum->nogSum +nog[x][y]; print(nogSum+" Vaqti: ");
5–qadam. Bunda i - eng qisqa yo‘l, yuklanishning davomiylik vaqti keltiriladi.
nogVaqt-> 0;
for (j -> 0,Len(List[n][i])-2) {
x -> List[n][i].get(j);
y -> List[n][i].get(j+1); nogVaqt->nogVaqt +vaqt[x][y];
|
}
x -> List[n][i].get(Len(List[n][i])-2);
y -> List[n][i].get(Len(List[n][i])-1); nogVaqt->nogVaqt +vaqt[x][y]; println(nogVaqt);
}
4. Algoritmni testlash
Misol uchun tugunlari 7 ta va tugunlararo bog‘lamlar 9 ta bo‘lgan graf berilgan bo‘lsin. Grafning bog‘lanish parametlari ikki turga ajratiladi, statik va dinamik parametrlar.
Statik parametrlar:
S – sig‘im koffisenti;V – tarmoqni o‘tkazish tezligi;t – o‘tkazish
vaqti.
Dinamik parametrlar:
Nog – biror tugunlararo yuklanish koffisenti;Vaqt – biror tugunlararo yuklanishning davomiylik vaqti.
Graf bog‘lanish chizig‘ining ustki qismida statik parametrlar va pastki qismida dinamik parametrlar ifodalanadi (2- rasm).
10 10 7
2 0 0 4
10 6 3 10
0 0 0 010 5 5 1 5 4 1
1 3 4 2 0 0
10 5 3 5 7
0 0 10 10 1
1 2 5 5 2
10 10 7 0 0
3 2 7 6
2.2 – rasm. Algoritmni testlash uchun graf tuzilmasi
|
|
Algoritmga kiritilgan parametrlarga nisbatan natijalarni kuyidagicha ko‘rish mumkin.
qisqa yol : Qarshilik koff=16, Uchlar soni=5, Royxat: 1->3->5->4->7 Nogruzkasi: 5 Vaqti: 4
qisqa yol : Qarshilik koff=17, Uchlar soni=4, Royxat: 1->2->4->7 Nogruzkasi: 0 Vaqti: 0
qisqa yol : Qarshilik koff=17, Uchlar soni=5, Royxat: 1->2->5->4->7 Nogruzkasi: 4 Vaqti: 2
qisqa yol : Qarshilik koff=21, Uchlar soni=4, Royxat: 1->3->6->7 Nogruzkasi: 2 Vaqti: 7
qisqa yol : Qarshilik koff=22, Uchlar soni=6,
Royxat: 1->3->5->2->4->7 Nogruzkasi: 1 Vaqti: 2 6-qisqa yol : Qarshilik koff=24, Uchlar soni=6,
Royxat: 1->2->5->3->6->7 Nogruzkasi: 3 Vaqti: 9
|
Do'stlaringiz bilan baham: |
