Note de curs, probleme algoritmică, 2 decembrie 2013

From Algopedia
Revision as of 23:10, 17 January 2014 by Dan (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Î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ă.