Ktu algorimtų kolio medžiaga (2)


Topologinis rusiavimas. Matricu kolis. Dinaminis programavimas konvejeris.

Informatikos konspektas. Dinaminis programavimo elementai ( įvadas, optimali substruktūra, pagalbinių uždavinių perdengimas). Dinaminis programavimas: konvejeris. Dinaminis programavimas: matricų daugybos tvarka. Godūs algoritmai: procesų pasirinkimo uždavinys. Godaus algoritmo strategija ( įvadas, optimali substruktūra). Grafų vaizdavimas. Paieška į plotį ( be teiginių įrodymo). Paieška į gylį. Topologinis rūšiavimas. Stipriai susieti komponentai. Minimalūs padengiantys medžiai. Kruskalo algoritmas. Prima algoritmas. Trumpiausi keliai iš vienos viršūnės. Belmano-fordo algoritmas. Deiksra algoritmas. Trumpiausi keliai tarp visų viršūnių porų. Floido-varšalo algoritmas.


atsiranda tuo atveju, jeigu jos optimalus sprendinys apima optimalius sprendinius pagalbinių uždavinių. Jei uždavinyje surandama optimalios struktūros buvimas, tai svarus argumentas, kad uždavinys gali būti sprendžiamas kaip din. progr. užd. (šios savybės buvimas gali rodyti, kad tai ir godus uždavinys). Dinaminio progr. opt. spr. formuojamas iš optimalių sprendinių. Konvejeryje kelias iki j-tosios darbo vietos bus optimalus, jei optimalus kelias iki j-1 vietos. Matricos daugybos atveju parodyta, kad optimali substruktūra AiAi+1... Aj dalinasi į dvi sekas tarp matricų Ak ir Ak+1 ir bus optimaliai padalinta, jei sekos AiAi+1... Ak ir Ak+1,Ak+2..., Aj bus optimalios, t.y. bus optimalu dėti skliaustelius tokiu būdu (AiAi+1... Ak-1 Ak)( Ak+1,Ak+2..., Aj).

Ktu algorimtų kolio medžiaga (2). (2013 m. Kovo 06 d.). http://www.mokslobaze.lt/ktu-algorimtu-kolio-medziaga-2.html Peržiūrėta 2016 m. Gruodžio 05 d. 00:31