|
Dinamik dasturlash
|
| bet | 1/5 | | Sana | 24.05.2023 | | Hajmi | 191.75 Kb. | | #64149 |
Bog'liq Dinamik dasturlash Rayhona 1. Anketa (talabalar), 3-mavzu, conference, 12 labaratoriya ishi, Маълумотлар тузилмаси ва алгоритмлар узб, Abduvositaka, Saralash algoritmlari, Akademik yozuv 2 Omonboyev Rashidbek 12, kontakt hodisalar, golosariy, Operatsion tizimlar uz, 1 - lesson (internet), 2-маруза мавзуси Симулятор, dars tahlili, 6666666666666666666666666666666666666
Dinamik dasturlash - bu kompyuter dasturlash texnikasi bo'lib, u bir-biriga o'xshash kichik muammolar va optimal pastki tuzilma xususiyatiga ega bo'lgan muammolar sinfini samarali hal qilishga yordam beradi . Dinamik dasturlash ham matematik optimallashtirish usuli, ham kompyuter dasturlash usulidir. Usul 1950-yillarda Richard Bellman tomonidan ishlab chiqilgan va aerokosmik muhandislikdan iqtisodiyotgacha bo'lgan ko'plab sohalarda qo'llanilishini topdi .
Ikkala kontekstda bu murakkab muammoni rekursiv usulda oddiy kichik muammolarga bo'lish orqali soddalashtirishga ishora qiladi . Ba'zi qarorlar bilan bog'liq muammolarni bu tarzda ajratib bo'lmasa-da, bir necha vaqt oralig'ida bo'lgan qarorlar ko'pincha rekursiv ravishda ajralib chiqadi. Xuddi shunday, kompyuter fanida, agar muammoni kichik muammolarga bo'lish va keyin kichik muammolarning optimal echimlarini rekursiv ravishda topish orqali optimal tarzda hal qilish mumkin bo'lsa, u holda u optimal quyi tuzilishga ega deyiladi .
Agar kichik muammolar kattaroq muammolar ichida rekursiv joylashtirilsa, dinamik dasturlash usullari qo'llanilishi mumkin bo'lsa, u holda kattaroq muammoning qiymati va kichik muammolarning qiymatlari o'rtasida bog'liqlik mavjud. [1] Optimallashtirish adabiyotida bu munosabat Bellman tenglamasi deb ataladi .
Agar biron-bir muammoni kichikroq kichik muammolarga bo'linadigan kichik muammolarga bo'lish mumkin bo'lsa va bu kichik muammolar o'rtasida bir-biriga o'xshash muammolar mavjud bo'lsa, u holda ushbu kichik muammolarning echimlari kelajakda foydalanish uchun saqlanishi mumkin. Shunday qilib, CPU samaradorligini oshirish mumkin. Yechimni echishning bu usuli dinamik dasturlash deb ataladi.
Bunday muammolar optimal echimni topish uchun bir xil kichik muammolarning qiymatini qayta-qayta hisoblashni o'z ichiga oladi.
Matematik optimallashtirish [ tahrirlash ]
Matematik optimallashtirish nuqtai nazaridan, dinamik dasturlash odatda qarorni vaqt o'tishi bilan qaror qabul qilish bosqichlari ketma-ketligiga bo'lish orqali soddalashtirishni anglatadi. Bu V 1 , V 2 , ..., V n qiymat funktsiyalari ketma-ketligini aniqlash orqali y ni 1 dan n gacha bo'lgan vaqtlarda tizim holatini ifodalovchi argument sifatida amalga oshiriladi . V n ( y ) ning ta'rifi oxirgi n vaqtida y holatida olingan qiymatdir . Qadriyatlar V i oldingi vaqtlarda i = n -1, n - 2, ..., 2, 1 ni Bellman tenglamasi deb ataladigan rekursiv munosabatdan foydalanib, orqaga qarab ishlash orqali topish mumkin . i = 2, ..., n , V i −1 uchun har qanday holatda y V i dan i − 1 vaqtidagi qarordan olinadigan daromadning oddiy funksiyasini (odatda yig‘indisi) va V i funksiyasini maksimallashtirish yo‘li bilan hisoblanadi. agar ushbu qaror qabul qilingan bo'lsa, tizimning yangi holatida. V i allaqachon kerakli holatlar uchun hisoblab chiqilganligi sababli , yuqoridagi operatsiya V i hosil qiladiBu davlatlar uchun -1 . Nihoyat, tizimning dastlabki holatidagi V 1 optimal yechimning qiymati hisoblanadi. Qaror o'zgaruvchilarining optimal qiymatlari allaqachon bajarilgan hisob-kitoblarni kuzatish orqali birma-bir tiklanishi mumkin.
Boshqarish nazariyasi [ tahrirlash ]
Nazorat nazariyasida odatiy muammo ruxsat etilgan nazoratni topishdir�∗ bu tizimga sabab bo'ladi�˙(�)=�(�(�),�(�),�) ruxsat etilgan traektoriyaga rioya qilish�∗ uzluksiz vaqt oralig'ida�0≤�≤�1 bu xarajat funktsiyasini minimallashtiradi
�=�(�(�1),�1)+∫�0�1�(�(�),�(�),�)d�
Ushbu muammoni hal qilish optimal nazorat qonuni yoki siyosatidir�∗=ℎ(�(�),�) , bu optimal traektoriyani ishlab chiqaradi�∗ va sarf-xarajat funksiyasi �∗ . Ikkinchisi dinamik dasturlashning asosiy tenglamasiga bo'ysunadi:
−��∗=min�{�(�(�),�(�),�)+��∗��(�(�),�(�),�)}
Gamilton-Jakobi-Bellman tenglamasi deb nomlanuvchi qisman differensial tenglama , unda��∗=∂�∗∂�=[∂�∗∂�1 ∂�∗∂�2 … ∂�∗∂��]� va��∗=∂�∗∂� . Biror kishi buni minimallashtirishni topadi� xususida� ,� , va noma'lum funksiya��∗ va keyin chegara sharti bilan yechiladigan qisman differentsial tenglamani olish uchun natijani Gamilton-Jakobi-Bellman tenglamasiga almashtiradi.�(�1)=�(�(�1),�1) . [2] Amalda, bu odatda aniq optimallashtirish munosabatlariga ba'zi bir diskret yaqinlashish uchun raqamli usullarni talab qiladi.
Shu bilan bir qatorda, uzluksiz jarayonni diskret tizim bilan taxmin qilish mumkin, bu Gamilton-Jakobi-Bellman tenglamasiga quyidagi takrorlanish munosabatiga olib keladi:
��∗(��−�)=min��−�{�^(��−�,��−�)+��−1∗(�^(��−�,��−�))}
da� - ning bosqichi� teng oraliqli diskret vaqt oraliqlari va qayerda�^ va�^ ga diskret yaqinliklarni bildiring� va� . Ushbu funktsional tenglama Bellman tenglamasi sifatida tanilgan , uni optimallashtirish tenglamasining diskret yaqinlashuvining aniq yechimi uchun echish mumkin. [3]
Iqtisodiyotdan misol: Ramseyning optimal tejash muammosi [ tahrir ]
|
| |
