Matematické Fórum

↑ turcovsky:
Ahoj, co je "kriterium hladovosti", tj. kterou aktivitu vybere hladový algoritmus jako první?

Ahoj, důkaz je asi celkem snadný, ale nepřišel jsem na nějaký jednoduchý. Avšak pokud budeme dokazovat silnější tvrzení a sice, že navíc dokážeme, že pokud náš hladový algoritmus A vybere stejný počet aktivit jako nějaký jiný algoritmus B, pak poslední úloha vybraná algoritmem A neskončí později než poslední úloha vybraná algoritmem B, pak je důkaz dle mého o mnoho snazší.

↑ turcovsky:
A znáš princip důkazu matematickou indukcí?
Chápeš princip toho hladového algoritmu?
Až budou odpovědi na obě otázky "ano", pak budeme pokračovat dále.

Napřed musíme ověřit:
1) hladový výběr nezablokuje cestu k optimálnímu řešení
2) každé optimální řešení řešení vypadá tak, že když z něj odeberu první aktivitu, tak zbytek je nějaké optimální řešení menšího problému (princip optimální podstruktury)

Indukční krok: ukázat, že algoritmus najde optimální řešení pro n aktivit, za předpokladu, že najde optimální řešení pro n-1, n-2, ..., 0 aktivit. Hladovým výběrem zmenším počet aktivit a ve zbylých aktivitách najdu optimální řešení. Díky 1) vím,  že existuje optimální řešení v němž je vybrána aktivita, kterou vybral hladový výběr a díky 2) vím, že tohle optimální řešení lze složit z optimálního řešení menšího problému.

↑ radekm:↑ radekm:
Ahoj díky, že ses také zapojil, dokázal by jsi to nějak hodit na papír? Lépe bych to z toho pochopil, nicméně z toho co jsi napsal, jsem přece jen o trochu chytřejší ;-)