Վիքիպեդիա

Haso1111

Joined 25 Նոյեմբերի 2011
The ծրագրավորման հարացույց Դինամիկ ծրագրավորում լեզուն, տես՝ Haso1111 (այլ կիրառումներ):

մաթեմատիկայում և [համակարգչային գիտությունում]], Դինամիկ ծրագրավորում –ը դա մի մեթոդ է հասարակ ենթախնդիրներ լուծելուց հետո ավելի բարդ խնդիրները լուծելու համար. Դա կիրառելի մասնավորապես ենթախնդիրների խնդիրների ցուցադրելու հատկություններն է : Դինամիկ ծրագրավորման հիմնական գաղափարը մնում է միանգամայն պարզ. Ընդհանուր առմամբ , լուծել տվյալ հիմնախնդիրություն, մենք պետք է լուծենք խնդրին տարբեր հատվածները ( ենթախնդիրներ ), ապա համատեղել ենթախնդիրների լուծումները և գալ համընդհանուր լուծումներ. Հաճախ այդ ենթախմբի խնդիրներից շատերն իսկապես նույնն են. Դինամիկ ծրագրավորում մոտեցումը նպատակ ունի լուծելու յուրաքանչյուր ենթախնդիր միայն մեկ անգամ `այսպիսով նվազեցնելով մի շարք հաշվարկներ. Սա հատկապես օգտակար է, երբ կրկնվող ենթախնդիրների մեկնաբանությունը մեծ է:

Top-ցած դինամիկ ծրագրավորման պարզապես նշանակում է պահելու արդյունքները, որոշ հաշվարկներով, որոնք հետագայում օգտագործվում է, քանի որ հաշվարկի ավարտված է ենթաօրենսդրական խնդիրն ավելի մեծ հաշվարկման. Ստորին-up դինամիկ ծրագրավորման ներառում ձեւակերպման բարդ հաշվարկ որպես recursive շարք պարզ հաշվարկներից:

պատմություն խմբագրել

Դինամիկ ծրագրավորում ը ի սկզբանե օգտագործվել է 1940 - ականներից: Richard Bellman նկարագրել խնդիրներ լուծելու գործընթացը որտեղ պետք է գտնել լավագույն որոշումներից մեկը մյուսի հետեւից: Ըստ 1953 թ., Նա նկարագրել է սա ժամանակակից իմաստով, անդրադառնալով հատկապես խոշոր որոշումների փոքր որոշումներով խնդիրների ներսում , իսկ դրանից հետո դաշտը ճանաչվել է IEEE, որպես Համակարգային վերլուծության ինժեներական թեման. Bellman է էական ներդրում է հիշում անունով, իսկ Bellman հավասարումը, որը կենտրոնական արդյունք է դինամիկ ծրագրավորմամբ, որոնց համար նշվում է օպտիմալացման խնդիր ռեկուրսիա ձեւով. Դինամիկ բառը ընտրվել է Bellmanի կողմից գրավել այն ժամանակ տարբեր առումով խնդիրներ, եւ քանի որ այն հնչում տպավորիչ Eddy, SR ինչ դինամիկ ծրագրավորում., Բնությո Կենսատեխնոլոգիա, 22 , 909-910 (2004): բառն ծրագրավորում անդրադարձել է օգտագործման եղանակով գտնել օպտիմալծրագիրը, այն իմաստով ռազմական ժամանակացույցով վերապատրաստման համար կամ նյութատեխնիկական. Սա օգտագործում է որպես նույնը, ինչ որ արտահայտություններ գծային ծրագրավորման եւ մաթեմատիկական ծրագրավորման, որը հոմանիշ է մաթեմատիկական օպտիմալացում.

Դիտարկում խմբագրել

Դինամիկ ծրագրավորումը եւ մաթեմատիկական օպտիմիզացում եղանակ է եւ համակարգչային ծրագրավորման մեթոդ է. Երկու համատեքստում խոսքը վերաբերում պարզեցնելով բարդ խնդիր կողմից խախտելու մեջ, այն պարզ ենթախնդիրն է recursive ձեւով: Թեեւ որոշ խնդիրներ որոշումներ չեն կարող կայացվել, բացի այդ ճանապարհը, որոշումները, որ span մի քանի միավոր ժամանակի համար հաճախ խախտել բացի ռեկուրսիվ; Bellman անվանել դա է « սկզբունքը Optimality»: Նմանապես, համակարգչային գիտության, մի խնդիր, որը կարող է կոտրվել են recursively է ունենալ օպտիմալ ենթակառուցվածք. Եթե ​​ենթախմբի խնդիրները կարող է լինել մարդ recursively ներսում ավելի մեծ խնդիրներ, այնպես, որ դինամիկ ծրագրավորման մեթոդները կիրառելի են, ապա կա միջեւ արժեքի մեծ խնդրի ու արժեքները ենթախմբի խնդիրների ներածություն ալգորիթմներ (2 - րդ խմբ.) MIT Մամլո & McGraw-Hill, ISBN 0-262-03293-7: , օպտիմալացման գրականության այդ հարաբերությունը կոչվում է Bellman հավասարումը.

Դինամիկ ծրագրավորման մաթեմատիկական օպտիմալացում խմբագրել

Առումով մաթեմատիկական օպտիմալացման, դինամիկ ծրագրավորում սովորաբար վերաբերում է պարզեցնել որոշում է խախտման այն վերածվում է հաջորդականություն որոշում քայլերի շուրջ ժամանակ. Դա արվում է սահմանելով այն հաջորդականություն արժեքային գործառույթների </ ենթակետի>, </ ենթակետի> </ ենթակետի>, ինչպես նաեւ փաստար y ներկայացնում վիճակը "համակարգի երբեմն. Սահմանումը Վ թիվ </ ենթակետի> (y) - ը ձեռք բերված արժեքը պետական​​ Y-ին, վերջին անգամ n. Արժեքները </ ենթակետի> էր ավելի վաղ ժամանակներից i =n -1, n-2, ..., 2, 1 կարելի է աշխատում հետընթաց, օգտագործելով recursive հարաբերությունը կոչվում է Bellman հավասարումը. For' i = 2, ..., n </ i ենթակետում> ցանկացած պետության y հաշվարկվում </ ենթակետի> Ըստ maximizing պարզ գործառույթը (սովորաբար գումարը), եւ շահում որոշման i-1 եւ </ ենթակետի> - ին: Նոր պետության, համակարգի եթե այս որոշումը կայացրել. Քանի Վ թ </ ենթախմբի Փոխանցել արդեն հաշվարկված համար անհրաժեշտ է, որ վերը նշված պետությունների համագործակցության զիջում Վ թ -1 </ ենթակետի > for այդ պետությունների Վերջապես, 1 </ ենթակետի> է նախնական վիճակին համակարգի արժեքը օպտիմալ լուծմանը: Օպտիմալ արժեքները որոշում փոփոխականների կարելի է վերականգնել, մեկ - մեկ, ի հետեւել ետ են հաշվարկներ են կատարւում

Դինամիկ ծրագրավորումը համակարգչային ծրագրավորման մեջ խմբագրել

Կան երկու առանցքային հատկանիշները, որ խնդիրը պետք է ունենան, որպեսզի դինամիկ ծրագրավորմամբ, որ կիրառելի է: օպտիմալ ենթակառուցվածք եւ overlapping subproblem s. Սակայն, երբ ենթախնդիրն խնդիրները շատ ավելի փոքր է, քան բուն խնդրին, ապա ռազմավարությունը կոչվում է « բաժանելուն եւ նվաճել,« ավելի շուտ, քան «դինամիկ ծրագրավորման թ. Սա է պատճառը, միաձուլել տեսակ, արագ տեսակ, եւ գտնելու բոլոր հանդիպումները մի հերթական դրսեւորում: չեն դասակարգվում որպես դինամիկ ծրագրավորման խնդիրներին:

Օպտիմալ ենթակառուցվածք նշանակում է, որ տվյալ օպտիմալացման խնդրի լուծումը կարելի է ձեռք բերել համադրությունը օպտիմալ լուծումների իր ենթաբազմության խնդիրներից: Հետեւաբար, առաջին քայլն է մշակել դինամիկ ծրագրավորում լուծման ստուգելը, թե արդյոք նման խնդրի ցուցադրումը օպտիմալ ենթակառուցcածք է ստեղծում. Նման օպտիմալ ենթակառուցվածքների սովորաբար նկարագրվում է ռեկուրսիամիջոով: Օրինակ, տրվում գրաֆիկը Գ = (V, E), ամենակարճ ուղին էջ - ը, մի vertex իա մի vertex ընդդեմ ցուցանմուշներին օպտիմալ ենթակառուցվածք: ձեռնարկի ցանկացած միջանկյալ vertex '' w այս ամենակարճ ճանապարհը էջ. Եթե ​​Դուք իսկապես ամենակարճ ուղին, ապա ճանապարհը </ ենթաբազմության> ից իա է եւ w էջ: </ ենթաբազմության>' ից w է' ընդդեմ իսկապես կարճ ուղիներ միջեւ համապատասխան vertices (ըստ պարզ արտահայտված եւ կպցնել փաստարկ նկարագրված CLRS). Հետեւաբար, կարելի է հեշտությամբ ձեւակերպել լուծումը գտնելու համար ամենակարճ ճանապարհները է recursive ձեւով, որը պետք է Bellman - Ford ալգորիթմը կամ Floyd-Warshall ալգորիթմը Թեմա.

Սա կարելի է հասնել կամ երկու եղանակով, Կաղապար:Հղում հարկավոր

  • Top-ի վար մոտեցումը: Սա ուղղակի ընկնում, դուրս recursive ձեւակերպման որեւէ խնդրի. Եթե ​​որեւէ խնդրի լուծումը կարելի է ձեւակերպել ռեկուրսիվորեն օգտագործելով իր ենթախմբի լուծում, եւ եթե դրա ենթախմբերը համընկնում են, ապա կարելի է հեշտությամբ memoize կամ պահում լուծումները, ինչպես նաեւ ենթախնդիրները մի սեղանի շուրջ Երբ մենք փորձում է լուծել նոր ենթախնդիր , մենք առաջին հերթին ստուգել աղյուսակը տեսնելու համար, եթե այն արդեն լուծված է: Եթե ​​լուծում չի արձանագրվել, մենք կարող ենք օգտագործել այն ուղղակի, այլապես ենթախնդիրը լուծում եւ ավելացնել իր լուծում սեղանին.


ծրագրավորման լեզուն - ից  Ոմանք, կարող է ավտոմատ կերպով,  memoize  որեւէ գործառույթ արդյունք է զանգի հետ որոշակի շարք փաստարկներ, որպեսզի արագացնեն զանգահարել առ անուն գնահատական ​​(այս մեխանիզմը կոչվում ինչպես  զանգահարել-ի կարիք ունեն:). Որոշ լեզուներով հնարավորություն portably (օրինակ,  Scheme, Common lisp մասին կամ Perl), ոմանք պետք է հատուկ ընդարձակման (օրինակ, C + +, մի քանի լեզուների են ավտոմատ memoization դեռ չի կառուցվել է, օրինակ, tabled տրամաբանական ծրագրավորման լեզու եւ  J, որն աջակցում memoization հետ  M. փոխըմբռնման | url = http://www.jsoftware.com/help/dictionary/dmcapdot.htm%7Cwork=J բառապաշարի | հրատարակիչ = J Software | accessdate = 28 Հոկտեմբեր 2011}}: Ամեն դեպքում, այդ հնարավոր է միայն մի  referentially թափանցիկ գործառույթից

Օրինակ: մաթեմատիկական օպտիմալացում խմբագրել

Օպտիմալ սպառումը եւ խնայողություն խմբագրել

A մաթեմատիկական օպտիմալացման խնդիր է, որ հաճախ օգտագործվում է ուսուցման դինամիկ ծրագրավորման, ինչպես նաեւ տնտեսագետների (քանի որ այն կարող է լուծվել ձեռքով Stokey et al., 1989, տղա. 1concerns սպառող, ով ապրում է ժամանակից t = 0,1,2, Մանրամասն ldots, եւ պետք է որոշի, թե որքանով են սպառում եւ որքան խնայել յուրաքանչյուր շրջանում.

Թող լինի սպառումը ժամկետով եւ ստանձնի սպառման զիջում օգտակար, քանի դեռ սպառողական կյանք: Ենթադրել, սպառողը պետք է անհամբեր, որ նա դիսկոնտավորումից Սկիզբ զեղչերը ապագան օգտակար է մի գործոնի, յուրաքանչյուր շրջանում, vhere թող լինի մայրաքաղաքն in ժամանակահատվածում ստանձնում նախնական կապիտալը, որ տվյալ գումարը, եւ ենթադրել, որ այս ընկած ժամանակահատվածում մայրաքաղաքում եւ սպառման որոշելու հաջորդ ժամանակահատվածը կապիտալում որպես>, որտեղ մշտապես դրական է. Ենթադրում կապիտալը չի կարող լինել բացասական: Այնուհետեւ սպառողական որոշումը խնդիրը կարելի է գրել հետեւյալ կերպ. 

: Max \ sum_ {t = 0 ^} T բ ^ t \ LN (c_t ենթակա k_ հաղորդագրությունները {t = AK +1} ^ a_t - c_t \ geq 0 բոլոր t = 0,1,2, \ ldots, T

Գրավոր այսպես, խնդիրը բարդ է նայում, որովհետեւ այն ներառում է լուծել բոլոր ընտրության փոփոխականների c_0 եւ c_1 եւ c_2, \ ldots եւ c_T եւ k_1, k_2, k_3, \ ldots եւ k_ {T +1} </ math> միաժամանակ. (Նկատի ունեցեք, որ k_0 չէ ընտրությունն է փոփոխական `սպառողի կողմից նախնական կապիտալը տեղափոխվել է տրվում):


