Min  I i ijijcB   

I-Jadval

x	0	1	2	3	4	5
	0	1	2	3	4	5
	0	1	2	3	4	5
	0	1	2	3	4	5

II-Jadval

y	1	2	3	4	5
	1	2	3	4	5
	1(0)	2(0)	3(0)	4(0.4)	7(5)
	2(1)	3(1)	4(1)	5(1)	7(0)

(6) tenglamaning o'ng tomoni maksimumga erishadigan qiymat ham ko'rsatilgan. V.2-jadvaldan ko'rinadiki, qaralayotgan masalada maksimal foyda bo'ladi. Resurslarni optimal taqsimlanishni topamiz. bo'lganligidan, uchinchi texnologik jarayonga resurs ajratamiz: SHunday qilib, 1, 2 jarayonlarga to'liq 5 hajmdagi resurs qoldi. V.2-jadvaldan ekanligini topamiz. Demak, maksimal foyda olish uchun hamma resursni ikkinchi texnologik jarayonga ajratish kerak shuning uchun, _.

d + t( C, E) +f( E) =16; d+t(C,F)+f(F)=13; PUSHelement. no action taken

(x, y) E A,

"Eng qisqa yo'l muammosi" ning maqsadi eng qisqa yo'lni topishdir
1-tugundan N-tugunga N tugun va A yoylarining asil tarmog'ida. Har bir
yoy (i, j) bog'langan t (i, J) og'irligiga ega. Dreyfus va Qonun [5] va Denardo [3] da tasvirlangan dinamik dasturlash bu muammoni hal qiladi.
ko'plab optimallashtirish muammolarini rekursiv hal qilish. i bilan belgilangan tugunlar
f(i), i-tugundan N.Belman insightiga qadar boʻlgan eng qisqa yoʻlning uzunligi.
Uning mashhur optirnallik printsipi edi: "optimal yo'llarning pastki yo'llari
o'zlari optimal." Bu rekursiyada mujassamlangan
f( i) = min{ t( i, j) +f( j) : (i, j) yoy}.
G'oya shundan iboratki, N dan i ga erishish uchun oxirgi qadam j tugunidan amalga oshiriladi. The
j tuguniga optimal tarzda erishish kerak, agar j optimal yo'lda bo'lsa
N dan i gacha. Shuni ta'kidlash kerakki, f(N) = 0 ni boshlash uchun kerak
rekursiya. Ushbu maqolaning mavzusi optimalga yaqin yo'llar uchun yangi algoritmni berishdir.

Agar optimal yaqin yo'llarning p% klassi kerak bo'lsa, u holda e (p/100)f(l) ga teng. Barcha yo'llar f(l)+ e miqdoridan kichik yoki unga teng keyin algoritm yordamida topiladi. Bu muammolar uchun qulaydir mos keladigan K noma'lum va/yoki katta. F(i) tugun belgilarini rekursiv hisoblashda hech qanday "ko'rsatgich" yoki qaror ma'lumotlarini saqlash kerak emas. Ushbu tugun belgilari ishlash orqali topiladi N tugunidan 1 tugun etiketlanmaguncha orqaga. Keyin yangi algoritm 1-tugundan boshlab va davom etuvchi stacking bilan birinchi chuqur qidiruvni amalga oshiradi barcha yaqin optimal yo'llar chiqmaguncha. Belgilangan joyga teng bo'lmagan x tugunini ko'rib chiqing. Ba'zi yo'l P bilan kumulyativ masofa d bizni 1-tugundan x tuguniga olib keldi. Kirish uchun test yoy (x, y) va stekga masofa d endi umumiy shaklni oladi, uchun hammasi (x, y) E A, Bu erda d - P yo'li bo'yicha 1-tugundan x tugungacha bo'lgan umumiy masofa (yo'q albatta eng qisqa yo'l bilan), t (x, y) - x tugundan y tugungacha bo'lgan masofa, f(y) esa y tugunidan N tugungacha optimal qolgan masofa. Algoritm oxir-oqibat 1-tugundan uzunligi d bo'lgan P yo'lni quradi tugun N. Keyin P va d chiqariladi va stek boshqa yoki yo'qligini tekshirish uchun tekshiriladi Optimalga yaqin yo'llar mavjud. Demak, algoritm oxirgi kirish, birinchi chiqish yoki bajarishni amalga oshiradi chuqurlik - birinchi qidiruv. Algoritmni asoslash uchun algoritm P ning yo‘lini yaratdi deylik d uzunligi 1 tugundan x tugungacha. P yo'liga qo'shilgan yoy (x, y) da yoqilgan d + t(x,y)+f(y) ~f(l)+ e bo'lsa, kamida bitta optimalga yaqin yo'l y dan N gacha bo'lgan eng yaxshi yo'l f(y) uzunligiga ega. E'tibor bering, yo'l uzunligidagi bog'lanishlar alohida muammolarga olib kelmaydi. Bu muhim Agar yoy eng maqbul yo'lda yotmasa, u to'planmaganligini ko'rish uchun. Bundan tashqari, test (*) hech qachon har bir tugun uchun bir martadan ortiq bajarilmaydi maxsus yaqin optimal yo'l.

