დპ ხეებზე

ორგანიზაციული სქემები, ფაილური სისტემები, კომენტარების ხეები და ქსელის ტოპოლოგიები ხეებია. მათზე ბევრი „საუკეთესო არჩევანის“ კითხვა, მაგალითად რაც შეიძლება მეტი ადამიანის მოწვევა ისე, რომ არცერთი უფროსი და მისი ქვეშევრდომი ერთად არ იყოს, წრფივ დროში იხსნება, თუ ყოველი წვერო შვილების პასუხებს აერთიანებს.

მოწინავე⏱ 12 წთ

←ეყრდნობა

10დპ-ის საფუძვლები: მემოიზაცია და ცხრილიხეზე დპ იგივე მემოს იდეაა, თითო მდგომარეობით ყოველ წვეროზე.6სიღრმეში ძებნა (DFS)წვეროს პასუხი მაშინ ითვლება, როცა DFS მას ტოვებს, ყველა შვილის შემდეგ.6ხის დიამეტრი და ცენტრიდიამეტრი ხეზე დპ-ითაც გამოითვლება: ყოველ წვეროში ორი უღრმესი შვილის განშტოება შეაერთე.

გზას უხსნის→

აქ გზამკვლევი სრულდება. გადახედე, რა გზა გაიარე.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01პასუხები ფოთლებიდან ზემოთ ადის

სათავიან ხეზე ბუნებრივი ქვეამოცანაა „პასუხი v-ს ქვეხისთვის“. სხვადასხვა შვილის ქვეხეები არ იკვეთება, ხოლო v-ს ქვეხე უბრალოდ v-ს და მისი შვილების ქვეხეებისგან შედგება. ამიტომ:

მდგომარეობა წვეროებზეა: dp[v], ზოგჯერ პატარა დამატებითი ნიშნით;
რიგი post-order DFS-ია: ყოველი შვილი მშობლამდე სრულდება;
ყოველი წვერო შვილების მნიშვნელობებს აერთიანებს, ამიტომ ყოველ წიბოს ერთხელ ვუყურებთ: ჯამში O(n).

უმარტივესი მაგალითი ქვეხის ზომაა: size[v] = 1 + Σ size[შვილი]. ფოთლების ზომა 1-ია, სათავე კი n-ს იღებს. ტრივიალურად გამოიყურება, მაგრამ ზომები ყველგან გამოიყენება: წიბოზე გამავალი წყვილების დათვლა, ცენტროიდის პოვნა, მძიმე-მსუბუქი დეკომპოზიცია.

რეკურსიით წერა ყველაზე მარტივია; ძალიან ღრმა ხეებისთვის (10⁵ წვეროიანი ჯაჭვი) სტეკის გადავსების თავიდან ასაცილებლად ცხადი სტეკი გამოიყენე.

02ორი მდგომარეობა წვეროზე: ავიღოთ თუ არა

მაქსიმალური დამოუკიდებელი სიმრავლე: ავირჩიოთ რაც შეიძლება მეტი წვერო ისე, რომ არცერთი ორი არჩეული წიბოთი არ იყოს შეერთებული. ზოგად გრაფზე ეს NP-რთულია; ხეზე მარტივია.

წვეროზე ერთი რიცხვი არ კმარა, რადგან მშობელმა უნდა იცოდეს, თავად შვილი აირჩა თუ არა. ამიტომ ორს ვინახავთ:

take[v] = საუკეთესო ზომა v-ს ქვეხეში, თუ v არჩეულია. მაშინ ვერცერთ შვილს ვერ ავირჩევთ: take[v] = 1 + Σ skip[c].
skip[v] = საუკეთესო ზომა v-ს გარეშე. მაშინ ყოველი შვილი თავისუფალია: skip[v] = Σ max(take[c], skip[c]).

ფოთლებისთვის take = 1, skip = 0. პასუხია max(take[root], skip[root]).

„დამატებითი ნიშანი მდგომარეობაში“ ხეზე დპ-ის გულია. როცა v-ში გაკეთებული არჩევანი შვილებს ზღუდავს (ფერები, წყვილები, დაცვა წვეროებზე), არჩევანი მდგომარეობას დაუმატე.

