Динамикалык программалоо, негизги

программалоо милдеттери кээде ПКнын эс жүктер маалымат айкаштарын ири өлчөмдөгү сорттой талап кылынат аткарууда оптималдуу чечүүнү тандоо үчүн. Мындай ыкмалар, мисалы, "Бөл да башкар" деген программалоо методу, камтыйт. Бул учурда алгоритм өзүнчө майда subtasks салып бөлүү маселесин карайт. Бул ыкма анча subtasks өз ара көз карандысыз болуп саналган учурларда гана колдонулат. бири-бирине көз каранды суб-милдеттердин болсо, ашыкча ишин аткарып алдын алуу үчүн, 50 жаштан сунушталган америкалык R.Bellmanom динамикалык программалоо ыкмасын колдонот.

ыкма

Динамикалык программалоо анын н айрым этаптарын бөлүшүп, оптималдуу чечим N өлчөмдүү маселени аныктоо болуп саналат. Алардын ар бир өзгөрмөлүү карата бир суб-милдети болуп саналат.

Бул ыкманын башкы артыкчылыгы Бир өлчөмдүү оптималдаштыруу көйгөй менен алектенген иштеп ордуна N өлчөмдүү маселенин subtasks, биздин негизги максаты "төмөндөн жогору карай" барып жатат деп каралышы мүмкүн.

Бул суб-милдеттери бири бири менен байланышылган учурларда динамикалык программалоо колдонуу максатка ылайыктуу болуп саналат, башкача айтканда, жалпы модулдарды бөлүшүү. алгоритм жолу subtasks ар бир чечим менен камсыз кылат, жана үнөмдөө жооп атайын столдун жүзөгө ашырылат. Бул ошол эле суб-милдети менен кайрадан жолугуп, ал жооп эсептөө мүмкүн эмес кылат.

Динамикалык программалоо тапшырма койгойун оптималдаштыруу. Бул методдун жазуучу R. Беллмандын оптималдуулугун Негизинен тарабынан коюлган: Бул кадамда аныкталган ар бир кадам менен чечүүгө алгачкы мамлекет болбосун, бардык кадам-жылдын акырына карата системаны кабыл алган мамлекетке карата оптималдуу тандоо үчүн төмөнкү.

ыкма диалектисине, же Recursion жолу менен чечилет милдеттерди аткаруусун жакшыртат.

Курулуш милдети алгоритми

Динамикалык программалоо алгоритми милдети анын чечүү үчүн эки же андан көп subtasks бөлүнүп бардык subtasks үчүн оптималдуу чечүү турат ушундай милдеттерди курулушун камтыйт, ал камтыйт. Андан сырткары, ал кайталоо мамилесин, жана жалпы иш үчүн оптималдуу параметр маанилери эсептөө жазуу зарыл.

Кээде, 3-кадам ар бир тапшырманы жүрүшү боюнча кээ бир кошумча маалымат жаттап болуп саналат. Бул кайра мээге деп аталат.

Колдонмо ыкмасы

эки мүнөздүү өзгөчөлүктөрү бар болсо, динамикалык программалоо колдонулат:

• subtasks үчүн оптималдуу;
• subproblems кайталаган көйгөйү бар.

динамикалык программалоо боюнча оптималдаштыруу маселесин чечүү, биринчи чечүү структурасын сүрөттөп керек. эритмеси subtasks мыкты чечимдердин турат, эгерде тапшырма оптималдуу болушу керек. Бул учурда, ал динамикалык программалоо пайдалануу максатка ылайыктуу.

Маселенин экинчи мүлк, бул ыкма абдан маанилүү, - суб-милдеттерди бир аз саны. Ошол эле бирин-бири кайталаган суб-көйгөйлөрдү колдонуп маселенин Recursive чечүү саны баштапкы маалыматтын көлөмүнө жараша болот. жооп атайын столдун сакталат, программа, бул маалыматты колдонуу менен убакытты үнөмдөйт.

Өзгөчө натыйжалуу маселе олуттуу этап менен чечимдерди кабыл алуу үчүн зарыл динамикалык программалоо пайдалануу болуп эсептелет. Мисалы, алмаштыруу жана жабдууларды ремонттоо маселесинин жөнөкөй бир мисал карап көрөлү. Кел, ошол эле учурда, шина өндүрүшү үчүн чечүүчү машина комбинатынын деп эки башка түрлөрүнө чарчап кылып көрөлү. түрлөрүнүн бири албаган учурда, ал машинаны бөлө зарыл. Бул учурда машинаны бөлө үчүн кээде пайдалуу алмаштыруу жана экинчи түрү, бул түрү кийинки этапта жүрбөгөн болот деп түшүнсө болот. Алар сөзсүз баштаганга чейин, өзгөчө, бул эки иш өзгөрөт ордуна жөнөкөйүрөөк бери. Динамикалык программалоо ыкмасы мыкты стратегиясын бул түрлөрүн алмаштыруу жагынан, бардык себептерди эске алуу менен аныктайт: пайдалануунун уланып түрлөрүнүн пайда, машина жоготуу, бош, Кыйылган шиналар жана наркы.