lecture-06-回溯算法(編輯修改稿)
2025-08-20 12:34 本頁面
【文章內(nèi)容簡介】 將這個(gè)集裝箱裝上這 2艘輪船。如果有，找出一種裝載方案。 容易證明，如果一個(gè)給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。 (1)首先將第一艘輪船盡可能裝滿； (2)將剩余的集裝箱裝上第二艘輪船。 將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問題等價(jià)于以下特殊的 01背包問題。 nixcxwxwiniiiniii????????1},1,0{s . t .m ax111用回溯法設(shè)計(jì)解裝載問題的 O(2n)計(jì)算時(shí)間算法。在某些情況下該算法優(yōu)于動(dòng)態(tài)規(guī)劃算法。 例 n=4, c1=12, w=[8,6,2,3] 具體算法描述如下： public static int maxLoading (int [] ww, int cc ) { //初始化類數(shù)據(jù)成員 n=。 w=ww。 c=cc。 cw=0。 bestw=0。 //計(jì)算最優(yōu)載重量 backtrack(1)。 return bestw。 } //回溯算法 private static void backtrack (int i) { //搜索第 i層結(jié)點(diǎn) if (in) { // 到達(dá)葉結(jié)點(diǎn) if (cwbestw) bestw=cw。 return； } //搜索子樹 if (cw+w[i]=c) { //搜索左子樹，即 cw += w[i]。 backtrack (i+1)。 cw = w[i]。 } backtrack (i+1)。 //搜索右子樹 } } public class Loading { //類數(shù)據(jù)成員 static int n。 //集裝箱數(shù) static int [] w。 //集裝箱重量數(shù)組 static int c。 //第一艘輪船的載重量 static int cw。 //當(dāng)前載重量 static int bestw。 //當(dāng)前最優(yōu)載重量 右子樹搜索條件？？ 改進(jìn)思想 :引入一個(gè)上界函數(shù)，用于剪去不含最優(yōu)解的子樹，從而改進(jìn)算法在平均情況下的效率。 上界函數(shù) public static int maxLoading (int [] ww, int cc ) { //初始化類數(shù)據(jù)成員 //初始化 r for (int i=1。 i=n。 i++) r += w[i]。 //計(jì)算最優(yōu)載重量 backtrack(1)。 return bestw。 } //回溯算法 private static void backtrack (int i) { //搜索第 i層結(jié)點(diǎn) if (in) { // 到達(dá)葉結(jié)點(diǎn) if (cwbestw) bestw=cw。 return； } //搜索子樹 r = w[i]。 if (cw+w[i]=c) { //搜索左子樹 cw += w[i]。 backtrack (i+1)。 cw = w[i]。 } if (cw+rbestw) //搜索右子樹 backtrack (i+1)。 r += w[i]。 } } public class Loading { static int r。 //剩余集裝箱重量 ?上界函數(shù) (不選擇當(dāng)前元素 )：當(dāng)前載重量 cw+剩余集裝箱的重量 r?當(dāng)前最優(yōu)載重量 bestw 構(gòu)造最優(yōu)解 為了不僅僅得到最優(yōu)裝載量，而且能得到與此最優(yōu)裝載量對(duì)應(yīng)的裝載方案，即需要構(gòu)造最優(yōu)解，則必須在算法中記錄與當(dāng)前最優(yōu)值相應(yīng)的當(dāng)前最優(yōu)解。在類 Loading中增加兩個(gè)私有數(shù)據(jù)成員 x和 bestx: x用于記錄從根至當(dāng)前結(jié)點(diǎn)的路徑， bestx記錄當(dāng)前最優(yōu)解。 算法搜索到達(dá)葉結(jié)點(diǎn)處，就修正 bestx的值。 public class Loading { static int []x。 //當(dāng)前解 static int []bestx。 //當(dāng)前最優(yōu)解 public static int maxLoading (int [] ww, int cc ) { //初始化類數(shù)據(jù)成員 x=new int[n+1]。 bestx=xx。 //計(jì)算最優(yōu)載重量 backtrack(1)。 return bestw。 } //回溯算法 private static void backtrack (int i) { //搜索第 i層結(jié)點(diǎn) if (in) { // 到達(dá)葉結(jié)點(diǎn) for (int j=1。 j=n。 j++) bestx[j]=x[
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1