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