Xoffmann kodi. Javoblar: Algoritm tushunchasi

Tushunarlilik –algoritmda ijrochiga berilayotgan ko'rsatmalar aniq mazmunda bo'lishi;

Diskretlilik – algoritmlarni chekli qadamlardan tashkil qilib bo'laklash imkoniyati ;

Cheklilik – bajarilayotgan algoritm chekli qadamlarda natijaga olib kelishi;

Natijaviylik - natijaning bo'lishi;

Ommaviylik – har bir algoritm mazmuniga ko'ra bir turdagi masalalarning barchasi uchun ham o'rinli bo'lishi .

Formallik –komandalarni mexanik bajarish imkoniyati.

Bu xossa robotlar, kompьyuterlar va boshqa qurilmalarda komandalarning ketma-ket bajarilishini ta'minlaydi.

2. 
   Optimallashtirish tamoyili nima va Bellman tenglamalari qanday yozilgan?
   

Matematik optimallashtirish (alternativ ravishda imlo optimallashtirish) yoki matematik dasturlash bu ba'zi mavjud alternativalar orasidan eng yaxshi elementni tanlash (ba'zi mezonlar bo'yicha). Turlarni optimallashtirish muammolari informatika va muhandislikdan tortib amaliy tadqiqotlar va iqtisodiyotgacha bo'lgan barcha miqdoriy fanlarda yuzaga keladi va hal qilish usullarini ishlab chiqish asrlar davomida matematikada qiziqish uyg'otdi.

Eng oddiy holatda, optimallashtirish muammosi ruxsat berilgan to'plam ichidan kirish qiymatlarini muntazam tanlash va funktsiyaning qiymatini hisoblash orqali real funktsiyani maksimal darajaga ko'tarish yoki kamaytirishdan iborat. Optimallashtirish nazariyasi va texnikasini boshqa formulalarga umumlashtirish amaliy matematikaning katta qismini tashkil etadi. Umuman olganda, optimallashtirish turli xil ob'ektiv funktsiyalar va domenlarning har xil turlarini o'z ichiga olgan aniqlangan domen (yoki kirish) berilgan ba'zi ob'ektiv funktsiyalarning "eng yaxshi mavjud" qiymatlarini topishni o'z ichiga oladi.

Richard E. Bellman nomli Bellman tenglamasi dinamik dasturlash deb nomlanuvchi matematik optimallashtirish usuli bilan bog'liq optimizm uchun zaruriy shartdir. U ba'zi bir boshlang'ich tanlovlar natijalarini qaytarish nuqtai nazaridan ma'lum bir vaqt ichida qarorning "qiymatini" va qolgan dastlabki echimlarning natijasi bo'lgan "echimning" qiymatini yozadi. Bellmanning "optimizm printsipi" da ta'kidlaganidek, optimallashtirish muammosi sodda dasturlarning ketma-ketligiga aylantirildi.

Bellman tenglamasi dastlab muhandislik nazorati nazariyasi va amaliy matematikadagi boshqa mavzularga qo'llanildi va keyinchalik iqtisodiy nazariyada muhim vosita bo'ldi; dinamik dasturlashning asosiy tushunchalari Jon Von Neumann va Oskar Morgensternning O'yinlar va iqtisodiy xulq-atvor nazariyasi va Avraam Voldning ketma-ket tahlilida keltirilgan.

Optimal boshqaruv nazariyasi yordamida echilishi mumkin bo'lgan deyarli har qanday muammoni tegishli Bellman tenglamasini tahlil qilish orqali hal qilish mumkin. vaqtni optimallashtirish muammolari. Uzluksiz optimallashtirish muammolarida shunga o'xshash tenglama qisman differentsial tenglama bo'lib, uni Hamilton-Yakobi-Bellman tenglamasi deyiladi.

Bellman tenglamasini tushunish uchun bir nechta asosiy tushunchalarni tushunish kerak. Birinchidan, har qanday optimallashtirish muammosi bir nechta maqsadga ega: sayohat vaqtini minimallashtirish, xarajatlarni minimallashtirish, foydani ko'paytirish, foydali xizmatlarni ko'paytirish va boshqalar. Ushbu maqsadni tavsiflovchi matematik funktsiya ob'ektiv funktsiya deb ataladi. Dinamik dasturlash ko'p bosqichli rejalashtirish muammosini turli bosqichlarda sodda qadamlarga aylantiradi. Shuning uchun, qaror qabul qilingan vaziyat vaqt o'tishi bilan qanday o'zgarishini kuzatib borishni talab qiladi. To'g'ri qaror qabul qilish uchun zarur bo'lgan hozirgi vaziyat haqida ma'lumot "davlat" deb nomlanadi.] Masalan, har bir vaqtda qancha iste'mol qilish va sarflashni hal qilish uchun odamlar o'zlarining dastlabki boyliklarini (boshqa narsalar qatorida) bilishlari kerak. Shuning uchun, boylik {\ displaystyle (W)} ularning holatlaridan biri bo'lar edi, lekin boshqalar ham bo'lishi mumkin.

