1. <code id="ya7qu"><span id="ya7qu"><label id="ya7qu"></label></span></code>

    <b id="ya7qu"><bdo id="ya7qu"></bdo></b>
    <wbr id="ya7qu"><optgroup id="ya7qu"><strike id="ya7qu"></strike></optgroup></wbr>
  2. <u id="ya7qu"><bdo id="ya7qu"></bdo></u>
    現(xiàn)在位置:范文先生網(wǎng)>理工論文>計(jì)算機(jī)論文>用動(dòng)態(tài)規(guī)劃法與回溯法實(shí)現(xiàn)0-1背包問題的比較

    用動(dòng)態(tài)規(guī)劃法與回溯法實(shí)現(xiàn)0-1背包問題的比較

    時(shí)間:2023-04-04 14:43:51 計(jì)算機(jī)論文 我要投稿
    • 相關(guān)推薦

    用動(dòng)態(tài)規(guī)劃法與回溯法實(shí)現(xiàn)0-1背包問題的比較

     1背包問題

      0-1背包問題:給定n種物品和一背包。物品i的重量是Wi,其價(jià)值為Vi,背包的容量為C。問應(yīng)如何選擇裝入背包中物品,使得裝入背包中物品的總價(jià)值最大?

    用動(dòng)態(tài)規(guī)劃法與回溯法實(shí)現(xiàn)0-1背包問題的比較

      對于一個(gè)實(shí)例:物品種類N=4,背包容量C=10,物品重量數(shù)組W={3,5,2,1},相應(yīng)價(jià)值數(shù)組V={9,10,7,4}。找一個(gè)n元0-1向量(x1,x2,x3….xn)xi∈{0,1},1≤i≤n.使得

      ,

      達(dá)到最大。下面分別以動(dòng)態(tài)規(guī)劃法和回溯法來解決這個(gè)實(shí)例。

      2動(dòng)態(tài)規(guī)劃法

      動(dòng)態(tài)規(guī)劃法的基本思想是將待求解問題分解成若干個(gè)子問題,先求解子問題,然后從這些子問題的解得到原問題的解。用一個(gè)表來保存記錄所有已解決的子問題的答案,在需要的時(shí)候再找出已求得的答案,避免重復(fù)的計(jì)算。

      動(dòng)態(tài)規(guī)劃法適用于解最優(yōu)化問題。通常可按以下4個(gè)步驟:

      (1)找出最優(yōu)解的性質(zhì)并刻畫其結(jié)構(gòu)特征。

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

      (3)以自底向上的方式計(jì)算出最優(yōu)值。

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

      對于所給0-1背包問題的子問題:

      ,

      的最優(yōu)值為m(i,j),即m(i,j)是背包容量為j,可懸著物品為i,i+1,….,n時(shí)0-1背包問題的最優(yōu)值。由于0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì),可以建立計(jì)算m(i,j)的如下遞歸式:

      (1.1)

      (1.2)

      從上面算法的執(zhí)行過程中可以看出假設(shè)有Q(n)個(gè)子問題,每一個(gè)子問題最多需要m次決策,則計(jì)算的頻率為nm,回溯的頻率為n,那么整個(gè)過程的算法的時(shí)間復(fù)雜度為T(n)=nm+n,即為Q(nm)。

      3回溯法。

      回溯法在包含問題的所有解的解空間樹中,按照深度優(yōu)先的策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹。回溯算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí),總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含,則跳過對以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索,逐層向其祖先結(jié)點(diǎn)回溯。否則,進(jìn)入該子樹,繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來求問題的所有解時(shí),要回溯到根,且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。簡單地說就是確定解空間,建立解空間樹,用深度優(yōu)先搜索算法遞歸搜索解空間樹,并同時(shí)注意剪枝。

      用回溯法解題的步驟:

      (1)針對所給問題定義問題的解空間;

      (2)確定易于搜索的解空間結(jié)構(gòu);

      (3)以深度優(yōu)先方式搜索解空間,并在搜索過程中用剪枝函數(shù)避免無效的搜索。

      根據(jù)上述0-1背包問題的數(shù)學(xué)描述解向量可以表示成X={X,X,...X|X=0或=1}若X=0,表示第i個(gè)物品不裝入背包,X=1,表示將第i個(gè)物品裝入背包。

      可以用樹的形式將解空間表達(dá)出來。樹中從第i層到第i+1層的邊上的值表示解向量中X的取值,并假定第i層的左子樹描述第i個(gè)物品被裝入背包的情況,右子樹描述第i個(gè)物品被拒絕的情況。則該0-1背包問題的狀態(tài)空間樹就表示為一棵高度為n的完全二叉樹。若n=3時(shí)則此0-1背包問題的解空間的結(jié)構(gòu)如圖1-1所示。從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的任一路徑就對應(yīng)解空間中的一個(gè)解向量

      圖1-1n=3時(shí),0-1背包問題的解空間樹

      用回溯法求解0-1背包問題時(shí),可以按照物品的單位價(jià)值從大到小排序。計(jì)算當(dāng)前節(jié)點(diǎn)的上界,搜索左子樹。只有當(dāng)右子樹包含可行解時(shí)才搜索右子樹。剪去右子樹的條件是當(dāng)前價(jià)值加上剩余物品的總價(jià)值小于當(dāng)前的最優(yōu)總價(jià)值時(shí),不需搜索右子樹,可將右子樹剪去。回溯法用一定的剪枝進(jìn)行優(yōu)化,算法的時(shí)間復(fù)雜度為O(n*2n),n為物品個(gè)數(shù)。

      4總結(jié)

      動(dòng)態(tài)規(guī)劃算法:動(dòng)態(tài)規(guī)劃可以把困難得多階段決策變換為一系列相互聯(lián)系比較容易的單階段問題。對于背包問題可以對子過程用枚舉法求解,而且約束條件越多,決策的搜索范圍越小,求解也越容易。但是對于規(guī)模較大的問題它并不是一個(gè)理想的算法。最重要的原因就是它的維數(shù)障礙。即計(jì)算和存儲(chǔ)量的需要對于狀態(tài)空間和決策空間的維數(shù)的增長呈指數(shù)增長關(guān)系,這樣驚人的增長速度是計(jì)算機(jī)難以承受的。這就使得直接的動(dòng)態(tài)規(guī)劃方法求解規(guī)劃較大的背包問題發(fā)生了困難,且目前尚沒有好的解決辦法。

      回溯法:回溯法需要為問題定義一個(gè)解空間,這個(gè)解空間必須至少包含問題的一個(gè)解(可能是最優(yōu)的)。使用遞歸回溯法解決背包問題的優(yōu)點(diǎn)在于它算法思想簡單,而且它能完全遍歷搜索空間,肯定能找到問題的最優(yōu)解。但是由于此問題解的總組合數(shù)有2個(gè),因此,隨著物件數(shù)n的增大,其解的空間將以2級增長,當(dāng)n大到一定程度上,用此算法解決背包問題將是不現(xiàn)實(shí)的。

      用此兩種方法都能得到問題的最優(yōu)解,從其時(shí)間復(fù)雜度來看,兩者的速度都較慢。

    【用動(dòng)態(tài)規(guī)劃法與回溯法實(shí)現(xiàn)0-1背包問題的比較】相關(guān)文章:

    比較的特殊表達(dá)法初探01-08

    比較法楷書教學(xué)探索02-25

    “聽說法”與“交際法”的比較及啟示08-17

    比較法在物理中的應(yīng)用08-17

    歐美產(chǎn)品責(zé)任法比較及啟示02-20

    儒法之比較及其現(xiàn)代意義02-24

    運(yùn)用改換比較法培養(yǎng)語感08-17

    國際法與國內(nèi)法關(guān)系中日之比較02-20

    產(chǎn)品責(zé)任法相關(guān)問題比較11-18

    国产福利萌白酱精品tv一区_日韩亚洲中字无码一区二区三区_亚洲欧洲高清无码在线_全黄无码免费一级毛片
    1. <code id="ya7qu"><span id="ya7qu"><label id="ya7qu"></label></span></code>

      <b id="ya7qu"><bdo id="ya7qu"></bdo></b>
      <wbr id="ya7qu"><optgroup id="ya7qu"><strike id="ya7qu"></strike></optgroup></wbr>
    2. <u id="ya7qu"><bdo id="ya7qu"></bdo></u>
      久久综合视频97 | 尤物九九久久国产精品 | 亚洲日韩国产综合 | 亚洲欧美无线码中文字母 | 欧美亚洲色综久久精品国产 | 亚洲业余性爱视频偷窥 |