Դինամիկ ծրագրավորում, հիմնական սկզբունքները

Ընտրել օպտիմալ լուծում, երբ իրականացնող Ծրագրավորման խնդիրները երբեմն պահանջվում է տեսակավորելու մեծ քանակությամբ տվյալների համադրությունը, որ բեռների հիշատակը անհատական համակարգչի. Նման մեթոդները ներառում են, օրինակ, ծրագրավորում մեթոդը, «բաժանիր եւ տիրիր». Այս դեպքում ալգորիթմը նախատեսում բաժանում խնդիրը առանձին փոքր subtasks: Այս մեթոդը կիրառելի է միայն այն դեպքերում, երբ փոքր Ենթախնդիրներ են երկուստեք անկախ. Խուսափելու համար կատարողական անհարկի աշխատել, եթե փոխադարձ կախվածության ենթահաշիվների առաջադրանքների, օգտագործում է դինամիկ ծրագրավորման մեթոդը առաջարկվող ամերիկյան R.Bellmanom է 50s.

այդ մեթոդը

Դինամիկ ծրագրավորման է որոշելու օպտիմալ լուծում է n- չափանի խնդիրը, կիսելով իր n առանձին փուլերը: Նրանցից յուրաքանչյուրը մի ենթահանձնաժողով խնդիրն նկատմամբ մեկ փոփոխականով:

Հիմնական առավելությունը այս մոտեցումը կարելի է համարել, որ մշակողները ներգրավված են մեկ-ծավալային օպտիմալացման խնդիր Ենթախնդիրներ փոխարեն n-ծավալային խնդրի, եւ մեր առաջնային նպատակն է, պատրաստվում է «ներքեւից-վերեւ»:

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

Դինամիկ ծրագրավորման խնդիրն է լուծում խնդիրը օպտիմալացման. Հեղինակն այս մեթոդի ձեւակերպվել է Ռ. Bellman optimality սկզբունքի, ինչ է նախնական վիճակը յուրաքանչյուր քայլերի եւ լուծման սահմանված այս քայլով, բոլոր հետեւյալը ընտրել օպտիմալ պետության նկատմամբ, որը ստանում համակարգը վերջում քայլի:

Այդ մեթոդը բարելավում կատարումը առաջադրանքների լուծվեն տարբերակների կամ ռեկուրսիա:

Շենքը խնդիրն ալգորիթմ

Դինամիկ ծրագրավորման ալգորիթմ ներառում է շինարարությունը այնպիսի խնդիրների, որոնք խնդիրը այնքան է բաժանվել երկու կամ ավելի subtasks է դրա լուծման բաղադրված է օպտիմալ լուծման բոլոր subtasks, այն ներառում: Բացի այդ, դա անհրաժեշտ է գրել կրկնություն հարաբերություն, եւ հաշվարկման օպտիմալ պարամետր արժեքները առաջադրանքի, որպես ամբողջություն.

Երբեմն, 3-րդ քայլին է անգիր որոշ լրացուցիչ տեղեկություններ է առաջընթացի յուրաքանչյուր առաջադրանքի: Սա կոչվում է Return Stroke:

Օգտագործման եղանակը

Դինամիկ ծրագրավորման կիրառվում է, երբ կան երկու բնորոշ հատկանիշները:

• համար օպտիմալ subtasks.
• ներկայությունը խնդրի overlapping subproblems:

Լուծելու օպտիմալացման խնդիրը դինամիկ ծրագրավորման, դուք նախ պետք է նկարագրել կառուցվածքը լուծման: Խնդիրն ունի օպտիմալ է, եթե լուծումը կազմված լավագույն որոշումների իր subtasks: Այս դեպքում, դա նպատակահարմար է օգտագործել դինամիկ ծրագրավորման.

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

Հատկապես արդյունավետ է օգտագործում դինամիկ ծրագրավորման, երբ խնդիրն, ըստ էության, ինչն անհրաժեշտ է որոշումներ կայացնել փուլերով. Օրինակ, համարում է մի պարզ օրինակ է խնդրի փոխարինման եւ վերանորոգման սարքավորումներ: Եկեք ասում է, որ ձուլման մեքենա գործարանի արտադրության անվադողերի միեւնույն ժամանակ, կատարել դող երկու տարբեր ձեւերով: Այն դեպքում, որ ձեւերից մեկը չի, դա անհրաժեշտ է disassemble մեքենա: Հասկանալի է, որ երբեմն ավելի շահութաբեր է փոխարինել եւ երկրորդ ձեւ է, որպեսզի ապամոնտաժելու մեքենա դեպքում, եւ այդ ձեւը պիտի լինի unworkable է հաջորդ փուլում: Հատկապես, քանի որ դա ավելի հեշտ է փոխարինել էլ աշխատանքային ձեւավորել, մինչեւ նրանք սկսում են ձախողել. Դինամիկ ծրագրավորման մեթոդը որոշում լավագույն ռազմավարությունը հարցում փոխարինման այդ ձեւերի, հաշվի առնելով բոլոր գործոնները: օգուտներին շարունակվող ձեւերի շահագործման, կորստի մեքենա downtime, արժեքի անտեսվեցին անվադողերի եւ ավելի.