Programmazzjoni dinamiku, il-prinċipji bażiċi

Biex tagħżel is-soluzzjoni ottimali meta jwettqu l-kompiti ta 'programmazzjoni huma kultant meħtieġa biex issolvi ammonti kbar ta' kombinazzjonijiet ta 'dejta li tagħbijiet-memorja tal-kompjuter personali. Dawn il-metodi jinkludu, per eżempju, il-metodu ipprogrammar ta ' "firda u l-istat". F'dan il-każ l-algoritmu jipprovdi problema separazzjoni fi subtasks separati iżgħar. Dan il-metodu huwa applikabbli biss fil-każijiet fejn subtasks żgħar huma reċiprokament indipendenti. Biex jiġi evitat li jwettqu xogħol bla bżonn jekk sub-kompiti interdipendenti, tuża metodu programmazzjoni dinamiku propost Amerikana R.Bellmanom fl-50s.

il-metodu

programmazzjoni dinamiku huwa li jiddetermina s-soluzzjoni ottimali-problema n dimensjonali, qsim n stadji separati tagħha. Kull wieħed minnhom huwa sub-kompitu fir-rigward varjabbli waħda.

Il-vantaġġ prinċipali ta 'dan l-approċċ jista' jitqies li l-iżviluppaturi involuti fil-problema ottimizzazzjoni dimensjonali wieħed subtasks minflok problema n dimensjonali, u l-għan ewlieni tagħna se "minn isfel għal fuq".

Huwa rakkomandabbli li tapplika programmazzjoni dinamiku f'dawk il-każijiet fejn is-sub-kompiti huma interrelatati, jiġifieri jaqsmu moduli komuni. L-algoritmu tipprovdi d-deċiżjoni ta 'kull subtasks darba, u risponsi ffrankar hija mwettqa fit-tabella speċjali. Dan jagħmilha possibbli li ma tikkalkulax tweġiba meta ltaqgħu għal darb'oħra bl-istess sotto-kompitu.

kompitu dinamika programmazzjoni issolvi l-problema ta 'ottimizzazzjoni. L-awtur ta 'dan il-metodu kien ifformulata mill-prinċipju optimality R. Bellman: dak kollu li huwa l-istat inizjali ta' kull passi u s-soluzzjoni definita f'dan il-pass, dawn kollha li ġejjin li jagħżlu l-aħjar fir-rigward tal-istat, li tirċievi s-sistema fl-aħħar tal-pass.

Il-metodu jtejjeb il-prestazzjoni tal-kompiti solvuti permezz ta 'varjanti, jew recursion.

Bini algoritmu kompitu

algoritmu programmazzjoni dinamiku jinvolvi l-bini ta 'tali kompiti li l-kompitu hekk huwa maqsum fi tnejn jew aktar subtasks li s-soluzzjoni tiegħu huwa kompost ta' soluzzjoni ottimali għall subtasks kollha, dan jinkludi. Barra minn hekk, huwa meħtieġ li tikteb relazzjoni rikorrenza, u jiġu kkalkulati l-valuri tal-parametri aħjar għall-kompitu kollha kemm hi.

Kultant, fit-3 pass huwa li jimmemorizza xi informazzjoni addizzjonali ta 'sfond dwar il-progress ta' kull kompitu. Dan jissejjaħ l-puplesija ritorn.

metodu ta 'applikazzjoni

programmazzjoni dinamiku huwa applikat meta jkun hemm żewġ karatteristiċi:

• ottimali għall subtasks;
• preżenza fil-problema ta 'overlapping subproblems.

Tissolva l-problema ottimizzazzjoni mill programmazzjoni dinamiku, inti l-ewwel bżonn biex jiddeskrivu l-istruttura tas-soluzzjoni. Il-kompitu għandu jkun ottimali jekk is-soluzzjoni hija komposta mill-aħjar deċiżjonijiet tal subtasks tagħha. F'dan il-każ, huwa rakkomandabbli li tuża programmazzjoni dinamiku.

It-tieni proprjetà tal-problema, li huwa essenzjali f'dan il-metodu, - numru żgħir ta 'sub-kompiti. Soluzzjoni rikursivi tal-problema jużaw l-istess sub-problemi jikkoinċidu, in-numru ta 'liema jiddependi fuq id-daqs tal-informazzjoni inizjali. It-tweġiba hija maħżuna fit-tabella speċjali, il-programm jiffranka ħin billi tuża din id-data.

Effettivi b'mod partikolari huwa l-użu ta 'programmazzjoni dinamiku meta l-kompitu essenzjalment meħtieġa biex jagħmlu deċiżjonijiet fi stadji. Per eżempju, jikkunsidraw eżempju sempliċi tal-problema ta 'sostituzzjoni u t-tiswija ta' tagħmir. Ejja ngħidu fuq il-fabbrika ikkastjar magna għall-produzzjoni ta 'tajers fl-istess ħin jagħmlu l-ilqugħ f'żewġ forom differenti. Fil-każ li waħda mill-forom jonqos, huwa meħtieġ li disassemble-magna. Wieħed jifhem li xi kultant aktar profittabbli li tissostitwixxi u formola oħra sabiex disassemble l-magna fil-każ u din il-formola se jkun fattibbli fl-istadju li jmiss. Speċjalment peress li huwa aktar faċli li tieħu post kemm forma ta 'xogħol qabel ma jibdew jonqsu. Metodu programmazzjoni dinamiku jiddetermina l-aħjar strateġija fil-kwistjoni tas-sostituzzjoni ta 'dawn il-formoli, filwaqt li jitqiesu l-fatturi kollha: l-benefiċċji ta' forom kontinwi ta 'sfruttament, telf ta' waqfien tal-magni, l-ispiża ta 'tajers mormija u aktar.