Rhaglennu deinamig, yr egwyddorion sylfaenol

I ddewis y ateb gorau posibl wrth perfformio weithiau mae'n ofynnol tasgau rhaglennu i ddidoli symiau mawr o gyfuniadau data sy'n llwytho'r cof y cyfrifiadur personol. dulliau o'r fath yn cynnwys, er enghraifft, y dull rhaglennu o "rhaniad a rheol". Yn yr achos hwn mae'r algorithm yn darparu problem gwahanu i mewn i is-dasgau llai ar wahân. Mae'r dull hwn yn berthnasol yn unig yn yr achosion hynny lle mae is-dasgau bach yn annibynnol ar ei gilydd. Er mwyn osgoi perfformio gwaith diangen os yw is-dasgau rhyngddibynnol, yn defnyddio dull rhaglennu deinamig arfaethedig Americanaidd R.Bellmanom yn y 50au.

Mae'r dull

rhaglennu Dynamic yw pennu ateb gorau posibl i'r broblem n-dimensiwn, gan rannu ei n cyfnodau ar wahân. Mae pob un ohonynt yn is-dasg ynglyn ag un newidyn.

Gall y prif fantais y dull hwn yn cael ei ystyried bod y datblygwyr yn rhan o'r broblem optimization un-dimensiwn is-dasgau yn hytrach na broblem n-dimensiwn, ac mae ein prif amcan yn mynd i "gwaelod i fyny".

Fe'ch cynghorir i wneud cais rhaglennu deinamig yn yr achosion hynny lle mae'r is-dasgau yn rhyngberthyn, hy rhannu modiwlau cyffredin. Mae'r algorithm yn rhoi penderfyniad pob un o'r is-dasgau unwaith, ac ymatebion arbed yn cael ei berfformio mewn tabl arbennig. Mae hyn yn ei gwneud yn bosibl i beidio â cyfrifo ateb pan wnaethant gyfarfod eto gyda'r un is-dasg.

tasg rhaglennu deinamig datrys y broblem o optimization. Mae awdur y dull hwn ei llunio gan R. Bellman egwyddor optimality: beth bynnag yw cyflwr cychwynnol pob un o'r camau a'r ateb a ddiffinnir yn y cam hwn, bob un o'r canlynol i ddewis y gorau posibl o ran y wladwriaeth, a oedd yn derbyn y system ar ddiwedd y cam.

Mae'r dull yn gwella perfformiad y tasgau datrys drwy gyfrwng amrywiadau, neu recursion.

algorithm tasg Adeiladu

algorithm rhaglennu deinamig yn cynnwys tasgau fel bod y dasg felly ei rhannu yn ddwy neu fwy o is-dasgau i'w ateb yn cynnwys ateb gorau posibl i bob is-dasgau adeiladu, mae'n cynnwys. Ymhellach, mae angen i ysgrifennu berthynas gylchol, a chyfrifo gwerthoedd paramedr gorau posibl ar gyfer y dasg yn ei gyfanrwydd.

Weithiau, ar y 3ydd cam yw i gofio gwybodaeth gefndir ychwanegol am gynnydd pob tasg. Gelwir hyn yn strôc dychwelyd.

dull ymgeisio

rhaglennu deinamig yn cael ei gymhwyso pan mae dau nodweddion:

• gorau ar gyfer is-dasgau;
• presenoldeb yn y broblem o gorgyffwrdd subproblems.

Datrys y broblem optimization trwy raglennu deinamig, mae angen i chi ddisgrifio strwythur y datrysiad yn gyntaf. Y dasg wedi i fod yn gorau posibl os yw'r ateb yn cynnwys y penderfyniadau gorau o'i is-dasgau. Yn yr achos hwn, fe'ch cynghorir i ddefnyddio rhaglennu deinamig.

Yr ail eiddo y broblem, hanfodol y dull hwn, - nifer fechan o is-dasgau. ateb recursive o'r broblem gan ddefnyddio'r un is-broblemau sy'n gorgyffwrdd, mae nifer ohonynt yn dibynnu ar faint y wybodaeth gychwynnol. Mae'r ateb yn cael ei storio mewn tabl arbennig, mae'r rhaglen yn arbed amser drwy ddefnyddio'r data hwn.

Yn enwedig effeithiol yw'r defnydd o raglennu deinamig pan fo angen yn y bôn y dasg i wneud penderfyniadau mewn camau. Er enghraifft, ystyriwch enghraifft syml o'r broblem o ailosod a thrwsio offer. Gadewch i ni ddweud ar y ffatri peiriant castio ar gyfer cynhyrchu teiars ar yr un pryd yn gwneud y teiars mewn dwy ffurf wahanol. Os bydd un o'r ffurfiau yn methu, mae angen i dadosod y peiriant. Mae'n ddealladwy bod weithiau yn fwy proffidiol i gymryd lle ac ail ffurflen er mwyn dadosod y peiriant rhag ofn a bydd y ffurflen hon yn anymarferol yn y cam nesaf. Yn enwedig gan ei fod yn haws i gymryd lle y ddau siâp gwaith cyn iddynt ddechrau i fethu. Dull rhaglennu deinamig pennu'r strategaeth gorau yn y mater o amnewid ffurflenni hyn, gan ystyried yr holl ffactorau: y manteision o ffurfiau parhaus o gamfanteisio, colli amser segur peiriant, y gost o deiars taflu a mwy.