資源描述：
《算法筆記動態(tài)規(guī)劃動態(tài)規(guī)劃與斐波那契數(shù)列問題最短路徑問題.docx》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、1、動態(tài)規(guī)劃算法：????動態(tài)規(guī)劃：通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。???????基本思想：若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時特別有用。????與分治法
2、區(qū)別：動態(tài)規(guī)劃算法與分治法類似，都使用了將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)值的思路，但動態(tài)規(guī)劃不是分治法：關(guān)鍵在于分解出來的各個子問題的性質(zhì)不同。分治法要求各個子問題是獨(dú)立的(即不包含公共的子問題)，因此一旦遞歸地求出各個子問題的解后，便可自下而上地將子問題的解合并成原問題的解。如果各子問題是不獨(dú)立的，那么分治法就要做許多不必要的工作，重復(fù)地解公共的子問題。動態(tài)規(guī)劃與分治法的不同之處在于動態(tài)規(guī)劃允許這些子問題不獨(dú)立(即各子問題可包含公共的子問題)，它對每個子問題只解一次，
3、并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計算。??????相關(guān)術(shù)語：???(1)階段：把所給求解問題的過程恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同，描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的。此外，也有階段變量是連續(xù)的情形。如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變量就是連續(xù)的。???(2)狀態(tài)：狀態(tài)表示每個階段開始面臨的自然狀況或客觀條件，也稱為不可控因素。過程的狀態(tài)通?？梢杂靡粋€或一組數(shù)來描述,稱為狀態(tài)變量。一般狀
4、態(tài)是離散的,但有時為了方便也將狀態(tài)取成連續(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ì)稱為無后效
5、性。???(4)決策：一個階段的狀態(tài)給定以后,從該狀態(tài)演變到下一階段某個狀態(tài)的一種選擇(行動)稱為決策。在最優(yōu)控制中,也稱為控制。在許多間題中,決策可以自然而然地表示為一個數(shù)或一組數(shù)。不同的決策對應(yīng)著不同的數(shù)值。描述決策的變量稱決策變量,因狀態(tài)滿足無后效性,故在每個階段選擇決策時只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史。決策變量的范圍稱為允許決策集合。????(5)策略：由每個階段的決策組成的序列稱為策略。對于每一個實(shí)際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中
6、達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。???(6)最優(yōu)性原理:作為整個過程的最優(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ù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。???
7、?算法步驟：????(1)分析最優(yōu)值的結(jié)構(gòu)，刻畫其結(jié)構(gòu)特征；???(2)遞歸地定義最優(yōu)值；???(3)按自底向上或自頂向下記憶化的方式計算最優(yōu)???2、斐波那契數(shù)列(Fibonaccipolynomial)???計算斐波那契數(shù)列(Fibonaccipolynomial)的一個最基礎(chǔ)的算法是，直接按照定義計算：[cpp]?viewplain?copy1.//3m1?未優(yōu)化斐波那契數(shù)列計算??2.#include?"stdafx.h"??3.#include???4.??5.using?na
8、mespace?std;???6.??7.void?input(int?&n);??8.int?fib(int?n);??9.??10.int?main()??11.{??12.????int?n;??13.????input(n);??14.????cout<<"fib("<
