動態(tài)規(guī)劃的技巧——階段的劃分和狀態(tài)的表示-資料下載頁
2025-08-03 01:02本頁面
【正文】 我們一眼便可看出這題應(yīng)該用動態(tài)規(guī)劃來解決。但是，如何動態(tài)規(guī)劃呢？如何劃分階段，又如何選擇狀態(tài)呢？方法1以花束的編號來劃分階段。在這里，第k階段布置第k束花，共有F束花，有F+1個階段，增加第F+1階段是為了計算的方便；狀態(tài)變量xk表示第k束花所在的花瓶。而對于每一個狀態(tài)xk，決策uk就是第k+1束花放置的花瓶號；最優(yōu)指標(biāo)函數(shù)fk(xk)表示從第k束花到第n束花所得到的最大美學(xué)值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F是花的總數(shù)。狀態(tài)轉(zhuǎn)移方程為規(guī)劃方程為邊界條件為：,事實上這是一個虛擬的邊界。最后要求的最大美學(xué)價值是方法2方法1的規(guī)劃方程中的允許決策空間：xk+1≤uk≤V(Fk)+1 比較麻煩，因此有待改進。還是以花束的編號來劃分階段，第k階段布置第k束花；狀態(tài)變量xk表示第k束花所在的花瓶；注意，這里我們考慮倒過來布置花瓶，即從第F束花開始布置到第1束花。于是狀態(tài)變量uk表示第k1束花所在的花瓶；最優(yōu)指標(biāo)fk(xk)表示從第一束花到第k束花所獲得的美學(xué)價值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F是花的總數(shù)。則狀態(tài)轉(zhuǎn)移方程為：規(guī)劃方程為：增加的虛擬邊界條件為：最后要求的最大美學(xué)價值是：可以看出，這種方法實質(zhì)上和方法1沒有區(qū)別，但是允許決策空間的表示變得簡單了。方法3以花瓶的數(shù)目來劃分階段，第k個階段決定花瓶k中是否放花；狀態(tài)變量xk表示前k個花瓶中放了多少花；而對于任意一個狀態(tài)xk，決策就是第xk束花是否放在第k個花瓶中，用變量uk=1或0來表示。最優(yōu)指標(biāo)函數(shù)fk(xk)表示前k個花瓶中插了xk束花，所能取得的最大美學(xué)值。注意，這里仍然是倒過來考慮。狀態(tài)轉(zhuǎn)移方程為規(guī)劃方程為邊界條件為三種不同的方法都成功地解決了問題，只不過因為階段的劃分不同，狀態(tài)的表示不同，決策的選擇有多有少，所以算法的時間復(fù)雜度也就不同。這個例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規(guī)劃方法。有時各種方法所產(chǎn)生的效果是差不多的，但更多的時候，就像我們的例子一樣，兩種方法會在某個方面有些區(qū)別。所以，在用動態(tài)規(guī)劃解題的時候，可以多想一想是否有其它的解法。對于不同的解法，要注意比較，好的算法好在哪里，差一點的算法差在哪里。從各種不同算法的比較中，我們可以更深刻地領(lǐng)會動態(tài)規(guī)劃的構(gòu)思技巧。
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1