"alamprobleemide" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

Algoritmid ja andmestruktuurid 2015 6 2.3 Divide and Conquer ehk jaga ja valitse Kogu meetod on oma olemuselt rekkursiivne (st jaga ülesanne tükkideks ja tükid omakorda tükkideks kuni saadakse sobiva suursega tükid, mida on paras lahendada) • Probleem jagatakse mitmeks alamprobleemiks, mis lahendatakse üksteisest sõltumatult. • Seejärel ühendateakse alamprobleemide lahendused nö alt üles ja saadakse lahendus kogu probleemile. 2.3.1 Omadused: • Minimaalne sisendi mõõt n0 – kui probleemi suurs on alla selle ei hakata probleemi jagama. • Alamprobleemi suurus, milleks kogu probleem jagatakse – milline suurus on paras? • Jagamisel saadavate alamprobleemide arv – liiga palju alamprobleeme pole ka hea • Algoritm, mida kasutakse alamprobleemide lahenduste ühendamiseks, sellest sõltub ka lahenduse