Programimi dinamik, parimet themelore

Për të zgjedhur zgjidhje optimale kur kryejnë detyrat e programimit janë nganjëherë të nevojshme për të zgjidhur sasi të mëdha të kombinimeve të dhënave që ngarkon kujtesën e kompjuterit personal. Këto metoda përfshijnë, për shembull, metoda programimi i "përçaj e sundo". Në këtë rast algorithm ofron problemin e ndarjes në subtasks të veçanta të vogla. Kjo metodë është e aplikueshme vetëm në ato raste kur subtasks vogla janë reciprokisht të pavarura. Për të shmangur kryerjen e punës të panevojshme nëse nën-detyrave të ndërvarura, përdor metodën e programimit dinamik propozuar amerikan R.Bellmanom në vitet '50.

Metoda

programimi dinamik është për të përcaktuar zgjidhje optimale e problemit n-dimensionale, duke ndarë n fazat e saj të veçanta. Secili prej tyre është një nën-detyrë në lidhje me një ndryshore.

Avantazhi kryesor i kësaj qasjeje mund të konsiderohet se zhvilluesit e përfshirë në një-dimensionale problemit optimization subtasks në vend të një problem n-dimensionale, dhe objektivi ynë kryesor do të "poshtë-lart".

Është e këshillueshme për të aplikuar programe dinamike në ato raste kur nën-detyrat e janë të ndërlidhura, dmth ndajnë module të përbashkëta. Algorithm jep vendimin e secilit prej subtasks një herë, dhe përgjigjet e kursimit është kryer në një tryezë të veçantë. Kjo bën të mundur për të mos llogaritur një përgjigje kur ata u takuan sërish me të njëjtën nën-detyrë.

Dynamic detyra programimi zgjidh problemin e optimization. Autori i kësaj metode është formuluar nga R. Bellman parim optimality: çdo gjë që është gjendja fillestare e secilit prej hapave dhe zgjidhjen e përcaktuar në këtë hap, të gjitha sa më poshtë për të zgjedhur optimale në lidhje me shtetin, i cili merr të sistemit në fund të hapit.

Metoda e përmirëson performancën e detyrave të zgjidhura me anë të variante, ose recursion.

Building detyrë algorithm

Dynamic programimit algorithm përfshin ndërtimin e detyra të tilla se detyra kështu është e ndarë në dy ose më shumë subtasks për zgjidhjen e tij është e përbërë nga një zgjidhje optimale për të gjitha subtasks, ajo përfshin. Më tej, është e nevojshme për të shkruar një lidhje përsëritje, dhe llogaritjen e vlerave optimale parametër për këtë detyrë si një e tërë.

Ndonjëherë, në hapin 3 është për të mësuar përmendësh disa informacione shtesë sfond mbi progresin e çdo detyrë. Kjo quhet goditje kthimi.

Metoda e aplikimit

programimi dinamik zbatohet kur ka dy tiparet karakteristike:

• optimal për subtasks;
• Prania në problemin e mbivendosjes subproblems.

Zgjidhja e problemit optimization nga programimi dinamik, ju së pari duhet për të përshkruar strukturën e zgjidhjes. Detyra duhet të jetë optimale, nëse zgjidhja është e përbërë nga vendimet më të mira të subtasks saj. Në këtë rast, është e këshillueshme që të përdorin programe dinamike.

Prona e dytë e problemit, thelbësor në këtë metodë, - një numër i vogël i nën-detyrave. zgjidhja rekursive e problemit duke përdorur të njëjtën nën-probleme mbivendosje, numri i të cilave varet nga madhësia e informacionit fillestar. Përgjigja është ruajtur në një tryezë të veçantë, programi kursen kohë duke përdorur këto të dhëna.

Veçanërisht efektive është përdorimi i programimit dinamik, kur detyra është në thelb e nevojshme për të marrë vendime në faza. Për shembull, e konsiderojnë një shembull të thjeshtë e problemit të zëvendësimit dhe riparimin e pajisjeve. Le të thonë se në fabrikën e hedh makinë për prodhimin e gomave në të njëjtën kohë të bëjë gomave në dy forma të ndryshme. Në rast se një nga format dështon, është e nevojshme për të çmontimit makinë. Është e kuptueshme që nganjëherë më e dobishme për të zëvendësuar dhe një formë të dytë në mënyrë që të çmontimit makinë në rast dhe kjo formë do të jetë jofunksionale në fazën e ardhshme. Sidomos pasi është më e lehtë për të zëvendësuar dy forma pune para se të fillojnë të dështojnë. Metoda e programimit dinamik përcakton strategjinë më të mirë në çështjen e zëvendësimit të këtyre formave, duke marrë parasysh të gjithë faktorët: Përfitimet e formave të vazhdueshme të shfrytëzimit, humbja e joproduktive makine, kostoja e gomave fshi dhe më shumë.