Note de curs, probleme algoritmică, 2 decembrie 2013
În acest curs am discutat despre problema 1463 - Happiness to People!.
Cerință
Dându-se un arbore cu muchii ponderate (cu costuri) și cu noduri ponderate (cu costuri) să se calculeze cel mai lung drum dintre două noduri din întreg arborele.
Rezolvare
Inițial, vom stabili arbitrar un nod (de ex. nodul 1) drept rădăcină pentru arbore și vom orienta toate muchiile în funcție de acesta.
Dinamică pe arbore
Această problemă se rezolvă prin calcularea unor valori (funcții) pentru fiecare dintre nodurile arborelui. Una dintre acestea este:
bestHappiness(node) = lungimea celui mai lung drum care trece prin nodul node și folosește noduri din subarborele cu rădăcina node
Acest drum este format prin alipirea a două drumuri care pornesc din node și continuă în subarborele său prin doi fii diferiți. De aceea, pentru a calcula funcția bestHappiness, trebuie să cunoaștem: (1) lungimea celui mai lung drum cu un capăt într-un nod și celălalt capăt în subarborele asociat nodului respectiv și (2) lungimea celui de-al doilea cel mai lung drum (nu are nicio muchie comună cu cel mai bun) cu un capăt într-un nod și celălalt capăt în subarborele asociat nodului respectiv. Astfel, va trebui să calculăm și funcțiile:
bestRoad(node) = lungimea celui mai lung drum cu un capăt în node și celălalt capăt în subarborele asociat lui node secondRoad(node) = lungimea celui de-al doilea cel mai lung drum cu un capăt în node, și celălalt capăt în subarborele asociat lui node (nu are nicio muchie comună cu cel mai lung drum)
Vom introduce următoarele notații:
happiness(node) = costul nodului node happiness(nodeA, nodeB) = costul muchiei care unește nodurile nodeA și nodeB
Folosind notațiile anterioare, cele 3 funcții definite anterior se pot calcula folosind formulele:
bestRoad(node) = happiness(node), dacă node nu are fii max(son in sons, happiness(node) + happiness(node, son) + bestRoad(son)), dacă node are fii secondRoad(node) = happiness(node), dacă node nu are fii secondMax(son in sons, happiness(node) + happiness(node, son) + bestRoad(son)), dacă node are fii bestHappiness(node) = bestRoad(node) + secondRoad(node) - happiness(node)
Ordinea calculării funcțiilor
Se observă că pentru a calcula valorile celor 3 funcții pentru un nod trebuie să cunoaștem valorile acestor funcții pentru toți fiii acelui nod. Așadar, va trebui să ordonăm nodurile "de jos în sus".
Un arbore admite o multitudine de ordonări ale nodurilor "de jos în sus". Există două modalități rapide prin care putem obține două astfel de ordonări:
- Parcurgerea în postordine;
- Parcurgerea în lățime inversată.