Dynamic programming

Dynamic programming (DP, dinamik dasturlash) deb muammoni kichik masalalarga ajratib, ularni faqat bir marta yechish va natijani keyingi bir xil tipdagi masalada ishlatish uchun saqlab turish texnikasiga aytiladi. DP odatda rekursiya uchun optimizatsiya vazifasini ham bajaradi: agar rekursiv funksiya bitta berilgan qiymatni bir necha marta ishlatayotgan bo’lsa (repeated calls), biz dynamic programming texnikasi bilan funksiyani optimallashtirishimiz mumkin. Shu oddiygina optimizatsiya ishlash vaqtini sezilarli darajada qisqartiradi.

Dynamic programming’ni misol bilan tushuntirishga harakat qilaman.

Fibonachchi sonlari haqida matematikaga qiziqqanlar bilishadi. Sonlar ketma-ketligida har bir son o’zidan avvalgi ikki sonning yig’indisiga teng:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Uning formulasi: Fn = Fn-1 + Fn-2 , bunda F0 = 0 va F1 = 1

Hisoblash uchun yoziladigan odatiy dastur quyidagicha ko’rinishida bo’ladi.

Grafik ko’rinishida:

Kodning ishlash vaqti eksponental: O(N2).

E’tibor bersangiz, funksiya ikki marta chaqirilyapti va ikki holda ham deyarli bir xil hisoblashni bajarmoqda. Biz hisoblashni faqat bir marta amalga oshirib, keyingi safar saqlangan joydan o’qib olishimiz mumkinmi?

Kodni optimizatsiya qilamiz (memoization varianti).

Natijalarni cache’ga yozish bilan biz qaytariladigan hisoblashlardan xalos bo’ldik. Shu sababli dasturimizning ishlash vaqti eksponental vaqtdan linear vaqtgacha tushdi.

Yuqoridagi kodning rekursiyasiz (tabulation) varianti:

Qanday qilib dasturda dynamic programming ishlatish mumkinligini aniqlaymiz?

Masalaning DPda yechish imkoni bor-yo’qligini aniqlash uchun uch savolga javob topish kerak bo’ladi.

  1. Muammoni bir necha kichik masalalarga bo’lish mumkinmi?
  2. Muammoga rekursiv yechimi bormi?
  3. Kichik masalalar qaytariluvchimi?

Agar uchala savolga ham javob “Ha” bo’lsa, u holda dynamic programming’ni qo’llashning iloji bor.