Programazio dinamikoa, oinarrizko printzipioak

optimoa irtenbide hautatzeko orduan eszenikoen programazio zereginak dira, batzuetan datuak konbinazioak ordenagailu pertsonala memorian kargatzen duten kopuru handiak ordenatzeko beharrezkoa. Horrelako metodoak artean, adibidez, programazioaren "eten eta arau" metodoa. Kasu honetan algoritmoa bereizketa arazo eskaintzen bereizi azpizereginak txikiagoetan banatzen. Metodo honek kasuetan azpizereginak txikiak elkarren independenteak dira soilik aplikatzen da. alferrikako lanak elkarren mendekoak azpi-zeregin bada eszenikoen ekiditeko, programazio dinamikoa proposatu American R.Bellmanom 50eko hamarkadan metodoa erabiltzen du.

metodoa

programazio dinamikoa da optimoa irtenbide zehazteko n dimentsioko arazoa, bere n bereizi fase partekatzen. Horietako bakoitzak aldagai bat aldean azpi-zeregin bat da.

Ikuspegi honen abantaila nagusia dela esan daiteke bat-dimentsioko optimizazioa arazo inplikatuta garatzaileei azpizereginak ordez n dimentsioko arazoren bat, eta gure helburu nagusia da joan "behetik gora".

Komenigarria da programazio dinamikoa aplikatzeko kasuetan azpi-zeregin erlazionatuta daude, hau ere modulu komunak partekatzeko. Algoritmoa azpizereginak bakoitzaren erabakia ematen du behin eta aurreztea erantzunak mahai berezian landuko. Horrek posible ez erantzun bat kalkulatu denean, berriro bildu dira berdinak azpi-zeregin batera.

Dinamikoa programazio zeregin arazoa konpontzen optimizatu. Metodo honen egilea R. Bellman optima- printzipioa formulatu zen: edozein izanda hasierako urratsak eta urrats hori definitutako soluzio bakoitzaren egoera da, optimoa aukeratzeko egoera, zein sistema jasotzen urratsa amaieran aldean hauetako guztia.

metodoa konpondu aldaera edo errekurtsio bitartez zereginak errendimendua hobetzen du.

Eraikina zeregin algoritmoa

Dinamikoa programazio algoritmoa zereginak, hala nola, zeregin orain bi edo gehiago azpizereginak zatitzen bere konponbidea azpizereginak guztiei irtenbidea optimoa bat osatzen eraikitzea dakar, berau barne. Gainera, beharrezkoa da errepikapena erlazio bat idazteko, eta zeregin osotasunean lortuta parametro balioak kalkulatzeko.

Batzuetan, 3. urratsa da zenbait hondo zeregin bakoitzaren aurrerapenei buruzko informazio osagarria memorizatzeko. Hau deitzen da itzulera trazua.

Aplikazio metodoa

programazio dinamikoa aplikatuko da orduan ezaugarria bi ezaugarri hauek dira:

• azpizereginak optimoa;
• subproblems gainjarriz arazoa presentzia.

optimizazioa arazoa programazio dinamikoa by konpontzea, lehen konponbidea egitura deskribatzeko behar duzu. Zeregin ditu optimoa izateko irtenbidea da bere azpizereginak erabakiak onenetako osatzen bada. Kasu honetan, komeni da programazio dinamikoa erabiltzeko.

Arazoa bigarren Jabetza da, ezinbestekoa Metodo honetan, - azpi-zeregin kopuru txiki bat. arazoaren konponbidea errekurtsiboa teilakatzen azpi-arazo berdinak erabilita, eta horrek kopuruaren hasierako informazio tamainaren araberakoa da. Erantzuna mahai berezi batean gordetzen dira, programa aurrezten denbora datu horiek erabilita.

Bereziki eraginkorra programazio dinamikoa denean zeregina, funtsean behar da erabakiak hartzeko fasetan erabilera da. Adibidez, ordezko eta ekipamenduen konponketa arazoa adibide sinple bat. Demagun casting makina pneumatikoak ekoizteko fabrika, aldi berean on pneumatikoen egiteko bi modu desberdinetan. Gertaera forma bat huts egiten horretan, beharrezkoa da makina desmuntatzen. Ulergarria da, batzuetan gehiago errentagarria dela ordezkatu eta ordena makina desmuntatu kasuan bigarren formulario bat eta formulario honen hurrengo fasean unworkable izango da. Batez ere errazagoa da lan forma biak ordezkatu huts hasi aurretik geroztik. Dinamikoa programazio metodoaren forma horien ordez materia estrategia onena ezartzen du; kontuan faktore guztiak hartzen: esplotazio modu jarraitu, makina downtime, baztertu pneumatikoak eta gehiago kostua galtzea onurak.