Dinamik dasturlash, asosiy tamoyillari

dasturlash vazifalari ba'zan shaxsiy kompyuter xotirasi yuklaydi ma'lumotlar birikmalarning katta miqdorda tartiblashtirish uchun talab qilinadi o'qiyotganda optimal yechim-ni tanlang. Bunday usullar, masalan, "bo'l va boshqar" dasturlash usuli, o'z ichiga oladi. Bu holda algoritm alohida kichikroq Alt kirib ajratish muammo beradi. Bu usul faqat kichik pastki o'zaro mustaqil bo'lgan hollarda qo'llaniladi. o'zaro bog'liq sub-vazifalarni agar keraksiz ishlarni amalga oldini olish uchun, 50-yillarida Amerika R.Bellmanom taklif dinamik dasturlash usuli foydalanadi.

usul

Dinamik dasturlash uning n alohida bosqichlarini almashish, eng munosib yechim n-o'lchovli muammoni aniqlash uchun hisoblanadi. Ularning har biri o'zgarmaydigan hurmat bilan sub-vazifa hisoblanadi.

Bu yondashuv asosiy afzalligi bir o'lchovli optimallash muammosi bilan shug'ullanuvchi Dasturchilar o'rniga bir n-o'lchovli muammoning pastki va bizning asosiy maqsadi "pastdan yuqoriga" ketadi, deb qabul qilinishi mumkin.

Bu, ya'ni sub-vazifalarni-biri bilan bog'liq bo'lgan hollar, jadal dasturiy amalga oshirish uchun tavsiya etiladi umumiy modullari baham. algoritm bir marta Alt topshiriqlardan har bir qaror beradi va tejash javob maxsus jadvalda amalga oshiriladi. Bu ular bir xil sub-vazifa bilan yana uchratganida javob hisoblash emas beradilar.

Dinamik dasturlash vazifa muammoni hal optimallashtirish. Bu usulning muallifi R. Bellman Optimallik siyosati tomonidan formuladan qilindi: qadamlar va bu bosqich belgilangan eritma har bir boshlang'ich davlat narsalar har qadam oxirida tizimini qabul davlat, nisbatan optimal tanlash uchun quyidagi.

usuli variantlarining, yoki özyineleme orqali hal vazifalar faoliyatini yaxshilaydi.

Bino vazifasi algoritm

Dinamik dasturlash algoritm, shuning uchun uning hal ikki yoki undan ko'p Alt bo'linadi vazifasi barcha Alt topshiriqlardan uchun optimal yechim topgan bunday vazifalarni qurilishini o'z ichiga oladi, u o'z ichiga oladi. Bundan tashqari, u qaytish aloqasi, yozish va bir butun sifatida vazifa uchun optimal parametr qadriyatlarini hisoblash uchun zarur.

Ba'zan, 3 qadam, har bir ishning borishi haqida ba'zi qo'shimcha fon ma'lumot yod iborat. Bu Qaytish urish deyiladi.

Application usuli

ikki xarakterli xususiyatlari bor qachon Dinamik dasturlash qo'llaniladi:

• Alt topshiriqlardan uchun optimal;
• subproblems nizomiga muvofiq muammosi mavjudligi.

dinamik dasturlash tomonidan optimallashtirish muammoni hal qilish, avval hal tuzilishini tasvirlab kerak. vazifa hal o'z Alt topshiriqlardan eng yaxshi qarorlardan iborat bo'lsa optimal bo'lishi kerak. Bu holda, u dinamik dasturiy foydalanish tavsiya etiladi.

Bu usul muhim muammoning ikkinchi xususiyat, - sub-vazifalarni kichik raqam. Shu ketma-ket kelgan sub-muammolarni yordamida muammoni Tekrarlamalı eritmasi, soni, dastlabki ma'lumotlar hajmiga bog'liq. javob maxsus jadvalda saqlanadi, dastur bu ma'lumotlarni yordamida vaqtni tejash imkonini beradi.

Ayniqsa, samarali vazifa aslida bosqichda qaror qabul qilish uchun zarur bo'lgan dinamik dasturlash foydalanish hisoblanadi. Misol uchun, almashtirish va uskunalar ta'mirlash muammoning oddiy misolni ko'rib. ikki turli shakllarda shina qilish bir vaqtning o'zida shinalari ishlab chiqarish bo'yicha to'qimalarining mashinasi zavodi haqida aytaylik. shakllaridan biri bajarilmasa, u holda, bu Demontaj uchun zarur. Bu ba'zan ko'proq daromadli o'rniga va holatda Demontaj uchun ikkinchi shakli va bu shakl keyingi bosqichda bajarilish bo'ladi, deb tushunsa bo'ladi. Ayniqsa, ular muvaffaqiyatsizlikka boshlash oldin ikkala ish shaklini o'zgartirish uchun oson, chunki. davom ekspluatatsiya shakllari, mashina uzilishlar, tashlanadi shinalari va ko'proq mablag 'yo'qotish foydalari: Dinamik dasturlash usuli hisobga barcha omillar olib, bu shakllarini almashtirish masalada eng yaxshi strategiya belgilab beradi.