資源描述：
《0009算法筆記【動態(tài)規(guī)劃】動態(tài)規(guī)劃與斐波那契數(shù)列問題,最短路徑問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、1、動態(tài)規(guī)劃算法:動態(tài)規(guī)劃：通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。動態(tài)規(guī)劃常常適用于好重疊子M題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題?；舅枷耄喝羲＝庖粋€給定問題，我們需要解其不冋部分（即子問題），再合并子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次，從而減少計(jì)算量：一旦某個給定子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接?xùn)吮怼＿@種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時特別有用。與分治法區(qū)別：動態(tài)規(guī)劃算法與分治法
2、類似，都使用了將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)值的思路，但動態(tài)規(guī)劃不是分治法：關(guān)鍵在于分解岀來的各個子問題的性質(zhì)不同。分治法耍求各個子問題是獨(dú)立的（即不包含公;R?的子問題），W此一旦遞歸地求出各個子問題的解后，便可自下而上地將子問題的解合并成原問題的解。如果各子問題是不獨(dú)立的，那么分治法就要做許多不必要的工作，重復(fù)地解公共的子問題。動態(tài)規(guī)劃與分治法的不同之處在于動態(tài)規(guī)劃允許這些子問題不獨(dú)立（即各子問題可包含公共的子問題），它對毎個子問題只解一次，并將結(jié)果保存起來，
3、避免每次碰到時都要重復(fù)計(jì)算。關(guān)術(shù)語:(1)階段：把所給求解問題的過程恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同，描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的。此外，也有階段變量是連續(xù)的情形。如果過程可以在任何時刻作出決策，且在任意兩個不冋的時刻之間允許有無窮多個決策時，階段變量就是連續(xù)的。(2)狀態(tài)：狀態(tài)表示每個階段開始面臨的自然狀況或客觀條件，也稱為不可控因素。過程的狀態(tài)通常可以用一個或一組數(shù)來描述，稱為狀態(tài)變量。一般狀態(tài)是離散的，但有時為了方便也將狀態(tài)取成連
4、續(xù)的。(3)無后效性：狀態(tài)具有下面的性質(zhì)，如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所冇各階段都確定時，整個過程也就確定了。換句詁說，過程的每一次實(shí)現(xiàn)付以用一個狀態(tài)序列表示，在前面的例子巾每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個線路也就完全確定。從某一階段以后的線路開始，當(dāng)這段的始點(diǎn)給定時，不受以前線路，所通過的點(diǎn)，的影響。狀態(tài)的這個性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展，這個性質(zhì)稱為無后效性。(4)決策：一個階段的狀態(tài)給定以后，從該
5、狀態(tài)演變到下一階段某個狀態(tài)的一種選擇(行動)稱為決策。在最優(yōu)控制屮，也稱為控制。在許多間題巾，決策可以自然而然地表示為一個數(shù)或一組數(shù)。不同的決策對應(yīng)著不同的數(shù)值。描述決策的變量稱決策變量，因狀態(tài)滿足無后效性，故在每個階段選擇決策吋只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史。決策變量的范圍稱為允許決策集合(1)策略：由每個階段的決策組成的序列稱為策略。對于每一個實(shí)際的多階段決策過程，討供選取的策略有一定的范圍限制，這個范圍稱為允許策略柒合。允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略⑹最優(yōu)性原理：作為整個過程
6、的最優(yōu)策略，它滿足，相對前面決策所形成的狀態(tài)而言，余卜*的子策略必然構(gòu)成一最優(yōu)子策略。問題特征：(1)最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。(2)重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。算法步驟：(1)分析最優(yōu)值的結(jié)構(gòu)，刻畫其結(jié)構(gòu)特征;(2)遞歸地定義最優(yōu)值；(3)按自底向
7、上或自頂向下記憶化的方式計(jì)算最優(yōu)2、斐波那契數(shù)列(Fibonaccipolynomial)計(jì)算斐波那契數(shù)列(Fibonaccipolynomial)的一個最基礎(chǔ)的算法是,直接按照定義計(jì)算：[cpp]viewplaincopy1.//3ml未優(yōu)化斐波那契數(shù)列計(jì)算2.#include"stdafx.h"3.#include4.4.usingnamespacestd;67.voidinput(int&n);8.intfib(intn);910.intmain()11.{12.intn;13
8、.input(n);14.cout<<"fib("<>n;21.}23.22.intfib(intn)23.{24.if(n==0
9、
10、n==l)25.{26.return1;27.}28.else29.{30.returnfib(n-l)+fib(n-2)
