算法實習(xí)報告(編輯修改稿)
2024-08-22 09:45 本頁面
【文章內(nèi)容簡介】 ))。 } return 0。 } 回溯法：實際上是一種搜索問題的解的一種方法。所采用的方法一般為深度優(yōu)先搜索法，所搜索的路徑一般是沿樹形結(jié)構(gòu)進行搜索。在搜索過程中，首先會判斷所搜索的樹結(jié)點是否包含問題的解，如果肯定不包含，則不再搜索以該結(jié)點為根的樹結(jié)點，而向其祖先結(jié)點回溯。否則進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。1）遞歸回溯 利用遞歸算法對樹進行深度遍歷，并在遍歷過程中不斷地判斷當(dāng)前搜索的結(jié)點是否符合搜索條件，如果符合繼續(xù)進行深度遍歷，否則剪去該分支，搜索后續(xù)分支。2）迭代回溯 采用樹的非遞歸深度優(yōu)先遍歷方法也可實現(xiàn)回溯算法。非遞歸算法實際上是用循環(huán)來取代遞歸進行回溯。裝載問題 有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi,且∑wi=C1+C2, 其中1=i=n。問是否可以找到一種裝載方法是的這n個集裝箱可以裝載到這2艘輪船上。裝載問題是一個NP問題。在該問題中，可以采用下面的策略： （1）首先盡可能的將第一艘輪船裝滿。 （2）看剩余的貨物能否裝入第2艘船。 為什么可采用上述策略呢？可以證明！ 顯然，對于策略（1）需要去搜索一些貨物，使其貨物重量盡可能的接近于第一艘輪船的裝載量。這個搜索策略當(dāng)然可采用回溯法實現(xiàn)。// : 定義控制臺應(yīng)用程序的入口點。//include include iostreamusing namespace std。template class TypeType MaxLoading(Type w[],Type c, int n)。template class Typeclass Loading{ friend Type MaxLoading(Type [], Type, int)。public: void Backtrack(int i)。 int n。 //集裝箱數(shù)量 //w集裝箱重量數(shù)組。c第一艘輪船的載重量；cw當(dāng)前載重量。bestw當(dāng)前最優(yōu)載重量 Type *w,c,cw,bestw。 //剩余集裝箱重量 Type r。}。 int main(){ int *w,c,n,bestw,tc, Maxw=0。 //輸入必要的數(shù)據(jù) coutPlease input the number of Container:。 cinn。 w=new int[n]。 coutPlease input the weight of each container:。 for(int i=1。i=n。i++){ cinw[i]。 Maxw+=w[i]。 } coutPlease input the Maximum weight for the first ship:。 cinc。 coutPlease input the Maximum weight for the second ship:。 cintc。 //調(diào)用函數(shù)實現(xiàn)回溯法搜索是否可以以最大限度的形式裝載集裝箱到第一艘船 bestw=MaxLoading(w,c,n)。 //判斷第2艘船是否可以裝載下剩余的集裝箱 if(Maxwbestwtc) coutthe two ship can load all the container:endl。 else
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1