Yoy uzunliklari t( i, j) va 1-rasmda berilgan asiklik tarmoqni ko‘rib chiqaylik.
A dan I gacha bo'lgan tugunlar, bu erda A va I tugunlari kelib chiqish va maqsadni ifodalaydi.
Har bir tugun ustidagi raqamlar [ f( i)] tugunning eng qisqa uzunligini bildiradi
I tugunga. Faraz qilaylik, foydalanuvchi optimal yo'lning 20% ​​doirasidagi barcha yo'llarni so'raydi
uzunligi 13, bu A tugunidagi tugun yorlig'i. Bu foiz a degan ma'noni anglatadi
15.6 ning yuqori chegarasi P tartiblangan yo'l massivida tugunlar mavjud.
Optimalga yaqin yo'l hozirda aniqlanmoqda va A tugun bilan ishga tushirilgan.
Stack elementi uchta ma'lumotni o'z ichiga oladi:
№1: Joriy tugun.
№2: Keyingi tugun.
№3: boshlang'ich (A tugun) dan №2 tugungacha bo'lgan masofa d.
Algoritm quyidagicha davom etadi:
Qadam 1. A tugunida, d = 0.
t( A, B) + f( B) = 14;
t( A, C) +f( C) = 13;
Yig'ish uchun elementni PUSH.
Yig'ish uchun elementni PUSH.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
A B 2
A C 0
c
2-qadam. Stackning oxirgi elementini POP va №2 da saqlangan “keyingi tugunni” P ga qo'ying
massiv = (A, C). C tugunida d # 3 yoki da saqlangan masofaga teng
d = 0.
d + t( C, E) +f( E) =16;
d+t(C,F)+f(F)=13; PUSHelement.
hech qanday chora ko'rilmagan.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
A B 2
C F 3
3-qadam. POP oxirgi elementi. P = (A, C, F). F tugunida d = 3.
d + f( F, H) + f ( H) = 13; PUSH elementi.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
A B 2
F H 7
4-qadam. POP oxirgi elementi. P = (A, C, F, H). H tugunida d = 7.
d + f( H, I) +f( I) = 13; PUSH elementi.
Stack tarkibiga quyidagilar kiradi:
#I #2 #3
A B 2
H I 13
5-qadam. POP oxirgi elementi. P = (A, C, F, H, I). Tugun I erishildi, shuning uchun
d = 13 bilan P yo'li chiqariladi. Stack hozir quyidagilarni o'z ichiga oladi:
#1 #2 #3
A B 2
6-qadam. POP elementi. P = (A, B), d = 2.
d + t( B, D)+f( D) =14; PUSH elementi.
d + t( B, E) +f( E) = 16; hech qanday chora ko'rilmagan.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
B D 4
7-qadam. POP elementi. P = (A, B, D), d = 4.
d + t( D, G) + f( G) = 14; PUSH elementi.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
D G 9
8-qadam. POP elementi. P = (A, B, D, G), d = 9.
d + t( G, I) + f( I) = 14; PUSH elementi.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
G I 14
9-qadam.
shuning uchun d = 14 bo'lgan P yo'l chiqariladi. Stack bo'sh, shuning uchun to'xtating.
POP elementi. P = (A, B, D, G, I). I tugunga erishildi,
Xulosa qilib aytadigan bo'lsak, A tugunidan I tugunga yaqin optimal yo'llar:
A+C+F+H+I, uzunlik13,
A + B + D + G -, I, uzunligi 14.
Bellman tenglamasi orqaga indüksiyon tomonidan hal qilinishi mumkin, yoki bir necha maxsus holatlarda analitik usulda, yoki kompyuterda raqamli ravishda. Orqaga sonli indüksiya turli xil muammolar uchun qo'llaniladi, ammo o'lchov o'lchovi la'nati tufayli juda ko'p davlat o'zgaruvchisi mavjud bo'lganda bu mumkin emas. Bellman funktsiyasini yaqinlashtirish uchun sun'iy neyron tarmoqlari (ko'p qavatli idroklar) yordamida D.P. Bertsekas va J. N. Tsitsiklis tomonidan taxminiy dinamik dasturlash joriy etilgan. Bu butun kosmik domen uchun funktsiyalarning to'liq xaritasini eslab qolishni yagona neyron tarmoq parametrlarini eslab qolish bilan almashtirish orqali o'lchamlilik ta'sirini kamaytirish uchun samarali yumshatish strategiyasidir. Bellman tenglamasi bilan bog'liq birinchi tartib shartlarini hisoblash va keyin qiymat funktsiyasining hosilalarini yo'q qilish uchun konvert teoremasidan foydalanib, "Eyler tenglamalari" deb nomlangan farq tenglamalari yoki differentsial tenglamalar tizimini olish mumkin. Farqli yoki differentsial tenglamalarni yechishning standart usullaridan keyin holat o'zgaruvchilarining dinamikasini va optimallashtirish muammosining boshqarish parametrlarini hisoblash uchun foydalanish mumkin.


Dinamik dasturlash deb matematik modellari ko’p bosqichli va dinamik jarayonli harakterga ega bo’lgan chiziqsiz dasturlashning maxsus masalalari va optimal boshqaruv masalalarini yechishning hisoblash usulig