Vaqtning istalgan vaqtida tanlangan o'zgaruvchilar ko'pincha boshqaruv o'zgaruvchilari deb ataladi. Masalan, hozirgi mavjud boyliklarini hisobga olgan holda, odamlar hozir qancha iste'mol qilishni hal qilishlari mumkin. Endi boshqaruv parametrlarini tanlash keyingi holatni tanlashga teng bo'lishi mumkin; Umuman olganda, keyingi holatga joriy nazoratdan tashqari boshqa omillar ham ta'sir qiladi. Masalan, eng oddiy holatda, bugungi boylik (davlat) va iste'mol (boshqarish) ertangi kunning boyligini (yangi davlat) aniq belgilashi mumkin, ammo odatda boshqa omillar ertangi kunning boyligiga ham ta'sir qiladi. Dinamik dasturlash usuli davlatning har qanday mumkin bo'lgan qiymatini hisobga olgan holda boshqarish kerak bo'lgan narsalarni ko'rsatadigan maqbul rejani tavsiflaydi. Masalan, agar iste'mol (c) faqat boylikka bog'liq bo'lsa (W), biz boylikning funktsiyasi sifatida iste'molni beradigan {\ displaystyle c (W)} qoidasini qidiramiz. Boshqarish holatini davlatlar funktsiyasi sifatida belgilaydigan bunday qoida siyosat funktsiyasi deb nomlanadi (Qarang: Bellman, 1957, III.2). Va nihoyat, ta'rifga ko'ra, maqbul bo'lgan eng yaxshi qiymatga erishadigan maqbul qaror. Misol uchun, agar kimdir baxtni maksimal darajada oshirish uchun iste'molni, boylikni tanlasa (faraz qilsangiz, H baxtni foydali funktsiya kabi matematik funktsiya bilan ifodalanishi mumkin va boylik bilan belgilanadigan narsadir), unda har bir boylik darajasi bog'liq bo'ladi. baxtning eng yuqori darajasi, {\ displaystyle H (W)}. Davlatning funktsiyasi sifatida yozilgan maqsadning mumkin bo'lgan eng yaxshi qiymati qiymat funktsiyasi deb ataladi.

Richard Bellman, diskret vaqtdagi dinamik optimallashtirish muammosi bir davrdagi qiymat funktsiyasi va keyingi davrdagi qiymat funktsiyasi o'rtasidagi munosabatni yozib, orqaga induksiya deb nomlanadigan rekursiv, bosqichma-bosqich shaklda ifodalanishi mumkinligini ko'rsatdi. Ushbu ikki qiymat funktsiyalari o'rtasidagi munosabatlar "Bellman tenglamasi" deb nomlanadi. Ushbu yondashuvda oxirgi vaqt oralig'idagi eng maqbul siyosat o'sha vaqtdagi davlat o'zgaruvchisining qiymatining funktsiyasi sifatida oldindan belgilanadi va ob'ektiv funktsiyaning natijaviy maqbul qiymati shu tarzda davlat o'zgaruvchisining qiymati bilan ifodalanadi. Keyingi, keyingi davrni optimallashtirish ushbu davrning davriy ob'ekti funktsiyasining yig'indisini va kelgusidagi ob'ekt funktsiyasining optimal qiymatini ko'paytirishni o'z ichiga oladi, bu davrning maqbul siyosati keyingi davrdagi davlat o'zgaruvchisining qiymatiga qarab belgilanadi. So'nggi davr qarori. [aniqlashtirish kerak] Ushbu mantiq birinchi davrga xos bo'lgan ob'ektiv funktsiyaning yig'indisini optimallashtirish orqali dastlabki holat o'zgaruvchan qiymatining funktsiyasi sifatida qaror qabul qilingan birinchi davrga qadar vaqt o'tishi bilan qaytariladi. va kelgusi barcha davrlar uchun qiymat beradigan ikkinchi davrning qiymat funktsiyasining qiymati. Shunday qilib, har bir davrning qarori kelajakdagi barcha qarorlar maqbul ravishda qabul qilinishini aniq tan olish orqali amalga oshiriladi.

Yechilish usullari:

"Taxmin qilish va tekshirish" deb nomlanuvchi aniqlanmagan koeffitsientlar usulidan ba'zi cheksiz ufqda, avtonom Bellman tenglamalarini echishda foydalanish mumkin.

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.