日韩黑丝制服一区视频播放|日韩欧美人妻丝袜视频在线观看|九九影院一级蜜桃|亚洲中文在线导航|青草草视频在线观看|婷婷五月色伊人网站|日本一区二区在线|国产AV一二三四区毛片|正在播放久草视频|亚洲色图精品一区

搜索
分享

常用算法二（動(dòng)態(tài)規(guī)劃）

 第一閱覽室 2014-04-19

一、基本概念

    動(dòng)態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，這種多階段最優(yōu)化決策解決問題的過程就稱為動(dòng)態(tài)規(guī)劃。

二、基本思想與策略

    基本思想與分治法類似，也是將待求解的問題分解為若干個(gè)子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時(shí)，列出各種可能的局部解，通過決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個(gè)子問題就是初始問題的解。

    由于動(dòng)態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對每一個(gè)子問題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。

    與分治法最大的差別是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。

 

三、適用的情況

能采用動(dòng)態(tài)規(guī)劃求解的問題的一般要具有3個(gè)性質(zhì)：

    (1) 最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。

    (2) 無后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

   （3）有重疊子問題：即子問題之間是不獨(dú)立的，一個(gè)子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）

 

四、求解的基本步驟

     動(dòng)態(tài)規(guī)劃所處理的問題是一個(gè)多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。

   初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)

                      圖1 動(dòng)態(tài)規(guī)劃決策過程示意圖

    (1)劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。

    (2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。

    (3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。

    (4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。

    一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。

實(shí)際應(yīng)用中可以按以下幾個(gè)簡化的步驟進(jìn)行設(shè)計(jì)：

    （1）分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。

    （2）遞歸的定義最優(yōu)解。

    （3）以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值

    （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解

 

五、算法實(shí)現(xiàn)的說明

    動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，也就是上面4個(gè)步驟的確定，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會非常簡單。

     使用動(dòng)態(tài)規(guī)劃求解問題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要素：

    （1）問題的階段 （2）每個(gè)階段的狀態(tài)

    （3）從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。

     遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個(gè)角度來說，動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來實(shí)現(xiàn)，不過因?yàn)檫f推可以充分利用前面保存的子問題的解來減少重復(fù)計(jì)算，所以對于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢，這也是動(dòng)態(tài)規(guī)劃算法的核心之處。

    確定了動(dòng)態(tài)規(guī)劃的這三要素，整個(gè)求解過程就可以用一個(gè)最優(yōu)決策表來描述，最優(yōu)決策表是一個(gè)二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對應(yīng)此問題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值（如最短路徑，最長公共子序列，最大價(jià)值等），填表的過程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個(gè)表格的數(shù)據(jù)通過簡單的取舍或者運(yùn)算求得問題的最優(yōu)解。

五、算法應(yīng)用示例

用一個(gè)實(shí)際例子來體現(xiàn)動(dòng)態(tài)規(guī)劃的算法思想——硬幣找零問題。

硬幣找零問題描述：現(xiàn)存在一堆面值為 V1、V2、V3 … 個(gè)單位的硬幣，問最少需要多少個(gè)硬幣才能找出總值為 T 個(gè)單位的零錢？假設(shè)這一堆面值分別為 1、2、5、21、25 元，需要找出總值 T 為 63 元的零錢。

很明顯，只要拿出 3 個(gè) 21 元的硬幣就湊夠了 63 元了。

基于上述動(dòng)態(tài)規(guī)劃的思想，我們可以從 1 元開始計(jì)算出最少需要幾個(gè)硬幣，然后再求 2 元、3元…每一次求得的結(jié)果都保存在一個(gè)數(shù)組中，以后需要用到時(shí)則直接取出即可。那么我們什么時(shí)候需要這些子問題的解呢？如何體現(xiàn)出由子問題的解得到較大問題的解呢？

其實(shí)，在我們從 1 元開始依次找零時(shí)，可以嘗試一下當(dāng)前要找零的面值（這里指 1 元）是否能夠被分解成另一個(gè)已求解的面值的找零需要的硬幣個(gè)數(shù)再加上這一堆硬幣中的某個(gè)面值之和，如果這樣分解之后最終的硬幣數(shù)是最少的，那么問題就得到答案了。

單是上面的文字描述太抽象，先假定以下變量：

values[] : 保存每一種硬幣的幣值的數(shù)組
valueKinds :幣值不同的硬幣種類數(shù)量，即values[]數(shù)組的大小
money : 需要找零的面值
coinsUsed[] : 保存面值為 i 的紙幣找零所需的最小硬幣數(shù)

算法描述：

當(dāng)求解總面值為 i 的找零最少硬幣數(shù) coinsUsed[ i ] 時(shí)，將其分解成求解 coinsUsed[ i – cents]和一個(gè)面值為 cents 元的硬幣，由于 i – cents < i ， 其解 coinsUsed[ i – cents] 已經(jīng)存在，如果面值為 cents 的硬幣滿足題意，那么最終解 coinsUsed[ i ] 則等于 coinsUsed[ i – cents] 再加上 1（即面值為 cents）的這一個(gè)硬幣。

下面用代碼實(shí)現(xiàn)并測試一下：

  1. public class CoinsChange {    
  2.     /**   
  3.      * 硬幣找零：動(dòng)態(tài)規(guī)劃算法   
  4.      *    
  5.      * @param values   
  6.      *            :保存每一種硬幣的幣值的數(shù)組   
  7.      * @param valueKinds   
  8.      *            :幣值不同的硬幣種類數(shù)量，即coinValue[]數(shù)組的大小   
  9.      * @param money   
  10.      *            :需要找零的面值   
  11.      * @param coinsUsed   
  12.      *            :保存面值為i的紙幣找零所需的最小硬幣數(shù)   
  13.      */   
  14.     public static void makeChange(int[] values, int valueKinds, int money,    
  15.             int[] coinsUsed) {    
  16.    
  17.         coinsUsed[0] = 0;    
  18.         // 對每一分錢都找零，即保存子問題的解以備用，即填表    
  19.         for (int cents = 1; cents <= money; cents++) {    
  20.    
  21.             // 當(dāng)用最小幣值的硬幣找零時(shí)，所需硬幣數(shù)量最多    
  22.             int minCoins = cents;    
  23.    
  24.             // 遍歷每一種面值的硬幣，看是否可作為找零的其中之一    
  25.             for (int kind = 0; kind < valueKinds; kind++) {                 
  26.                 // 若當(dāng)前面值的硬幣小于當(dāng)前的cents則分解問題并查表    
  27.                 if (values[kind] <= cents) {    
  28.                     int temp = coinsUsed[cents - values[kind]] + 1;    
  29.                     if (temp < minCoins) {    
  30.                         minCoins = temp;    
  31.                     }    
  32.                 }    
  33.             }    
  34.             // 保存最小硬幣數(shù)    
  35.             coinsUsed[cents] = minCoins;    
  36.    
  37.             System.out.println("面值為 " + (cents) + " 的最小硬幣數(shù) : "   
  38.                     + coinsUsed[cents]);    
  39.         }    
  40.     }    
  41.         
  42.     public static void main(String[] args) {    
  43.    
  44.         // 硬幣面值預(yù)先已經(jīng)按降序排列    
  45.         int[] coinValue = new int[] { 25, 21, 10, 5, 1 };    
  46.         // 需要找零的面值    
  47.         int money = 63;    
  48.         // 保存每一個(gè)面值找零所需的最小硬幣數(shù)，0號單元舍棄不用，所以要多加1    
  49.         int[] coinsUsed = new int[money + 1];    
  50.    
  51.         makeChange(coinValue, coinValue.length, money, coinsUsed);    
  52.     }    
  53. }   

0/1背包問題的動(dòng)態(tài)規(guī)劃法求解，前人之述備矣，這里所做的工作，不過是自己根據(jù)理解實(shí)現(xiàn)了一遍，主要目的還是鍛煉思維和編程能力，同時(shí)，也是為了增進(jìn)對動(dòng)態(tài)規(guī)劃法機(jī)制的理解和掌握。 

      值得提及的一個(gè)問題是，在用 JAVA 實(shí)現(xiàn)時(shí)， 是按算法模型建模，還是用對象模型建模呢？ 如果用算法模型，那么 背包的值、重量就直接存入二個(gè)數(shù)組里；如果用對象模型，則要對背包以及背包問題進(jìn)行對象建模。思來想去，還是采用了對象模型，盡管心里感覺算法模型似乎更好一些。有時(shí)確實(shí)就是這樣，對象模型雖然現(xiàn)在很主流，但也不是萬能的，采用其它的模型和視角，或許可以得到更好的解法。

背包建模：

  1. public class Knapsack {      
  2.         
  3.     /** 背包重量  */      
  4.     private int weight;      
  5.           
  6.     /** 背包物品價(jià)值  */      
  7.     private int value;      
  8.     /***   
  9.      * 構(gòu)造器   
  10.      */      
  11.     public Knapsack(int weight, int value) {      
  12.         this.value = value;      
  13.         this.weight = weight;      
  14.     }      
  15.     public int getWeight() {      
  16.         return weight;      
  17.     }      
  18.           
  19.     public int getValue() {      
  20.         return value;      
  21.     }      
  22.           
  23.     public String toString() {      
  24.         return "[weight: " + weight + " " + "value: " + value + "]";        
  25.     }      
  26. }       
  27.   
  28. import java.util.ArrayList;      
  29.     
  30. /**   
  31.  * 求解背包問題：   
  32.  * 給定 n 個(gè)背包，其重量分別為 w1,w2,……,wn, 價(jià)值分別為 v1,v2,……,vn   
  33.  * 要放入總承重為 totalWeight 的箱子中，    
  34.  * 求可放入箱子的背包價(jià)值總和的最大值。   
  35.  *    
  36.  * NOTE: 使用動(dòng)態(tài)規(guī)劃法求解 背包問題   
  37.  * 設(shè) 前 n 個(gè)背包，總承重為 j 的最優(yōu)值為 v[n,j], 最優(yōu)解背包組成為 b[n];   
  38.  * 求解最優(yōu)值：   
  39.  * 1. 若 j < wn, 則 ： v[n,j] = v[n-1,j];   
  40.  * 2. 若  j >= wn, 則：v[n,j] = max{v[n-1,j], vn + v[n-1,j-wn]}。   
  41.  *    
  42.  * 求解最優(yōu)背包組成：   
  43.  * 1. 若 v[n,j] > v[n-1,j] 則 背包 n 被選擇放入 b[n],    
  44.  * 2. 接著求解前 n-1 個(gè)背包放入 j-wn 的總承重中，    
  45.  *    于是應(yīng)當(dāng)判斷 v[n-1, j-wn] VS v[n-2,j-wn], 決定 背包 n-1 是否被選擇。   
  46.  * 3. 依次逆推，直至總承重為零。   
  47.  *       
  48.  *    重點(diǎn)： 掌握使用動(dòng)態(tài)規(guī)劃法求解問題的分析方法和實(shí)現(xiàn)思想。   
  49.  *    分析方法： 問題實(shí)例 P(n) 的最優(yōu)解S(n) 蘊(yùn)含 問題實(shí)例 P(n-1) 的最優(yōu)解S(n-1);   
  50.  *              在S(n-1)的基礎(chǔ)上構(gòu)造 S(n)    
  51.  *    實(shí)現(xiàn)思想： 自底向上的迭代求解 和 基于記憶功能的自頂向下遞歸   
  52.  */      
  53. public class KnapsackProblem {      
  54.           
  55.     /** 指定背包 */      
  56.     private Knapsack[] bags;      
  57.           
  58.     /** 總承重  */      
  59.     private int totalWeight;      
  60.           
  61.     /** 給定背包數(shù)量  */      
  62.     private int n;      
  63.           
  64.     /** 前 n 個(gè)背包，總承重為 totalWeight 的最優(yōu)值矩陣  */      
  65.     private int[][] bestValues;      
  66.           
  67.     /** 前 n 個(gè)背包，總承重為 totalWeight 的最優(yōu)值 */      
  68.     private int bestValue;      
  69.           
  70.     /** 前 n 個(gè)背包，總承重為 totalWeight 的最優(yōu)解的物品組成 */      
  71.     private ArrayList<Knapsack> bestSolution;      
  72.           
  73.     public KnapsackProblem(Knapsack[] bags, int totalWeight) {      
  74.         this.bags = bags;      
  75.         this.totalWeight = totalWeight;      
  76.         this.n = bags.length;      
  77.         if (bestValues == null) {      
  78.             bestValues = new int[n+1][totalWeight+1];      
  79.         }      
  80.     }      
  81.           
  82.     /**   
  83.      * 求解前 n 個(gè)背包、給定總承重為 totalWeight 下的背包問題   
  84.      *    
  85.      */      
  86.     public void solve() {      
  87.               
  88.         System.out.println("給定背包：");      
  89.         for(Knapsack b: bags) {      
  90.             System.out.println(b);      
  91.         }      
  92.         System.out.println("給定總承重: " + totalWeight);      
  93.               
  94.         // 求解最優(yōu)值      
  95.         for (int j = 0; j <= totalWeight; j++) {      
  96.             for (int i = 0; i <= n; i++) {      
  97.                   
  98.                 if (i == 0 || j == 0) {      
  99.                     bestValues[i][j] = 0;      
  100.                 }         
  101.                 else       
  102.                 {      
  103.                     // 如果第 i 個(gè)背包重量大于總承重，則最優(yōu)解存在于前 i-1 個(gè)背包中，      
  104.                     // 注意：第 i 個(gè)背包是 bags[i-1]      
  105.                     if (j < bags[i-1].getWeight()) {      
  106.                         bestValues[i][j] = bestValues[i-1][j];      
  107.                     }         
  108.                     else       
  109.                     {      
  110.                         // 如果第 i 個(gè)背包不大于總承重，則最優(yōu)解要么是包含第 i 個(gè)背包的最優(yōu)解，      
  111.                         // 要么是不包含第 i 個(gè)背包的最優(yōu)解， 取兩者最大值，這里采用了分類討論法      
  112.                         // 第 i 個(gè)背包的重量 iweight 和價(jià)值 ivalue      
  113.                         int iweight = bags[i-1].getWeight();      
  114.                         int ivalue = bags[i-1].getValue();      
  115.                         bestValues[i][j] =       
  116.                             Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);            
  117.                     } // else      
  118.                 } //else               
  119.            } //for      
  120.         } //for      
  121.               
  122.         // 求解背包組成      
  123.         if (bestSolution == null) {      
  124.             bestSolution = new ArrayList<Knapsack>();      
  125.         }      
  126.         int tempWeight = totalWeight;      
  127.         for (int i=n; i >= 1; i--) {      
  128.            if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight]) {      
  129.                bestSolution.add(bags[i-1]);  // bags[i-1] 表示第 i 個(gè)背包      
  130.                tempWeight -= bags[i-1].getWeight();      
  131.            }      
  132.            if (tempWeight == 0) { break; }      
  133.         }      
  134.         bestValue = bestValues[n][totalWeight];      
  135.     }      
  136.           
  137.     /**   
  138.      * 獲得前  n 個(gè)背包， 總承重為 totalWeight 的背包問題的最優(yōu)解值   
  139.      * 調(diào)用條件： 必須先調(diào)用 solve 方法   
  140.      *    
  141.      */      
  142.     public int getBestValue() {       
  143.         return bestValue;      
  144.     }      
  145.           
  146.     /**   
  147.      * 獲得前  n 個(gè)背包， 總承重為 totalWeight 的背包問題的最優(yōu)解值矩陣   
  148.      * 調(diào)用條件： 必須先調(diào)用 solve 方法   
  149.      *    
  150.      */      
  151.     public int[][] getBestValues() {      
  152.               
  153.         return bestValues;      
  154.     }      
  155.           
  156.     /**   
  157.      * 獲得前  n 個(gè)背包， 總承重為 totalWeight 的背包問題的最優(yōu)解值矩陣   
  158.      * 調(diào)用條件： 必須先調(diào)用 solve 方法   
  159.      *    
  160.      */      
  161.     public ArrayList<Knapsack> getBestSolution() {      
  162.         return bestSolution;      
  163.     }      
  164.           
  165. }     
  166.   
  167. public class KnapsackTest {      
  168.         
  169.     public static void main(String[] args) {      
  170.               
  171.         Knapsack[] bags = new Knapsack[] {      
  172.                 new Knapsack(2,13), new Knapsack(1,10),      
  173.                 new Knapsack(3,24), new Knapsack(2,15),      
  174.                 new Knapsack(4,28), new Knapsack(5,33),      
  175.                 new Knapsack(3,20), new Knapsack(1, 8)      
  176.         };      
  177.             
  178.         int totalWeight = 10;      
  179.         KnapsackProblem kp = new KnapsackProblem(bags, totalWeight);      
  180.               
  181.         kp.solve();      
  182.         System.out.println(" -------- 該背包問題實(shí)例的解: --------- ");      
  183.         System.out.println("最優(yōu)值：" + kp.getBestValue());       
  184.         System.out.println("最優(yōu)解【選取的背包】: ");      
  185.         System.out.println(kp.getBestSolution());      
  186.         System.out.println("最優(yōu)決策矩陣表：");      
  187.         int[][] bestValues = kp.getBestValues();      
  188.         for (int i=0; i < bestValues.length; i++) {      
  189.             for (int j=0; j < bestValues[i].length; j++) {      
  190.                 System.out.printf("%-5d", bestValues[i][j]);      
  191.             }      
  192.             System.out.println();      
  193.         }      
  194.     }      
  195. }      

    本站是提供個(gè)人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多