Динамичното програмиране е концепция, разработена от Ричард Белман, математик и икономист.
По това време Белман търсеше начин за решаване на сложни проблеми с оптимизацията. Проблемите с оптимизацията изискват да изберете най-доброто решение от набор от опции.
Пример за оптимизационен проблем е проблемът на пътуващия търговец. Целта е да се намери най-краткият маршрут, който да позволи на продавача да посети всеки град точно веднъж и да се върне в началния град.
Подходът на Белман към тези проблеми беше да ги раздели на по-малки подпроблеми и да разреши подпроблемите от най-малките до най-големите. След това той съхранява резултатите от подпроблемите и ги използва повторно за решаване на по-големи подпроблеми. Това е основната идея зад динамичното програмиране.
Съдържание
Какво е динамично програмиране?
Динамичното програмиране решава проблемите на оптимизацията, като ги разделя на по-малки подпроблеми, като решава всеки подпроблем веднъж и съхранява техните решения, така че да могат да бъдат използвани повторно и комбинирани за решаване на по-големия проблем. Проблемите се решават от най-малките до най-големите, което позволява решенията да бъдат използвани повторно.
Как работи динамичното програмиране?
Решаването на проблем чрез динамично програмиране включва следните стъпки:
За да видим това в действие, ние изчисляваме 6-то число на Фибоначи, F(6), използвайки този процес.
Първо, дефинирайте подпроблемите, които трябва да бъдат решени.
F(n) = F(n-1) + F(n-2) за n > 1
Следователно: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Втората стъпка включва решаване на всеки подпроблем с помощта на рекурсивна функция или итеративен процес. Ние решаваме подпроблемите от най-малките до най-големите, като използваме повторно резултатите от по-малките подпроблеми. Това ни дава следното:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Докато решаваме всеки от подпроблемите, ние съхраняваме решенията в масив или таблица, така че да могат да бъдат използвани повторно при решаването на по-големи подпроблеми, като например:
След като всички подпроблеми са решени, ние използваме решенията, за да конструираме решението на първоначалния проблем.
В този случай решението на първоначалния проблем е 6-то число на Фибоначи, което се намира чрез сумиране на резултатите от F(5) и F(4), подпроблеми, идентифицирани от най-големия проблем. Резултатът ни дава 8.
Къде и защо се използва динамичното програмиране?
Динамичното програмиране се използва в области, където имаме проблеми, които могат да бъдат разделени на по-малки подпроблеми, а техните решения се използват за решаване на по-големи проблеми.
Тези области включват компютърни науки, икономика, математика и инженерство. В компютърните науки се използва за решаване на проблеми, включващи последователности, графики и цели числа и в конкурентно програмиране.
В икономиката се използва за решаване на проблеми с оптимизацията във финансите, производството и разпределението на ресурсите. В математиката динамичното програмиране се използва в теорията на игрите, статистиката и вероятността, където се използва за решаване на проблеми с оптимизацията.
В инженерството се използва за решаване на проблеми в разпределението на ресурсите, планирането, производството, комуникациите и системите за управление.
Има няколко предимства при използването на динамично програмиране за решаване на проблеми с оптимизацията:
Когато става въпрос за решаване на проблеми с оптимизацията, динамичното програмиране е много полезен инструмент за осигуряване на ефективност на решенията.
Подходи, използвани в динамичното програмиране
В динамичното програмиране се използват два подхода за решаване на оптимизационни проблеми. Това са подходът отгоре надолу и подходът отдолу нагоре.
Подход отгоре надолу
Този подход е известен също като мемоизация. Мемоизацията е техника за оптимизация, използвана предимно за по-бързи компютърни програми чрез съхраняване на резултатите от извиквания на функции в кеша и връщане на кешираните резултати следващия път, когато са необходими, вместо да ги изчислява отново.
Подходът отгоре надолу включва рекурсия и кеширане. Рекурсията включва функция, която се самоизвиква с по-прости версии на проблема като свой аргумент. Рекурсията се използва за разделяне на проблема на по-малки подпроблеми и решаване на подпроблемите.
След като подпроблемът бъде разрешен, неговият резултат се кешира и се използва повторно, когато възникне подобен проблем. Отгоре надолу е лесен за разбиране и прилагане и решава подпроблем само веднъж. Недостатъкът му обаче е, че заема много памет поради рекурсия. Това може да доведе до грешка при препълване на стека.
Подход отдолу нагоре
Подходът отдолу нагоре, известен също като табулиране, премахва рекурсията, заменяйки я с итерация, като по този начин се избягват грешки при препълване на стека.
При този подход голям проблем се разделя на по-малки подпроблеми и решенията на подпроблемите се използват за решаване на по-големия проблем.
По-малките подпроблеми първо се решават от най-големия към най-малкия и техните резултати се съхраняват в матрица, масив или таблица, откъдето идва и името табулиране.
Съхранените резултати решават по-големи проблеми, които зависят от подпроблемите. След това резултатът от първоначалния проблем се намира чрез решаване на най-големия подпроблем с помощта на предварително изчислени стойности.
Този подход има предимството, че е ефективен върху паметта и времето, като премахва рекурсията.
Примери за проблеми, които могат да бъдат решени чрез динамично програмиране
Следват някои програмни проблеми, които могат да бъдат разрешени с помощта на динамично програмиране:
#1. Проблем с раницата
Източник: Wikipedia
Раницата е чанта, изработена от платно, найлон или кожа, обикновено завързана на гърба и използвана от войници и туристи за носене на провизии.
В проблема с раницата ви се представя раница и като се има предвид нейната товароносимост, от вас се изисква да изберете предмети, всеки със своята стойност. Вашият избор трябва да бъде такъв, че да получите максималната обща стойност на избраните артикули и теглото на артикулите да е по-малко или равно на капацитета на раницата.
Пример за проблем с раницата е даден по-долу:
Представете си, че отивате на поход и имате раница с капацитет 15 килограма. Имате списък с елементи, които можете да носите със себе си, заедно с техните стойности и тегла, както е показано в таблицата по-долу:
Артикул Стойност Тегло Палатка 2003 Спален чувал 1502 Печка 501 Храна 1002 Бутилка вода 100,5 Комплект за първа помощ 251
Изберете подгрупа от артикули, които да донесете, така че общата стойност на артикулите да е максимална, докато общото тегло е по-малко или равно на капацитета на раницата, който е 15 килограма.
Приложенията в реалния свят на проблема с раницата включват избор на ценни книжа, които да се добавят към портфолио, за да се минимизира рискът и да се увеличи максимално печалбата и намирането на най-малко разточителните начини за намаляване на суровините.
#2. Проблем с планирането
Проблемът с планирането е оптимизационен проблем, при който целта е оптимално да се присвоят задачи на набор от ресурси. Ресурсите могат да бъдат машини, персонал или други ресурси, използвани за изпълнение на задачите.
Пример за проблем с графика е даден по-долу:
Представете си, че сте ръководител на проекти, отговорен за планирането на набор от задачи, които трябва да бъдат изпълнени от екип от служители. Всяка задача има начален час, краен час и списък на служителите, които са квалифицирани да я изпълнят.
Ето таблица, която описва задачите и техните характеристики:
Задача Начален час Краен час Квалифицирани служители T1911A, B, CT21012A, CT31113B, CT41214A, B
Възлагайте всяка задача на служител, за да минимизирате общото време за изпълнение.
Проблемът с планирането може да се срещне в производствената индустрия, когато се опитвате да оптимизирате разпределението на ресурси като машини, материали, инструменти и труд.
Може да се срещне и в здравеопазването при оптимизиране на използването на легла, персонал и медицински консумативи. Други отрасли, в които може да възникне този проблем, са управление на проекти, управление на веригата за доставки и образование.
#3. Проблем с пътуващия търговец
Източник: Wikipedia
Това е един от най-изследваните оптимизационни проблеми, които могат да бъдат решени с помощта на динамично програмиране.
Проблемът с пътуващия търговец предоставя списък с градове и разстоянията между всяка двойка градове. От вас се изисква да намерите най-краткия възможен маршрут, който посещава всеки град точно веднъж и се връща в града на произход.
Пример за проблем с пътуващ търговец е даден по-долу:
Представете си, че сте продавач, който трябва да посети набор от градове за възможно най-кратко време. Имате списък с градовете, които трябва да посетите, и разстоянията между всяка двойка градове, както е показано в таблицата по-долу:
ГрадABCDEA010152030B100352515C153503020D202530010E301520100
Проблемът с пътуващия търговец може да се срещне в индустрията за свободното време, когато се опитвате да планирате маршрути за туристи, логистиката, когато планирате доставката на стоки, транспорта, когато планирате автобусни маршрути, и в индустрията за продажби, наред с други.
Ясно е, че динамичното програмиране има много приложения в реалния свят, което помага да научите повече за него.
Разгледайте следните ресурси, за да разширите знанията си за динамично програмиране.
Ресурси
Динамично програмиране от Ричард Белман
Динамично програмиране е книга от Ричард Белман, който измисли динамичното програмиране и го разви в ранните му етапи.
Книгата е написана по лесен за разбиране начин, който изисква само основни познания по математика и смятане за разбиране на текста. В книгата Белман въвежда математическата теория на многоетапния процес на вземане на решения, който е ключов в динамичното програмиране.
След това книгата разглежда проблемите с тесните места в многоетапните производствени процеси, теоремите за съществуване и уникалност и уравнението за оптимален инвентар.
Най-хубавото в книгата е, че Белман предлага примери за много сложни проблеми в области като логистика, теория на графици, теория на комуникацията, математическа икономика и контролни процеси и показва как динамичното програмиране може да реши проблемите.
Книгата се предлага във версии за Kindle, с твърди корици и с меки корици.
Магистърски курс по алгоритми за динамично програмиране
Този магистърски курс по алгоритми за динамично програмиране от Udemy се предлага от Apaar Kamal, софтуерен инженер в Google, и Prateek Narang, който също е работил с Google.
Курсът е оптимизиран, за да помогне на обучаемите да се отличат в състезанието по програмиране, което включва много проблеми, които изискват динамично програмиране.
Освен за състезатели по програмиране, курсът е идеален за програмисти, които искат да подобрят разбирането си за алгоритмите и хора, които се подготвят за интервюта по програмиране и онлайн кръгове за кодиране.
Курсът, който е с продължителност над 40 часа, обхваща задълбочено динамичното програмиране. Курсът първо предлага опресняване на концепции като рекурсия и обратно проследяване.
След това обхваща динамично програмиране в теорията на игрите, низове, дървета и графики, степенуване на матрици, битови маски, комбинаторика и подпоследователности, проблеми с разделянето и многомерно динамично програмиране, сред много други концепции.
Състезателно програмиране Essentials, Master Algorithms
Udemy предлага Основен курс по конкурентно програмиране от Prateek Narang и Amal Kamaar, който обхваща динамично програмиране, математика, теория на числата и усъвършенствани структури от данни и алгоритми по начин, който е полезен и подходящ за конкурентни програмисти.
Курсът предлага опресняване на структурите от данни и алгоритмите, преди да се потопите в по-сложни алгоритми и техники, които са полезни в конкурентното програмиране.
Курсът обхваща динамично програмиране, математика, теория на игрите, съвпадение на шаблони, битово маскиране и безброй усъвършенствани алгоритми, използвани и тествани в състезания по програмиране.
Курсът на Udemy е разделен на 10 модула и 42 раздела и предоставя много практически въпроси след всеки раздел. Този бестселър курс е задължителен за всеки, който се интересува от конкурентно програмиране.
Заключителни думи
Динамичното програмиране е полезно умение за всеки програмист да се научи да подобрява решаването на проблеми от реалния свят. Следователно програмистите трябва да обмислят преминаването през предложените ресурси, за да добавят този важен инструмент към своята кутия с инструменти.
След това можете да разгледате езиците за програмиране, които да използвате в науката за данни.