算法設(shè)計(jì)與分析實(shí)驗(yàn)4報(bào)告

1、湖南科技學(xué)院實(shí)驗(yàn)報(bào)告系部數(shù)學(xué)與計(jì)算科學(xué)專業(yè)信息與計(jì)算科學(xué)成績?cè)u(píng)定班級(jí)信計(jì)0902班學(xué)號(hào)1姓名易丹課程名稱算法設(shè)計(jì)與分析實(shí)驗(yàn)時(shí)間2012.5.18實(shí)驗(yàn)編號(hào)實(shí)驗(yàn)四實(shí)驗(yàn)名稱回溯法實(shí)驗(yàn)環(huán)境D315、一臺(tái)電腦、Codeblocks10.05實(shí)驗(yàn)?zāi)康?. 理解回溯法的深度優(yōu)先搜索策略。2. 掌握用回溯法解題的算法框架。3. 掌握回溯法的設(shè)計(jì)策略。實(shí)驗(yàn)內(nèi)容（算法、程序、步驟和方法 輸入、輸出、實(shí)驗(yàn)結(jié)果 實(shí)驗(yàn)結(jié)果分析）實(shí)驗(yàn)內(nèi)容： 1. 排兵布陣問題某游戲中，不同的兵種處在不同的地形上其攻擊能力不一樣，現(xiàn)有n個(gè)不同兵種的角色1,2,.,n，需安排在某戰(zhàn)區(qū)n個(gè)點(diǎn)上，角色i在j點(diǎn)上的攻擊力為Aij。試設(shè)計(jì)一個(gè)布陣方

2、案，使總的攻擊力最大。數(shù)據(jù)：防衛(wèi)點(diǎn)角色1234516040805060290608070203305040508049040307090560809060502. 0-1背包問題（選做）編程實(shí)現(xiàn)0-1背包問題的回溯算法。數(shù)據(jù)文件見附件。實(shí)驗(yàn)要求： 1. 實(shí)驗(yàn)報(bào)告只寫實(shí)驗(yàn)。2. 寫出算法思想、主要程序代碼、算法復(fù)雜性分析。實(shí)驗(yàn)（1）的步驟、算法及運(yùn)行結(jié)果： 1. 回溯法的總體思想回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)

3、，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。2.回溯法的實(shí)現(xiàn)。打開Codeblocks10.05，編輯頭文件Queue.h和主程序main.cpp,利用參考程序，同時(shí)還設(shè)計(jì)了從文件讀入數(shù)據(jù)，使程序更清晰，其主要程序如下：Main.cpp#include #include #include #include #define INT_MAX 90using namespace std;template /交換兩個(gè)變量的值void Swap(Type &a,Type &b) Type t=b; b=a

4、; a=t;template /創(chuàng)建二維數(shù)組void TwoDimArray(Type* &p,int r,int c) p=new Type *r; for(int i=0; ir; i+) pi=new Typec; for(int i=0; ir; i+) for(int j=0; jc; j+) pij=0;template /輸出一維數(shù)組的元素void Print1(Type a,int n) for(int i=1; i=n; i+) coutai ; coutendl;templatevoid InputData2(T *M,int r,int c,char *filename)

5、 ifstream infile; infile.open(filename); /打開文件 if(!infile) /測試是否已經(jīng)成功地打開了文件 cerr文件打開失敗！endl; exit(1); /結(jié)束程序 string s; for(int i=0; ir; +i) /讀取矩陣數(shù)據(jù) getline(infile,s); /讀一行 istringstream ss(s); /創(chuàng)建字符串流ss for(int j=0; jMij; /從流中讀取一個(gè)T類型的數(shù)賦給M class Flowshop friend int Flow(int *,int,int );private: void Ba

6、cktrack(int i); int *M; /各作業(yè)所需的處理時(shí)間 int *x; /當(dāng)前位置安排 int *bestx; /當(dāng)前最優(yōu)攻擊力 int *f2; /機(jī)器2完成處理時(shí)間 int f1; /機(jī)器1完成處理時(shí)間 int f; /當(dāng)前攻擊力 int bestf; /當(dāng)前最優(yōu)值 int n; /角色;void Flowshop:Backtrack(int i) if(in) int t=0; for(int i=1; ibestf) bestf=t; for(int j=1;j=n;j+) bestxj=xj; else for(int j=i; j=n; j+) /自i后，有i:n項(xiàng)

7、作業(yè) Swap(xi,xj); /xj成為第i個(gè)作業(yè) Backtrack(i+1); Swap(xi,xj); int Flow(int *M,int n,int bestx) Flowshop X; /初始X對(duì)象的數(shù)據(jù) X.x=new intn+1; X.f2=new intn+1; X.M=M; X.n=n; X.bestx=bestx; X.bestf=0; X.f1=0; X.f=0; for(int i=0; i=n; i+) X.f2i=0; X.xi=i; X.Backtrack(1); delete X.x; delete X.f2; return X.bestf;int ma

8、in() Flowshop X; int *M; int n; int *bestx; int bestf; TwoDimArray(M,5,5); X.x=new intn+1; X.M=M; X.n=n; X.bestx=new intn+1; X.bestf=0; int s=Flow(M,n,bestf); coutsendl; Print1(bestx,5); return 0;運(yùn)行結(jié)果：實(shí)驗(yàn)總結(jié)今天主要學(xué)的是回溯法，由于上一次實(shí)驗(yàn)老師要求我們從文件輸入數(shù)據(jù)，因此這一次我同樣利用了該種方式，將矩陣中的數(shù)據(jù)仍從文件輸入，還挺好上手的，但是本該順暢的實(shí)驗(yàn)過程中卻出現(xiàn)了一個(gè)笨錯(cuò)誤，就是我的程序調(diào)試總是不正確，我還想著明明就和別人的差不多，不應(yīng)該啊但是別的同學(xué)都可以運(yùn)行了，我很糾結(jié)，又反復(fù)看了很