Matematické Fórum

ziky · 02. 12. 2013 19:54

Dobrý den,

Řeším v současné době problém, jak za pomoci principu dynamického programování najít ve stromu počet všech maximálních nezávislých množin vrcholů. Chtěl bych se nejdříve zeptat, jestli je vůbec možné tento problém vyřešit pomocí dynamického programování (myslím, že by to mělo jít, ale nemůžu zatím přijít na to, jak). Doteď se mi podařilo přijít na to, jak pomocí dp zjistit její velikost nebo jak zjistit velikost největší vážené, ale s tímto problémem nějak nemohu hnout.

Předem děkuji za odpověď.

vojta_vorel · 05. 12. 2013 08:44

Ahoj

Rád se nad tím taky zamyslím, ale pro zčátek napiš, jak přesně postupuješ při tom zjišťování maximální velikosti nezávislé množiny, ať se máme od čeho odrazit. A budou se tedy brát v potaz i nějaké váhy vrcholů?

Vojta

ziky · 05. 12. 2013 13:36 — Editoval ziky (05. 12. 2013 15:59)

Takže provádím klasické DP vycházím z listů a myslím, že by mělo být možné nakombinovat výsledek z následujících čtyř čísel: s = velikost maximální nezávislé množiny obsahující aktuální kořen, s' = velikost maximální nezávislé množiny bez kořene, n = počet maximálních nezávislé množin s kořenem a n' = počet maximálních nezávislých množin bez kořene.

Přišel jsem již na to, že:
$s = 1 + \sum_{i}^{n}s_i'$
$s' = \sum_{i}^{n}max(s_i, s'_i)$

Problém mám s odvozením vzorečku pro n, n' a pro následné zkombinování čísel, když s==s'. V případech, kdy s>s' by mělo být výsledkem n a kdy s<s' pak n'.

Váhy vrcholů v potaz neberu, jen jsem si to vyzkoušel a doufal, že mě u toho napadne, jak na původní problém.

edit:
tak už se mi podařilo zjistit, že pravděpodobně:
$n = \prod_i^n(n'_i)$

A když s = s' tak výsledek je n+n'

Takže mi chybí už jen to, jak zjistit n' a ověření toho, že je to opravdu, tak jak si myslim.

vojta_vorel · 05. 12. 2013 16:25

↑ ziky:
Ahoj
Podle mě máš pravdu. A řekl bych, že pro spočítání $n'$ se stačí zamyslet jen o trochu víc. Každá největší nez. mn. neobsahující aktuální kořen je poskládaná z:
- nějaké nejv. nez. mn. prvního podstromu
- nějaké nejv. nez. mn. druhého podstromu
...atd...
- nějaké nejv. nez. mn. posledního podstromu
a tyhle části můžu vybrat prostě jakkoliv, takže se bude zase násobit přes všechna i. Ale jaké členy v tom produktu budou? Bude to počet největších nezávislých množin v i-tém podstromě. Kolik jich je? Pokud $s'_i>s_i$ , tak každá největší je bez kořene a je jich $n'_i$ . Pokud $s_i>s'_i$ , každá největší je s kořenem a je jich $n_i$ . A pokud $s'_i=s_i$ , existují největší s kořenem i největší bez kořene a je jich $n'_i+n_i$ .
Žádný hezká formulka, ale k naprogramování brnkačka..

Co ty na to? Za správnost neručím..
Vojta