Dinamik dasturlash (DP) — bu masalalarni optimal quyi tuzilishga ega bo‘lgan, bir-birini qoplaydigan kichik masalalarga bo‘lish orqali yechish texnikasi. DP dan foydalanadigan ko‘plab masalalar mavjud, masalan, qism to‘plami yig‘indisi, ryukzak, tangalarni qaytim qilish va h.k. DP ayrim maxsus masalalarni yechish uchun daraxtlarda ham qo‘llanilishi mumkin.
Asosiy subtree DP misoli
N ta tugun va N−1 ta qirrali daraxt berilgan. Tugunlarni qayta tashrif buyurmasdan ildizdan biror barggacha bo‘lgan yo‘lda tugun qiymatlarining maksimal yig‘indisini topish talab qilinadi.
Yuqoridagi rasmda N=14 ta tugunli daraxt va qiymatlar ko‘rsatilgan:
Bu yerda ochko‘z (greedy) yondashuv ishlamaydi: lokal maksimal qiymatlarni tanlash (3→10→5) 18 yig‘indili 7-yo‘lni beradi, bu esa optimal emas.
Yechim g‘oyasi
Daraxtda DP dan foydalanamiz.
Quyidagicha belgilaymiz:
DPi=i dan istalgan barggacha bo‘lgan yo‘lning maksimal yig‘indisi
Unda:
barg uchun: DPi=valuei
ichki tugun uchun:
DPi=valuei+u∈children(i)maxDPu
Hisoblash DFS orqali pastdan yuqoriga bajariladi.
Barglardan boshlaymiz va yuqoriga ko‘tarilamiz, har safar joriy tugunga subtree ichidagi maksimumni qo‘shamiz. Oxirida DP1 ildizdan barggacha bo‘lgan yo‘lning maksimal yig‘indisini o‘z ichiga oladi.
Masala 1
Masala sharti
N ta tugundan iborat T daraxt berilgan.
Har bir i tugunda Ci ta tanga bor.
Shunday tugunlar qism to‘plamini tanlash kerakki:
ikkita qo‘shni tugun tanlanmagan bo‘lsin
tangalar yig‘indisi maksimal bo‘lsin
Yechim
Bu masala massivdagi masalaga o‘xshaydi:
dp(i)=max(Ai+dp(i−2),dp(i−1))
Daraxtda holat cho‘qqining subtree si bilan aniqlanadi.
Ildizni (masalan, 1) qilib belgilaymiz. dp(V) — V cho‘qqisi subtree si uchun javob bo‘lsin.
Izlanayotgan javob: dp(1).
Cho‘qqini tanlash
Agar V cho‘qqisini tanlasak:
uning bolalari v1,…,vk ni tanlab bo‘lmaydi
nabiralarni tanlash mumkin
Agar V ni tanlamasak:
bolalarni tanlash mumkin
DP-formulirovka
Ikki holat kiritamiz:
dp1(V) — V kiritilgan bo‘lsa maksimum
dp2(V) — V kiritilmagan bo‘lsa maksimum
Unda:
dp1(V)=CV+u∈children(V)∑dp2(u)
dp2(V)=u∈children(V)∑max(dp1(u),dp2(u))
Javob:
max(dp1(1),dp2(1))
Realizatsiya
Masala 2
Masala qo‘yilishi
N ta tugundan iborat T daraxt berilgan. Istalgan ikki tugun orasidagi eng uzun yo‘l uzunligini (daraxt diametrini) hisoblash talab qilinadi.
Yechim
Daraxt ildizini 1 tugunda belgilaymiz.
Ixtiyoriy x cho‘qqini ko‘rib chiqamiz. Maksimal yo‘lning ikki turi bo‘lishi mumkin:
Yo‘l x dan boshlanib pastga, uning subtree siga tushadi. Uzunligini f(x) deb belgilaymiz.
Yo‘l x orqali o‘tib, uning ikkita subtree sini bog‘laydi. Uzunligini g(x) deb belgilaymiz.
Daraxt diametri:
xmaxmax(f(x),g(x))
f(x) ni hisoblash
V cho‘qqining avlodlari v1,v2,…,vn bo‘lsin.
Ta’rifga ko‘ra:
f(V)=1+max(f(v1),f(v2),…,f(vn))
Agar avlodlar bo‘lmasa (barg):
f(V)=1
Bu standart Tree-DP rekursiyasi: tugun qiymati bolalar qiymatlariga bog‘liq.
g(x) ni hisoblash
Yo‘l:
vi subtree sida boshlanishi
V orqali o‘tishi
vj subtree sida tugashi, i=j
Uzunlikni maksimal qilish uchun quyidagilar orasidan eng katta ikkita qiymatni tanlaymiz:
f(v1),f(v2),…,f(vn)
Unda:
g(V)=2+( f(vi) orasidagi ikki maksimal qiymat)
Yakun
Har bir cho‘qqi uchun yangilaymiz:
diameter=max(diameter,f(V),g(V))
Realizatsiya
Masala 3
Masala qo‘yilishi
N ta tugundan iborat T daraxt va butun son K berilgan.
O‘lchami K dan oshmaydigan turli bog‘langan subtree lar sonini topish talab qilinadi.
Yechim
Avval ta’rifni aniqlashtiramiz.
Subtree — bu asl daraxt cho‘qqilarining istalgan bog‘langan qism to‘plami.
Bu cho‘qqining standart subtree sidan (uning barcha avlodlarini o‘z ichiga oladigan) farq qiladi.
Daraxt masalalarida odatdagidek, ildizni 1 tugunda belgilaymiz.
S(V) orqali V cho‘qqining standart subtree sini belgilaymiz
(V subtree sidagi barcha cho‘qqilar).
Barcha subtree larni sanash
Avval barcha subtree lar sonini (o‘lcham cheklovisiz) hisoblaymiz.
Quyidagicha belgilaymiz:
f(V)=S(V) ichidagi, V ni o‘z ichiga oladigan subtree lar soni
Agar V ning bolalari v1,v2,…,vn bo‘lsa, har bir bola uchun ikki variant bor:
uning subtree sidan hech narsa olmaslik
ildizi vi da bo‘lgan subtree ni olish
Shuning uchun:
f(V)=i=1∏n(1+f(vi))
Biroq bu faqat ildizi V da bo‘lgan subtree larni sanaydi.
Shuningdek, avlodlar ichida yotgan subtree larni ham hisobga olish kerak.
Kiritamiz:
g(V)=S(V) ichidagi, V ni o‘z ichiga olmaydigan subtree lar soni
Unda:
g(V)=u∈children(V)∑(f(u)+g(u))
Daraxtdagi subtree larning umumiy soni:
f(1)+g(1)
O‘lcham cheklovi ≤ K
Endi faqat o‘lchami K dan oshmaydigan subtree larni sanash talab qilinadi.
Aniqroq DP kiritamiz.
DP-holat
f(V,k)=V ildizli, o‘lchami k bo‘lgan subtree lar soni
Unda k+1 o‘lchamli subtree quyidagilardan iborat:
V cho‘qqisi
bolalar subtree larining umumiy o‘lchami k
Bolalarni kombinatsiyalash
V ning bolalari v1,…,vn bo‘lsin.
Agar vi subtree sidan ai ta cho‘qqi olsak, u holda:
∑ai=k
va hissa:
∏f(vi,ai)
k ning barcha bo‘linishlari bo‘yicha yig‘ib, f(V,k+1) ni olamiz.
Lokal DP (bolalar bo‘yicha ryukzak)
Hisoblash uchun oraliq DP yuritish qulay.
Quyidagicha belgilaymiz:
dp[i][j]=birinchi i ta boladan j ta cho‘qqi tanlash usullari soni
O‘tish:
dp[i][j]=t=0∑jdp[i−1][j−t]⋅f(vi,t)
Oxirida:
f(V,k)=dp[n][k−1]
(−1, chunki bitta cho‘qqi — bu V ning o‘zi).
Yakuniy javob
Barcha cho‘qqilar va o‘lchamlar bo‘yicha yig‘ish kerak:
V=1∑Nk=1∑Kf(V,k)
Realizatsiya
Endi murakkablikni tahlil qilaylik. Har bir tugunda n ta bola bo‘lsa, biz n⋅K2 hisoblashni bajaramiz, shuning uchun umumiy murakkablik O(N⋅K2).
Optimallashtirish
Bu musobaqaviy dasturlash olamida juda foydali masala. O‘sha blogda keltirilgan yechim O(n⋅K2) murakkablikka ega, lekin biz uni O(n⋅K) ga o‘zgartirmoqchimiz.
Subv ni v cho‘qqining subtree o‘lchami deb belgilaymiz.
Yechim o‘sha blogdagi yechimga o‘xshaydi, farqi juda sodda. Sizga K ning barcha qiymatlarini ko‘rib chiqish shart emas. Ravshanki, agar i>Subv bo‘lsa, dp[v][i]=0. Shuning uchun har safar min(K,Subv) qiymatlarini ko‘rib chiqishingiz kerak.
Kod quyidagicha bo‘ladi:
Murakkablik isboti
Avval EnterTime massivini kiritamiz. Agar EnterTimev=x bo‘lsa, demak v — aylanib chiqishda biz kirgan x-chi cho‘qqi. Har bir cho‘qqining stv si bor, u massiv bo‘lib, eng boshida barcha v lar uchun stv={v}. Keyinroq biz bu to‘plamni o‘zgartiramiz va qanday o‘zgarishini ko‘ramiz. Shuningdek, stv har doim EnterTime bo‘yicha tartiblangan deb hisoblaymiz.
Biz n o‘lchamli yo‘naltirilgan H grafini qurmoqchimiz. dp[v] ni uning qiz cho‘qqisi u dan yangilamoqchi bo‘lganimizda, H grafida stu dagi har bir cho‘qqidan stv dagi har bir cho‘qqiga yo‘naltirilgan qirra qo‘shamiz.
So‘ng stv ni yangilaymiz: stu dan birinchi K−size(stv) ta cho‘qqini qo‘shamiz (agar size(stv)=K bo‘lsa, bu e’tiborga olinmaydi). Shuningdek, stu dan har bir cho‘qqini o‘chirib tashlaymiz.
Murakkablik H dagi qirralar soniga teng. Biz H dagi qirralar soni n⋅(2K) dan oshmasligini, ya’ni H dagi har bir cho‘qqidan ko‘pi bilan 2K ta chiquvchi qirra borligini isbotlab ko‘rsatmoqchimiz.
Bizning ta’rifimizga ko‘ra, istalgan vaqtda istalgan v cho‘qqi uchun vstu da bo‘ladigan ko‘pi bilan 1 ta u cho‘qqi mavjud. w joylashgan oxirgi to‘plamni ko‘rib chiqamiz, u stu bo‘lib, biz dp[v] ni uning qiz cho‘qqisi u dan yangilamoqchimiz. Faraz qilaylik, wstu da p-o‘rinda turadi. Bizning ta’rifimizga ko‘ra, w dan chiquvchi qirralar — bu stu dagi birinchi p−1 ta cho‘qqiga boradigan qirralar.
Biz bilamizki, p≤K, demak hozirgacha w dan chiquvchi qirralar soni K dan oshmaydi. dp[v] ni yangilaganimizda, bu songa ko‘pi bilan K ni qo‘shamiz. Demak, shu paytda w ko‘pi bilan 2K ta chiquvchi qirraga ega bo‘ladi. Shuningdek, biz stu ni w joylashgan oxirgi to‘plam sifatida ko‘rib chiqdik. Demak, kelajakda w dan chiquvchi boshqa qirralar bo‘lmaydi.
Shunday qilib, biz H dagi qirralar soni n⋅(2K) dan oshmasligini isbotladik, demak murakkablik O(nK) ga teng.