Դինամիկ ծրագրավորում մոտեցում լուծելու այս խնդիրը ներառում կոտրել այն բացի մեջ հաջորդականությամբ փոքր որոշումների Դա անելու համար, մենք սահմանել հաջորդականություն արժեքային գործառույթների V_t (K) </ մաթեմատիկական>, հանուն t = 0,1,2, \ ldots, ք, ք +1 որոնք ներկայացնում արժեքը ունեցող ցանկացած քանակի կապիտալ մասին k հաղորդագրությունները յուրաքանչյուր անգամ t Նշենք, որ V_ {T} +1 (ժա) = 0 որ կա (ըստ ենթադրության), ոչ մի օգտակար է ունենալ կապիտալի մահից հետո.

Արժեքը ցանկացած քանակի կապիտալ է ցանկացած նախորդ անգամ կարող է հաշվարկվել է [[ետ զորակոչի] օգտագործելով Bellman հավասարումը. Այս խնդրի յուրաքանչյուր t = 0,1,2, \ ldots, T ապա Bellman հավասարումը է 

V_t (k_t) \, = \, \ Max \ ձախ (\ LN (c_t) + բ V_ {t +1} (k_ {t +1}) \ աջ) \ տեքստը {ենթակա} {k_ t = AK +1} ^ a_t - c_t \ geq 0

Այս խնդիրը շատ ավելի պարզ, քան որեւէ մեկը, որ մենք գրել ենք, որովհետեւ այն ներառում է միայն երկու որոշում է, փոփոխականների c_t k_ {t +1} Intuitively փոխարեն ընտրելով իր ողջ կյանքի պլան է ծննդյան սպառողը կարող է իրերը մի քայլ միաժամանակ. Միեւնույն ժամանակ t>, նրա ներկայիս մայրաքաղաք k_t տրվում, եւ նա ընդամենը պետք է ընտրել ընթացիկ սպառման c_t </ մաթեմատիկական> եւ փրկելու k_ {, T + 1}

Իրականում լուծել այդ խնդիրը, մենք աշխատում ենք հետընթաց. For պարզությամբ, ներկայիս մակարդակը մայրաքաղաքում կետը կորոշվի նաեւ Ղ </ մաթեմատիկական>. V_ {T} +1 (k) արդեն հայտնի է, ուստի օգտագործելով Bellman հավասարումը մեկ անգամ կարող ենք հաշվել V_T (K) </ մաթեմատիկական> եւ այլն, մինչեւ ենք ստանում, որ Սկիզբ math մասին > V_0 (k) որը հանդիսանում է' արժեքը նախնական որոշման խնդիր է ամբողջ կյանքի ընթացքում: Այսինքն, երբ մենք գիտենք V_ {T-ժ +1} (K) մենք կարող ենք հաշվել V_ {} Tj (K)որը առավելագույնը\ LN (c_ {} Tj) + բ V_ {T-ժ +1} (AK ^ a-c_ {} Tj) որտեղ c_ {Tj} - ի ընտրությունը փոփոխական է եւ AK ^ a-c_ {Tj} \ ge 0

Աշխատանքային հետընթաց, կարելի է ցույց տվեց, որ արժեքը ֆունկցիան է ժամանակ t = Tj - ը 

V_ {} Tj (ժա) \, = \ Ա \ sum_ {i = 0 ^} ja ^ ^ i ib \ LN k + v_ {Tj}

որտեղ յուրաքանչյուր v_ {Tj} է անընդհատ, եւ օպտիմալ չափը պետք է ժամանակ սպառում t = Tjհաղորդագրությունները է

< C_ {} Tj (ժա) \, = \, \ frac {1} {\ sum_ {i = 0 ^} ja ^ ^ i ib} AK ^ ա

որը կարող է պարզեցված

C_ {T} (ժա) \, = \, AK ^ ա իսկ c_ {T-1} (ժա) \, = \, \ frac {AK ^ ա} { 1 + AB}, իսկ c_ {T-2} (ժա) \, = \, \ frac {AK ^ ա} {1 + AB + ա ^ ^ 2b 2} եւ այլն:

Մենք տեսնում ենք, որ այն օպտիմալ է սպառում ավելի մեծ կոտորակ ընթացիկ հարստության ինչպես է ավելի վերջապես սպառող ողջ մնացած հարստության շրջանում T վերջին ժամկետը կյանքում.

Օրինակներ: Համակարգչային ալգորիթմեր խմբագրել

Dijkstra ի ալգորիթմը է ամենակարճ ճանապարհով խնդիր խմբագրել 

դինամիկ ծրագրավորման տեսակետից Dijkstra ի ալգորիթմը ի ամենակարճ ճանապարհը խնդիրը սա հերթական մերձեցումը սխեման, որը լուծում է դինամիկ ծրագրավորում ֆունկցիոնալ հավասարումը է ամենակարճ ճանապարհով խնդիր հայտարարել է '' գնացող եղանակի  (PDF) pl/ksiazki/cc/cc35/cc3536.pdf http://matwbn.icm.edu. pl/ksiazki/cc/cc35/cc3536.pdf {{citation}}: Check |url= value (օգնություն); Cite has empty unknown parameter: |ետգրություն= (օգնություն); Missing or empty |title= (օգնություն); Text "Թողարկում # 3" ignored (օգնություն); Unknown parameter |Title= ignored (|title= suggested) (օգնություն) Online Ծանոթություններ թղթի վրա ինտերակտիվ հաշվողական մոդուլների. անուն = denardo_03 , էջ 270, ISBN [[Special:BookSources/978-0486428109 անուն = sniedovich_10 , ISBN 9780824740993 {{citation}}: Missing or empty |title= (օգնություն); Unknown parameter |Title= ignored (|title= suggested) (օգնություն)In fact, Dijkstra's explanation of the logic behind the algorithm harvnb|978-0486428109 անուն = sniedovich_10 '"`UNIQ--templatestyles-00000002-QINU`"'<cite class="citation cs2">, [[ISBN (identifier)|ISBN]]&nbsp;[[Special:BookSources/9780824740993|<bdi>9780824740993</bdi>]]</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.isbn=9780824740993&rfr_id=info%3Asid%2Fhy.wikipedia.org%3A%D5%84%D5%A1%D5%BD%D5%B6%D5%A1%D5%AF%D5%AB%D6%81%3AHaso1111" class="Z3988"></span> <span class="cs1-visible-error citation-comment"><code class="cs1-code">{{[[Template:citation|citation]]}}</code>: </span><span class="cs1-visible-error citation-comment">Missing or empty <code class="cs1-code">&#124;title=</code> ([[Help:CS1 errors#citation_missing_title|օգնություն]])</span>; <span class="cs1-visible-error citation-comment">Unknown parameter <code class="cs1-code">&#124;Title=</code> ignored (<code class="cs1-code">&#124;title=</code> suggested) ([[Help:CS1 errors#parameter_ignored_suggest|օգնություն]])</span>In fact, Dijkstra's explanation of the logic behind the algorithm harvnb]] {{citation}}: Check |isbn= value: invalid character (օգնություն); Missing or empty |title= (օգնություն); Text "1959" ignored (օգնություն); Text "Dijkstra" ignored (օգնություն); Unknown parameter |Title= ignored (|title= suggested) (օգնություն); templatestyles stripmarker in |ISBN= at position 38 (օգնություն) namely
  
 'Խնդիր 2.' Գտնել ճանապարհով նվազագույն ընդհանուր երկարությամբ երկու տրված հանգույցների էջ եւ Հ.

Մենք օգտագործում ենք այն փաստը, որ եթե R մի ուռուցք է նվազագույն ճանապարհին է: P Q դեպի գիտելիք, որ վերջինիս ենթադրում է գիտելիքների այն նվազագույն ճանապարհից դուրս P Ռ.
  
որը փոխակերպում է  Bellman ի նշանավոր սկզբունքը Optimality համատեքստում է ամենակարճ ճանապարհը խնդրի.


Fibonacci հաջորդականությունը խմբագրել

Ահա մի միամիտ իրականացման գործառույթը գտնելու նպատակով' թիվ րդ անդամ է Fibonacci հաջորդականությունը, հիմնված է ուղղակիորեն է մաթեմատիկական սահմանման: 

     'գործառույթը' ստախոսություն (n)
         'Եթե n = 0 'վերադարձը 0
         'Եթե n = 1 'վերադարձը ա
         'վերադարձը' ստախոսություն (n-1) + ստախոսություն (n-2)

Նկատում է, որ եթե մենք կոչ ենք անում, ասենք, ստախոսություն (5), մենք արտադրում է մի կանչի ծառ, որը կոչ է անում գործառույթը նույն արժեքային տարբեր ժամանակներում: 

#  Ստախոսություն (5)
#  Ստախոսություն (4) + ստախոսություն (3
#  (Ստախոսություն (3) + ստախոսություն (2)) + (ստախոսություն (2) + ստախոսություն (1))
#  ((Ստախոսություն (2) + ստախոսություն (1)) + (ստախոսություն (1) + ստախոսություն (0))) + ((ստախոսություն (1) + ստախոսություն (0)) + ստախոսություն (1)
#  (((Ստախոսություն (1) + ստախոսություն (0)) + ստախոսություն (1)) + (ստախոսություն (1) + ստախոսություն (0))) + ((ստախոսություն (1) + ստախոսություն (0)) + ստախոսություն (1))

Մասնավորապես, ստախոսություն (2 անգամ հաշվարկված է երեք անգամ զրոյից, իսկ ավելի մեծ օրինակներ շատ ավելի արժեքները սուտ է, կամ' subproblems են վերահաշվարկվում `հանգեցնելով մի exponential ժամանակային ալգորիթմի.

Հիմա, կարծում ենք, մի պարզ  քարտեզ օբյեկտ, մ, որը քարտեզները յուրաքանչյուր արժեքը, սուտ է, որ արդեն հաշվարկված է իր արդյունքը, եւ մենք մեր փոփոխությունները գործառույթ օգտագործել այն եւ թարմացնել այն. Իսկ արդյունքում ֆունկցիան պահանջում է միայն,  O ( n) ժամանակը փոխարեն exponential համար


'Գլիցերոլ չ = 'քարտեզ (0 0 1 → → 1) 

     'գործառույթը' ստախոսություն (n)
         'Եթե 'քարտեզ' չ 'չի պարունակում կարեւոր n
            ժգ [n] = ստախոսություն (n-1) + ստախոսություն (n-2)
         'վերադարձը' մ [n]

Այս տեխնիկան փրկելու արժեքներում, որոնք արդեն իսկ հաշվարկված կոչվում է memoization, <! - Այո, memoization, ոչ memorization. Ոչ typo. -> Սա վերին ցած մոտեցում է, քանի որ մենք առաջին անգամ խախտել է խնդիրը subproblems եւ հաշվարկել եւ պահպանել արժեքները: 

Է 'ներքեւից `մինչեւ մոտենում ենք հաշվարկել փոքր արժեքները, հետո կառուցել ավելի մեծ արժեքներ են նրանց համար: Այս մեթոդը նաեւ օգտագործում հաղորդագրությունները O (n'), ժամանակն է, քանի որ այն պարունակում է մի հանգույց, որը կրկնում է N-1 անգամ, սակայն դա միայն պետք է անընդհատ (O (1)) տարածք, ի տարբերություն վերեւ - ներքեւ մոտեցմանը, որը պահանջում հաղորդագրությունները O ( n) տարածքը պետք է պահել քարտեզը.

'գործառույթը' ստախոսություն (n) 

         'Գլիցերոլ' previousFib: = 0, currentFib: = 1
         'Եթե' n = 0
             'վերադարձը' 0
         'Else կրկնել 'n - 1 անգամ '/ / հանգույց, որը skipped Եթե n = 1
             'Գլիցերոլ' newFib: = previousFib + currentFib
            previousFib: = currentFib
            currentFib: = newFib
         'վերադարձը' currentFib

Երկու Այս օրինակներում, մենք հաշվարկել է միայն մեկ անգամ, ապա այն օգտագործել է հաշվարկել, թե փոխարենը `ՀԱՇՎՈՂԱԿԱՆ դա ամեն անգամ էլ նրանց գնահատվում. (Նկատի ունեցեք, հաշվարկը է Fibonacci հաջորդականությամբ, որն օգտագործվում է ցույց դինամիկ ծրագրավորման Մի O (' 1) բանաձեւը, հայտնի Binet ի բանաձեւի, գոյություն ունի, որից մի կամայական ժամկետը կարելի է հաշվարկել, որը կազմում է ավելի արդյունավետ, քան որեւէ դինամիկ ծրագրավորման տեխնիկայով)

հավասարակշռության մի տեսակ 0-1 մատրիցով խմբագրել

Դիտարկենք խնդիրը նշանակվում արժեքներին, կամ զրո կամ, ինչպես դիրքերից մի անգամ, որպեսզի յուրաքանչյուր տող եւ ամեն սյուն պարունակում է ճիշտ zeros ու նորերը. Մենք խնդրում ենք չորս հնարավոր լուծումներ են

 


Գոյություն ունեն առնվազն երեք հնարավոր մոտեցումները: ամենակոպիտ բռնությունների կիրառումը, backtracking, եւ դինամիկ ծրագրավորում. 

Ամենակոպիտ բռնությունների կիրառումը բաղկացած ստուգում բոլոր հանձնարարականները zeros ու նորերը, եւ հաշվել նրանց, ովքեր ունեն հավասարակշռված տողերը, ու սյուները (Չհաջողվեց վերլուծել (շարահյուսության սխալ): {\displaystyle  նաեւ պետք / 2: </ Մաթեմատիկա Փոխանցել zeros եւ <math> նաեւ պետք / 2: </ Մաթեմատիկա Փոխանցել նորերը): Քանի որ կաn հնարավոր հանձնարարականները, այդ ռազմավարությունը չի գործնական, բացի գուցե մինչեւ  n = 6 .   Backtracking այս խնդրի բաղկացած է ընտրելու մի հրաման է մատրիցով տարրերի եւ recursively տեղադրելով նորերը կամ zeros, իսկ ստուգում է, որ յուրաքանչյուր տողում ու դաշտով համարը տարրեր, որոնք չեն հանձնարարված գումարած թիվը պատահողները կամ zeros երկուսն էլ առնվազն'' n / 2''. Թեեւ ավելի բարդ է, քան ամենակոպիտ բռնությունների կիրառումը: Այս մոտեցումը կայցելի յուրաքանչյուր լուծում մի անգամ, դարձնելով այն անպետք է'' n'' մեծ է, քան վեց, քանի որ բազմաթիվ լուծումների արդեն 116963796250 - ի'' n = 8'', քանի որ մենք պետք է տեսնել,.  Դինամիկ ծրագրավորում  թույլ է տալիս հաշվարկել շարք որոշումներ, առանց հայտնվելու դրանք. Պատկերացրեք ետդարձի արժեք առաջին գծում - ինչ տեղեկատվություն ենք մենք պետք մասին այլ գծերի, որպեսզի կարողանան ճիշտ հաշվարկել լուծումները ստացած յուրաքանչյուր արժեքի առաջին շարքում. Մենք հավատում ենք, խորհուրդ, որտեղ   տողերը պարունակում փակցնելուց 2 </ մաթեմատիկական հաղորդագրությունները <math> zeros եւ արեք / 2: </ մաթեմատիկական Թեմա դրանք. Գործառույթը զ'', որը'' [[հիշել]] են քարտեզները vectors'''' N մի զույգ integers մեջ թվի վավեր քարտերի (լուծույթներ): Կա մեկ զույգ յուրաքանչյուր սյունակում եւ նրա երկու բաղադրիչների, համապատասխանաբար, ցույց են տալիս բազմաթիվ zeros ու նորերը, որոնք պետք է տեղադրվեն այդ սյունակում: Մենք ձգտում արժեքը <math> F ((N / 2, n / 2), (n / 2 n / 2), \ ldots (n / 2 n / 2)) </ math> (<math> n < միասին Մաթեմատիկա Փոխանցել փաստարկները կամ վեկտորը <math> համար նաեւ պետք է </ math Փոխանցել տարրերի) համար. Գործընթացը ստեղծելու subtask ներառում iterating միջոցով յուրաքանչյուր <math> \ tbinom հաղորդագրությունները {թիվ} {N / 2} </ math> հնարավոր առաջադրանքները համար վերեւի շարքում վարչության, եւ անցնում է յուրաքանչյուր սյունակի, subtracting հետեւյալ համապատասխան տարր է զույգի Այս սյունակի կախված Ըստ նշանակելու վերեւում գծի պարունակվող զրո կամ մեկ այս դիրքորոշումը. Եթե ​​արդյունքը բացասական է, ապա հանձնարարությունը, անվավեր է եւ չի նպաստում մնացած լուծման փաթեթի (ռեկուրսիա դադարում): Հակառակ դեպքում, մենք ունենք մի աշխատանք է վերեւում գտնվող {{math մասին խորհրդի եւ recursively հաշվարկել թիվը լուծումների  {{math մասին խորհուրդ, ավելացնելով, որ թվով լուծումներ յուրաքանչյուր հնարավոր հանձնարարությամբ վերին շարքով եւ վերադարձման այն գումարի, որը ներկայումս memoized. Հիմնական տարբերակն է, չնչին subtasks, որ տեղի է ունենում, որ {{math մասին | Խորհրդի. Թիվն լուծումների այս խորհրդին կամ զրոյական, կամ, կախված նրանից, թե որ վեկտորը permutation է ((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4   0      1      0      1              0      0      1      1  ((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3   1      0      1      0              0      0      1      1  ((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2   0      1      0      1              1      1      0      0  ((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1   1      0      1      0              1      1      0      0  ((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0)) </PRE>  The number of solutions {{OEIS|id=A058527}} is :<math> 1,\, 2,\,  90,\, 297200,\, 116963796250,\, 6736218287430460752, \ldots }

Links to the MAPLE implementation of the dynamic programming approach may be found among the external links.

շախմատի տախտակ խմբագրել

Դիտարկենք a շախմատի տախտակ հետ, n' n × քառակուսիները եւ ծախսերի գործում գ ( i' ժ), որը վերադարձնում է ծախսերը հետ կապված հրապարակ i, ժ (' i լինելով շարքով' ժ լինելու սյունակ). Օրինակ, (մի 5 × 5 շախմատի տախտակ),

Դուք = "wikitable" ոճը = "մեջբերումը - Դաշինքը կենտրոն"
5 6 7 4 7 8
4 7 6 1 1 4
3 3 5 7 8 2
2 – 6 7 0 –
1 – – *5* – –
. ոճը = "լայնություն 15px;" | 1. ոճը = "լայնություն 15px;" | 2. ոճը = "լայնություն 15px;" | 3. ոճը = "լայնություն 15px;" | 4. ոճը = "լայնություն 15px;" | 5 
Այսպիսով' գ (1, 3) = 5

Եկեք ասում եք ունեցել շախմատի տախտակ, որը կարող է սկսել որեւէ հրապարակում է առաջին աստիճանի (այսինքն, տող), եւ դուք ուզում իմանալ ամենակարճ ուղին (գումարը ծախսերի վերաբերյալ այցելել հրապարակներում են նվազագույնի) ստանալու վերջին աստիճանի , ենթադրելով, որ տախտակ էին տեղափոխվել միայն diagonally մնացել առաջ, diagonally իրավունքը պետք է, կամ ուղիղ առաջ. Այսինքն, մի տախտակ է, (1,3) կարող է տեղափոխել (2.2), (2,3), կամ (2,4).

4
3
2 x x x
1 o
1 2 3 4 5

This problem exhibits optimal substructure. That is, the solution to the entire problem relies on solutions to subproblems. Let us define a function q(i, j) as

q(i, j) = the minimum cost to reach square (i, j)

If we can find the values of this function for all the squares at rank n, we pick the minimum and follow that path backwards to get the shortest path.

Note that q(i, j) is equal to the minimum cost to get to any of the three squares below it (since those are the only squares that can reach it) plus c(i, j). For instance:

5
4 A
3 B C D
2
1
1 2 3 4 5
 

Now, let us define q(i, j) in somewhat more general terms:

 


Առաջին գիծ, այս հավասարման կա, որպեսզի պարզ recursive գույքը (երբ գործ հետ եզրեր, այնպես որ մենք պետք է միայն մեկ ռեկուրսիա). Երկրորդ գիծը ասում է, թե ինչ է կատարվում վերջին աստիճանի, ապահովել է բազային գործը. Երրորդ գիծը, ապա ռեկուրսիա, այն կարեւոր մաս. Այն նման է A, B, C, D օրինակով. Այս սահմանման, մենք կարող ենք շիտակ recursive կոդը համար ): Հետեւյալ pseudocode, n այն չափը խորհրդի գ (i, j)որ ծախսերի ֆունկցիան, եւ րոպե () վերադառնում նվազագույն մի շարք արժեքներ: 

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)


Հարկ է նշել, որ այս գործառույթը միայն computes ճանապարհով-ի արժեքը, ոչ թե իրական ուղին: Մենք հասնելու ճանապարհին շուտով: Այս, ինչպես Fibonacci - ի համարները, օրինակ, այն horribly դանդաղ, քանի որ ծախսում լեռներում ժամանակի recomputing նույն ամենակարճ ճանապարհները կրկին ու կրկին. Սակայն մենք կարող ենք հաշվարկել այն ավելի արագ է ներքեւից-up նորաձեւության եթե մենք պահում ճանապարհը-ի ծախսերի մի երկու ծավալային գրանցվեք q [i, j] </ code>, այլ ոչ թե, օգտագործելով մի գործառույթ. Այս խուսափում recomputation առաջ computing ծախսերը մի ճանապարհ ենք ստուգել զանգված q [i, j] </ code> տեսնել, եթե ճանապարհը արժեքն արդեն այնտեղ. 

Մենք նաեւ պետք է իմանալ, թե ինչ իրական ամենակարճ ուղին է. Դա անել, մենք օգտագործում ենք ուրիշ զանգված մի նախորդը . 



 function computeShortestPathArrays()
     for x from 1 to n
         q[1, x] := c(1, x)
     for y from 1 to n
         q[y, 0]     := infinity
         q[y, n + 1] := infinity
     for y from 2 to n
         for x from 1 to n
             m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
             q[y, x] := m + c(y, x)
             if m = q[y-1, x-1]
                 p[y, x] := -1
             else if m = q[y-1, x]
                 p[y, x] :=  0
             else
                 p[y, x] :=  1

Now the rest is a simple matter of finding the minimum and printing it. 

 function computeShortestPath()
     computeShortestPathArrays()
     minIndex := 1
     min := q[n, 1]
     for i from 2 to n
         if q[n, i] < min
             minIndex := i
             min := q[n, i]
     printPath(n, minIndex)

 function printPath(y, x)
     print(x)
     print("<-")
     if y = 2
         print(x + p[y, x])
     else
         printPath(y-1, x + p[y, x])

հաջորդականության հավասարեցում խմբագրել

Ին Ծագումնաբանություն, հաջորդականությունը հավասարեցում կարեւոր ծրագիր է, ուր դինամիկ ծրագրավորում շատ էական է: Սովորաբար, խնդիրը բաղկացած փոխակերպման մեկ հաջորդականությունը այլ, օգտագործելով խմբագրել գործողություններին, որոնք փոխարինում, մտցրեք կամ հեռացնել մի տարր. Յուրաքանչյուր գործողություն ունի հարակից ծախսերը, իսկ նպատակն է գտնել այն հաջորդականությունը խմբագրումները հետ ամենացածր ընդհանուր արժեքի. 

Խնդիրը կարելի է ասել, բնականաբար, որպես ռեկուրսիա է, հաջորդականությունը A է optimally խմբագրվել մեջ հերթական B-ի կամ.

# Տեղադրելու առաջին բնույթը B, եւ կատարում է օպտիմալ դասավորվածության A եւ պոչը եւ Բ
# Վերացման առաջին բնույթը A եւ իրականացնելու օպտիմալ դասավորվածության պոչը են A եւ B
# Փոխարինելու առաջին բնույթը A առաջին բնույթի Բ եւ իրականացնելու օպտիմալ alignments ՀՀ tails մի եւ Բ.

Մասնակի alignments կարող tabulated է մատրիցով, որտեղ բջջային (i, j) պարունակող ծախսերը օպտիմալ դասավորվածության a [1 .. i] Ինչպես B [1 .. ժ. Արժեքն է խցում (i, j) կարող է հաշվարկվել, ավելացնելով ծախսերը համապատասխան գործողությունների արժեքի հարեւան բջիջներում, եւ ընտրելով օպտիմալ.

Տարբեր տարբերակներ կան, տես Սմիթ թիավար ալգորիթմը եւ Needleman-Wunsch ալգորիթմը.


Թաուեր - ից Hanoi Փազլ խմբագրել

The 'Tower - ից Hanoi կամ 'Towers է Hanoi հանդիսանում է մաթեմատիկական խաղ կամ Փազլ. Այն բաղկացած է երեք ձողերով եւ մի շարք սկավառակների տարբեր չափսերի, որոնք կարող գաղտնաբառը վրա ցանկացած գավազանով. The Փազլ սկսվում հետ սկավառակների մի կոկիկ դեղ Աճման կարգով եւ չափերով մի գավազանով, որ ամենափոքր վերեւում `այդպիսով կատարելով կոնաձլ ձեւավորել.

Նպատակն է Puzzle է շարժվել ամբողջ կույտ այլ գավազանով, հնազանդվելով հետեւյալ կանոնները.

  • Միայն մեկ սկավառակի կարելի է տեղափոխել ցանկացած ժամանակ:
  • Յուրաքանչյուր քայլը, որը կազմված է վերին սկավառակի ից մեկը ձողերով ու լոգարիթմական այն տալու, այլ գավազանով, գագաթին մյուս սկավառակների, որը կարող է արդեն այսօր այդ գավազանով.
  • Ոչ սկավառակի կարող տեղադրել գագաթին մի փոքր սկավառակ.

Դինամիկ ծրագրավորում լուծումը բաղկացած է լուծելու ֆունկցիոնալ հավասարումը

S (n - ը, t) = S (n-1, H, ոչ (h, ք)), S (1 - ը, ք), S (n-1, ոչ (h, ք), t)

որտեղ n նշանակում թիվը սկավառակների է տեղափոխվել, ը մատնանշում է տուն գավազանով, t նշանակում թիրախ գավազանով, ոչ (h, t) նշանակում է երրորդ գավազանով (Ոչ ը, ոչ էլ t), «,» նշանակում concatenation, եւ

S (n - ը, t) = լուծում խնդիրը կազմված թիվ սկավառակների որոնք կարող են տեղափոխվել գավազանով ժ - ից գավազանով t.

Նշենք, որ n = 1 խնդիրն այն է, չնչին, մասնավորապես S (1 - ը, t) = "տեղափոխել սկավառակի էին գավազանով ժ - ից գավազանով T", (կա միայն մեկ սկավառակի ձախից).

Թիվն քայլերի համար սույն լուծում է 2 1. Եթե ​​խնդիրն է 'մեծացնելու' թվաքանակը (առանց քայլերի Հեծանվավազք), ապա այդ դինամիկ ծրագրավորման ֆունկցիոնալ հավասարումը փոքր - ինչ ավելի բարդ են, իսկ 3 ընթրել - 1 քայլերը պարտադիր են / http://archive.ite.journal.informs.org/Vol3No1/Sniedovich / {{citation}}: Check |url= value (օգնություն); Cite has empty unknown parameter: |ետգրություն= (օգնություն); Missing or empty |title= (օգնություն); Unknown parameter |Գտնել այս հեղինակի= ignored (օգնություն); Unknown parameter |ամսագիրը= ignored (օգնություն); Unknown parameter |անվանումը= ignored (օգնություն); Unknown parameter |էջերը= ignored (օգնություն); Unknown parameter |ծավալը= ignored (օգնություն); Unknown parameter |տարին= ignored (օգնություն)

Ձու հրաժարվելու Փազլ խմբագրել

Ստորեւ նկարագրությունը խնդրանքով այդ հայտնի է [[Փազլ] ներգրավելու n = 2 ձու եւ մի շենքում H = 36 Հարկերի քանակը: Konhauser JDE, Velleman, Դ եւ վագոն, Ս. (1996): Որ ճանապարհն էր, որ Bicycle Գնալ? Dolciani մաթեմատիկական Ցուցադրանք - Ոչ 18. The մաթեմատիկական ընկերակցությունը Ամերիկա

Ենթադրենք, որ մենք ցանկանում ենք իմանալ, որոնց պատմությունները մի 36 հարկանի շենքում ապահով են հրաժարվել ձու է, եւ որը կհանգեցնի ձու խախտել է վայրէջքի: Մենք մի քանի ենթադրությունը:
  • Մի ձու, որ survives մի անկումը կարող է օգտագործվել է.
  • A կոտրված ձու պետք է անտեսվեցին.
  • Գործողությունը, որի անկումից նույնն է բոլոր ձու.
  • Եթե ձվի ընդմիջումների ժամանակ, երբ նվազել է, ապա այն պետք է կոտրել, եթե նվազել է ավելի բարձր պատուհանում.
  • Եթե ձու survives է անկում, ապա այն գոյատեւում է մի կարճ անկում.
  • Չի բացառվում, որ առաջին հարկի պատուհանները ընդմիջում ձու, ոչ էլ է դա բացառվում է, որ 36th - Հատակի պատուհանները չեն առաջացնում է ձու կոտրելու.

Եթե ​​միայն մեկ ձու կա, եւ մենք ցանկանում ենք վստահ լինել, քան ձեռք ճիշտ արդյունքի, այդ փորձը կարող է իրականացվել միայն մեկ ճանապարհով. Թողնել ձու է առաջին հարկի պատուհանից, եթե survives, թողնել այն երկրորդ հարկի պատուհանից: Շարունակել դեպի վեր, մինչեւ այն խախտում է: Իսկ վատագույն դեպքում, այս մեթոդը կարող է պահանջել, 36 կղկղանք. Ենթադրենք 2 ձու են հնարավոր. Որն է առնվազն թիվն ձվի հետ աղբ, որը երաշխավորված է աշխատել բոլոր դեպքերում.

To բխում դինամիկ ծրագրավորման ֆունկցիոնալ հավասարումը այս Puzzle, թող 'երկիր է' - ի դինամիկ ծրագրավորման մոդել է լինել զույգ մասին = (n, k), որտեղ

' N = շարք ստուգողական ձու առկա,' n = 0, 1, 2, 3, ...,' N-1.
K = քանակ (հետեւողական) հատակը դեռ պետք է քննություն,' k = 0, 1, 2, ...,' H-1.

Օրինակ,' s = (2,6), ցույց է տալիս, որ երկու ստուգողական ձու հասանելի են, եւ 6 (հետեւողական) հարկերը, որոնք դեռ պետք է փորձարկվել: Նախնական վիճակը գործընթացի' s = ( N' H), որտեղ' N նշանակում համարը փորձարկման ձու առկա է սկսելու, որ փորձի: Գործընթացը դադարում է, երբ կան այլեւս փորձարկման ձու (' n = 0), կամ երբ' k = 0, որն տեղի է ունենում առաջին անգամ. Եթե ​​դադարեցումը տեղի է ունենում պետական' s = (0, k'), իսկ k> 0, ապա test ձախողվել է:

Հիմա, թող

W ( n, k) = նվազագույն շարք դատավարությունների պահանջվում բացահայտել արժեքը կրիտիկական հարկի տակ, վատագույն դեպքում, տվյալ սցենարի, որ գործընթացը գտնվում է պետության s ' '= ( n' ժա).

Ապա դա կարող է ցույց տվեց, որ Sniedovich, Մարիամ (2003): [Http://archive.ite.journal.informs.org/Vol4No1/Sniedovich/index.php ուրախության ձվի-ի հրաժարվելու դեպքում Braunschweig եւ Հոնկոնգ. Տեղեկացնում գործարքներ է կրթության,

W ( n' ժա) = 1 + min {Max ( W ( n - 1, x - 1) , W ( n, k - x)): x է, {1, 2, ..., k}} ,' n = 2, ...,' N;' k = 2, 3, 4, ...,' H

ինչպես W ( n, 1) = 1 բոլորի համար' n> 0, իսկ' W (1, k) = մասին k - 'բոլոր' Ղ. Դա շատ հեշտ է լուծել այս հավասարումը iteratively կողմից համակարգված ավելացնող արժեքները' եւ թիվ k.

An ինտերակտիվ օն - լայն հաստատության հասանելի փորձերի հետ, այս մոդելի, ինչպես նաեւ այլ տարբերակների այս Puzzle (օրինակ, երբ խնդիրն է նվազագույնի հասցնել '' արժեքը ակնկալվող թվի փորձերի

<! - === Մատրիցան շղթա բազմապատկում ===

Դեռ գրված

Ցուցադրել, թե ինչպես է տեղադրում առնված ազդում համարը scalar multiplications պահանջվում բազմապատկած մի փունջ matrices.

Ցույց տալ, թե ինչպես է գրել դինամիկ ծրագիր հաշվարկել օպտիմալ տեղաբաշխման փակագծեր.

Սա այնպիսի մի քանի օրինակ, որ այն կարող է լինել ավելի լավ է, որ իր հոդվածում: ->

Ալգորիթմները, որոնք օգտագործում են դինամիկ ծրագրավորման խմբագրել

Ձեր հերթական լուծումներ վանդակավոր մոդելները: - ի սպիտակուցային է ԴՆԹ պարտադիր

Ձեր Շատ ալգորիթմական խնդիրները գրաֆիկներն, կարող է լուծվել արդյունավետ է գրաֆիկներն bounded treewidth կամ bounded կլիկ, լայնությունը օգտագործելով դինամիկ ծրագրավորման վրա, ծառի տարրալուծման է գրաֆիկի .

Ձեր Pseudopolynomial անգամ ալգորիթմները այն նյութեր հանրագումարի եւ պայուսակ եւ միջնորմ խնդիրը խնդիրներով

  • The դինամիկ time warping ալգորիթմը համար Համակարգչային գլոբալ միջեւ հեռավորությունը երկու ժամանակային շարքերի
  • The Selinger (aka System R) ալգորիթմ է Հարաբերական տվյալների բազայի հարցման օպտիմալացում
  • De շինական ալգորիթմ - ի գնահատման B-spline կորեր
  • Duckworth-Lewis եղանակը լուծելու խնդիրը, երբ պարտիաները ծղրիդ են ընդհատվում
  • The Value բազմակրկնություն մեթոդ լուծելու Մարկովը որոշման գործընթացը: es
  • Որոշ գրաֆիկական պատկերների եզրին են հետեւյալ ընտրության մեթոդները, ինչպիսիք են մագնիս է "Ընտրանքի գործիք Photoshop

Ձեր որոշ մեթոդներ լուծելու [[]] ընդմիջում պլանավորման խնդիրները Ձեր որոշ մեթոդներ լուծելու բառը փաթեթավորեք հետ կապված խնդիրներ Ձեր որոշ մեթոդներ լուծելու ճանապարհորդություն վաճառողն խնդրի, կամ էլ հենց (in exponential ժամանակ), կամ մոտ (օրինակ միջոցով bitonic տուր)

Ձեր ստերեո ալգորիթմները լուծելու թղթակցության խնդիրը օգտագործվել ստերեո տեսլականի համար.

Ձեր Որոշ մոտավոր լուծույթ մեթոդներ է գծային որոնման խնդրի.

Տես նաեւ խմբագրել 

* Bellman հավասարումը
* Ուռուցիկություն տնտեսագիտության
* Բաժանելուն եւ նվաճել ալգորիթմ:
* Ագահ ալգորիթմը
* Մարկովը որոշման գործընթացը:
* Ոչ ուռուցիկություն (տնտեսագիտություն)
* Stochastic ծրագրավորում==վկայակոչում==

Կաղապար:Ցուցակ

հետագա ընթերցում խմբագրել

Տնտեսագիտություն | հրատարակիչ = MIT Press}}. An մատչելի Պահեստավորված դինամիկ ծրագրավորման Տնտեսագետ. Հղումը պարունակում օրինակելի ծրագրեր.

Կարգապահություն եւ դինամիկ ծրագրավորման նկատմամբ հերթական տվյալներ" ignored (օգնություն); Text "Թողարկում # 3" ignored (օգնություն)

Կաղապար:Օպտիմալացում ալգորիթմները

Արտաքին հղումներ խմբագրել

Տեսանյութեր: Programación dinámica Դա: Programmazione dinamica Նա: תכנון דינמי Մլ: ഡൈനാമിക് പ്രോഗ്രാമിങ് Մեծ Բրիտանիա: Динамічне програмування

Ստացված է «https://hy.wikipedia.org/w/index.php?title=Մասնակից:Haso1111&oldid=7019530» էջից