定義
動(dòng)態(tài)規(guī)劃（dynamic programming, DP) 是運(yùn)籌學(xué)的一個(gè)分支逗鸣，是求解決策過(guò)程最優(yōu)化的過(guò)程。是一種解決問(wèn)題的方法无畔，也可定義為一種數(shù)學(xué)模型闽寡。在20世紀(jì)50年代初，由美國(guó)數(shù)學(xué)家貝爾曼等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)相味，提出了著名的最優(yōu)化原理拾积，從而創(chuàng)立了動(dòng)態(tài)規(guī)劃。
基本原理
有一類活動(dòng)攻走，可以將過(guò)程分為若干個(gè)互相聯(lián)系的階段殷勘，每個(gè)階段做出決策，從而使得整個(gè)過(guò)程有最好的效果昔搂。各個(gè)階段決策的選取依賴當(dāng)前的狀態(tài)玲销，還影響以后的發(fā)展。通過(guò)各個(gè)階段組成的決策序列確定整個(gè)過(guò)程的一條活動(dòng)路線摘符，把問(wèn)題看作一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就叫做多階段決策問(wèn)題贤斜。
在多階段決策問(wèn)題中，各個(gè)階段采取的決策逛裤，一般來(lái)說(shuō)是與時(shí)間有關(guān)的瘩绒，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移带族，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的锁荔，稱這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)規(guī)劃方法。
基本思想
動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題蝙砌。在這類問(wèn)題中阳堕，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值择克，我們希望找到具有最優(yōu)值的解恬总。
其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題肚邢，然后從這些子問(wèn)題的解得到原問(wèn)題的解壹堰。
各個(gè)子問(wèn)題不是相互獨(dú)立的。為了避免子問(wèn)題的重復(fù)計(jì)算骡湖，我們使用一個(gè)表來(lái)記錄所有已求解的子問(wèn)題的結(jié)果贱纠，稱為記憶化存儲(chǔ)。這是動(dòng)態(tài)規(guī)劃的基本思路响蕴。具體的動(dòng)態(tài)規(guī)劃算法多種多樣并巍，但都有相同的填表格式。
三大重要性質(zhì)
- 最優(yōu)子結(jié)構(gòu)性質(zhì)：一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的换途。一個(gè)問(wèn)題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)懊渡。
- 子問(wèn)題重疊性質(zhì)：有些子問(wèn)題在遞歸算法自頂向下求解過(guò)程中，有些會(huì)被重復(fù)計(jì)算军拟。動(dòng)態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余剃执，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)懈息，它在實(shí)現(xiàn)的過(guò)程中肾档，不得不存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其他的算法辫继。選擇動(dòng)態(tài)規(guī)劃算法是因?yàn)閯?dòng)態(tài)規(guī)劃算法在空間上可以承受怒见，而搜索算法在時(shí)間上卻無(wú)法承受，所以我們舍空間而取時(shí)間姑宽。
- 無(wú)后效性： 過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展遣耍。每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。如果給定某一階段的狀態(tài)炮车，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響舵变，所有各階段都確定時(shí)，整個(gè)過(guò)程也就確定了瘦穆。
分類
根據(jù)決策過(guò)程的演變可分為確定性或者隨機(jī)性纪隙。
按照時(shí)間參量可分為離散或者連續(xù)的變量。
所以有四種：離散確定性扛或、離散隨機(jī)性绵咱、連續(xù)確定性、連續(xù)隨機(jī)性四種決策過(guò)程模型熙兔。
使用場(chǎng)景
應(yīng)用廣泛悲伶，包括工程技術(shù)、經(jīng)濟(jì)黔姜、工業(yè)生產(chǎn)拢切、軍事以及自動(dòng)化控制等領(lǐng)域，并在背包問(wèn)題秆吵、生產(chǎn)經(jīng)營(yíng)問(wèn)題淮椰、資金管理問(wèn)題、資源分配問(wèn)題纳寂、最短路徑問(wèn)題和復(fù)雜系統(tǒng)可靠性問(wèn)題等中取得了顯著的效果主穗。
局限性
- 沒(méi)有統(tǒng)一的處理方法，具體問(wèn)題具體性質(zhì)和技巧來(lái)分析和處理
- 變量的維數(shù)越大毙芜，總的計(jì)算量和存儲(chǔ)量變大忽媒。受存儲(chǔ)空間和計(jì)算速度的限制，即‘維數(shù)障礙’
以上僅供學(xué)習(xí)腋粥，如侵權(quán)請(qǐng)聯(lián)系；抻辍＜懿堋！