03გაშვება და სიმრავლის აღდგენა

მაგალითის ხეზე, სათავით 4, post-order ჯერ ფოთლებს ავსებს (1, 0), შემდეგ 1 იღებს (1, 1)-ს, 7 იღებს (2, 2)-ს, 3 იღებს (1, 1)-ს, 8 იღებს (2, 2)-ს, სათავე კი take = 1 + 2 + 2 = 5, skip = 2 + 2 = 4. პასუხია 5.

წვეროების ჩამოსაწერად სათავიდან ქვემოთ მივდივართ: თუ v დასაშვებია და take[v] ≥ skip[v], ვირჩევთ v-ს და შვილებს ვკრძალავთ; სხვა შემთხვევაში v-ს ვტოვებთ და შვილები თავად წყვეტენ. აქ ეს {4, 6, 1, 3, 5}-ს ირჩევს.

იგივე ორგავლიანი იდეა (ზემოთ მნიშვნელობებისთვის, ქვემოთ არჩევანისთვის) ხსნის წყვილების (matching) და მინიმალური წვეროვანი დაფარვის ამოცანებს. მეორე ოჯახი, გადასათავება (rerooting), ამატებს ქვემოთ გავლას, რომელიც ყოველ შვილს „პასუხს ჩემი ქვეხის გარედან“ გადასცემს, და ასე, მაგალითად, ყოველი წვეროდან მანძილების ჯამს O(n)-ში იღებ.

ყოველი წარწერა არის (take, skip). მწვანე წვეროები მაქსიმალურ დამოუკიდებელ სიმრავლეს ქმნის.

ფასი ერთი შეხედვით

შვილების გამაერთიანებელი ნებისმიერი დპ ხეზეO(n)

არჩეული სიმრავლის აღდგენაO(n)

გადასათავება (პასუხი ყოველი სათავისთვის)O(n)

დაიმახსოვრე

სხვადასხვა შვილის ქვეხეები დამოუკიდებელია, ამიტომ dp[v] შვილებიდან post-order რიგით ითვლება, ჯამში O(n).
როცა v-ში არჩევანი შვილებს ზღუდავს, ყოველი არჩევანისთვის ცალკე მნიშვნელობა შეინახე, მაგ. take[v] და skip[v].
მნიშვნელობები ზემოთ ადის; რეალური არჩევანის აღსადგენად სათავიდან ქვემოთ ჩადი.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე, როგორ ჩნდება t:take s:skip ყოველი წვეროს ქვეშ post-order რიგით, ჯერ ფოთლებზე, შემდეგ კი ქვემოთ გავლა არჩეულ სიმრავლეს აფერადებს.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

დინამიური პროგრამირება ხეზე: მაქსიმალური დამოუკიდებელი სიმრავლე

მაქსიმალური დამოუკიდებელი სიმრავლე: ავირჩიოთ მაქსიმალურად ბევრი წვერო ისე, რომ არცერთი ორი მეზობელი არ იყოს. ხეზე DFS + შვილების გაერთიანება ამას O(n)-ში ხსნის.

ფსევდოკოდი

 1 post-order (children before parent): 2   take[v]  = 1 + Σ skip[child]        // v chosen ⇒ children excluded 3   skip[v]  = Σ max(take[c], skip[c])  // v free ⇒ children may be chosen 4 answer at root = max(take[root], skip[root]) 5 walk down choosing take/skip consistently to recover the set

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

წვეროს სამი შვილი ჰყავს, სამივე ფოთოლია. რას უდრის მისი take და skip?

№2

რა რიგით უნდა გამოითვალოს ხეზე დპ-ის მნიშვნელობები?

№3

რატომ არ მუშაობს იგივე take/skip იდეა პირდაპირ ციკლებიან გრაფზე?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

CSESSubordinates დამწყები↗LeetCodeHouse Robber III საშუალო↗CSESTree Matching საშუალო↗CSESTree Diameter საშუალო↗CSESTree Distances II მოწინავე↗