Dynamic programu, kanuni za kimsingi

Kuchagua ufumbuzi mojawapo wakati wa kutekeleza majukumu ya programu ni wakati mwingine wanatakiwa kutatua kiasi kikubwa cha mchanganyiko data kwamba mizigo kumbukumbu ya kompyuta binafsi. mbinu hizi ni pamoja na, kwa mfano, njia ya programu ya "kugawa na kutawala". Katika hali hii algorithm hutoa tatizo kujitenga katika kazi ndogo tofauti ndogo. Njia hii inatumika tu katika matukio hayo ambayo kazi ndogo ndogo ni pande huru. Ili kuepuka kufanya kazi ya lazima kama kutegemeana kazi ndogo, hutumia nguvu ya programu njia zilizopendekezwa American R.Bellmanom katika 50s.

Mbinu

Programu Dynamic ni kuamua ufumbuzi mojawapo ya tatizo n-dimensional, wakishiriki n hatua yake tofauti. Kila mmoja wao ni ndogo kazi kuhusiana na kutofautiana moja.

Faida kuu ya njia hii inaweza kuchukuliwa kwamba watengenezaji kushiriki katika tatizo moja ya pande optimization kazi ndogo badala ya tatizo n-dimensional, na lengo letu la msingi ni kwenda na "bottom-up".

Ni vyema kuomba nguvu ya programu katika matukio hayo ambayo ndogo kazi wa uhusiano, yaani kushiriki modules ya kawaida. algorithm hutoa uamuzi wa kila mmoja kazi ndogo mara moja, na majibu ya kuokoa ni kazi katika meza maalum. Hii inafanya kuwa inawezekana si kufanya mahesabu jibu wakati wao walikutana tena kwa hiyo ndogo ya kazi.

Dynamic programu kazi kutatua tatizo la Biashara. mwandishi wa njia hii ilikuwa yaliyoandaliwa na R. Bellman optimality kanuni: chochote ni hali ya awali ya kila moja ya hatua na ufumbuzi inavyoelezwa katika hatua hii, yote yafuatayo ili kuchagua mojawapo kuhusiana na hali, ambayo inapokea mfumo katika mwisho wa hatua.

Mbinu inaboresha utendaji wa kazi kutatuliwa kwa njia ya variants, au recursion.

Vifaa kazi algorithm

Dynamic programu algorithm unahusu ujenzi wa kazi kiasi kwamba kazi hiyo ni umegawanyika katika kazi ndogo mbili au zaidi ili ufumbuzi wake linajumuisha ufumbuzi mojawapo kwa kazi ndogo zote, ni pamoja na. Zaidi ya hayo, ni muhimu kuandika kujirudia uhusiano, na kuhesabu optimum maadili parameter kwa kazi kwa ujumla.

Wakati mwingine, juu ya hatua ya 3 ni ya kukariri baadhi background maelezo ya ziada juu ya maendeleo ya kila kazi. Hii inaitwa kurudi kiharusi.

Mbinu maombi

Programu Dynamic hutumika wakati kuna sifa mbili tabia:

• mojawapo kwa kazi ndogo,
• kuwepo kwa tatizo la zinazobadilika subproblems.

Kutatua tatizo optimization kwa programu nguvu, unahitaji kwanza kuelezea muundo wa ufumbuzi. Kazi ina kuwa mojawapo ikiwa ufumbuzi linajumuisha maamuzi bora ya kazi ndogo yake. Katika hali hii, ni vyema kutumia nguvu ya programu.

mali ya pili ya tatizo, muhimu katika njia hii, - idadi ndogo ya kazi ndogo. Kujirudia ufumbuzi wa tatizo la kutumia huo zinazoingiliana ndogo matatizo, idadi ambayo inategemea ukubwa wa habari wa awali. jibu ni kuhifadhiwa katika meza maalum, mpango anaokoa muda kwa kutumia data hii.

Hasa ufanisi ni matumizi ya programu nguvu wakati kazi ni kimsingi zinazohitajika ili kufanya maamuzi katika hatua. Kwa mfano, fikiria mfano rahisi ya tatizo la uingizwaji na matengenezo ya vifaa. Tuseme juu akitoa mashine kiwanda kwa ajili ya uzalishaji wa matairi wakati huo huo kufanya gurudumu katika aina mbili tofauti. Iwapo mojawapo ya aina inashindwa, ni muhimu kutenganisha mashine. Inaeleweka kwamba wakati mwingine zaidi faida badala na fomu pili ili kutenganisha mashine katika kesi na fomu hii itakuwa unworkable katika hatua ya pili. Hasa tangu ni rahisi kuchukua nafasi ya sura zote mbili za kazi kabla ya kuanza kushindwa. Dynamic programu Mbinu huamua mkakati bora katika suala la uwekaji wa aina hii, kwa kuzingatia mambo yote: faida za aina kuendelea unyonyaji, kupoteza mashine downtime, gharama ya tairi kuondolewa na zaidi.