計算機(jī)算法分析與設(shè)計(第四版)習(xí)題算法分析部分詳解(實驗六)

1、實驗六 分支限界法/6-1、 6-6 項目 VC+6.0 測試通過/6-15 項目 VC2005 測試通過/6-1 最小長度電路板排列問題/頭文件 stdafx.h/ stdafx.h : include file for standard system include files,/ or project specific include files that are used frequently, but/ are changed infrequently/ #pragma once#define WIN32_LEAN_AND_MEAN/ Exclude rarely-used stuf

2、f from Windows headers#include <stdio.h>#include <tchar.h>/ TODO: reference additional headers your program requires here/ sy61.cpp : Defines the entry point for the console application. /Description:/分支限界法 6_1 最小長度電路板排列問題/#include "my.h"#include "stdafx.h"#include &l

3、t;iostream>#include <queue> using namespace std;int n,m;/#include "OutOfBounds.h" /定義節(jié)點類 class BoardNodefriend int FIFOBoards(int *,int ,int,int *&);/ 非類成員，可以訪問私有成員的函數(shù)，最優(yōu) 序列查找public:operator int() constreturn cd;/ 返回常數(shù) cdint len();public:int *x,s,cd,*low,*high;/x 表示當(dāng)前節(jié)點的電路板排列，

4、 s 表示當(dāng)前節(jié)點排列好的電 路板的數(shù)/表示當(dāng)前節(jié)點的最大長度， low ， high 分別表當(dāng)前節(jié)點表示每一個連接塊的第一個，和最 后一個電路板/的位置;編寫類的len()函數(shù)，求出當(dāng)前節(jié)點的連接塊長度的最大值int BoardNode:len()int tmp=0;for(int k=1;k<=m;k+)if(lowk<=n && highk>0 && tmp<highk-lowk) tmp=highk-lowk;return tmp;int FIFIOBoards(int *B，int n，int m，int *&bestx

5、)/n 為電路板的數(shù)量， m 為連接塊的數(shù)量/ int bestd;queue<BoardNode> q;/聲明 BoardNode 類的節(jié)點隊列 q BoardNode E;E.x=new intn+1;/ 為數(shù)組指針 x 分配 n+1 個動態(tài)空間，存儲當(dāng)前的排列E.s=0;/最初時，排列好的電路板的數(shù)目為0E.cd=0;E.low=new intm+1;/ 存儲每個連接塊的第一個電路板的位置 E.high=new intm+1;/ 存儲每個連接塊的最后一個電路板的位置 for(int i=1;i<=m;i+)0，表示連接E.highi=0;/ 初始化開始時的每個連接塊的最

6、后一個電路板的位置為塊 i 還沒有電路板放入 E.x 的排列中n+1，表示連E.lowi=n+1;/ 初始化開始時的每個連接塊的第一個電路板的位置為接塊 i 還沒有電路板放入 E.x 的排列中for(i=1;i<=n;i+)E.xi=i;/ 初始化 E.x 的排列為 1， 2，3nint bestd=n+1;/ 最優(yōu)距離 bestx=O;/記錄當(dāng)前最優(yōu)排列doif(E.s=n-1)/ 當(dāng)已排列了 n-1 個時 /判斷是否改變每個連接塊的最后一個電路板的位置 for(int j=1;j<=m;j+)if(BE.xnj && n>E.highj) E.highj=

7、n;int ld=E.len();/ 存儲當(dāng)前節(jié)點的各連接塊長度中的最大長度 /如果當(dāng)前的最大長度小于了 n+1if(ld<bestd)delete bestx; bestx=E.x;bestd=ld;/最優(yōu)距離else delete E.x;/刪除分配給 E.x的數(shù)組空間 delete E.low;/ 刪除分配給 E.low 的數(shù)組空間 delete E.high;/ 刪除分配給 E.high 的數(shù)組空間elseint curr=E.s+1;/rr 記錄現(xiàn)在應(yīng)該排列第幾個電路板 for(int i=E.s+1;i<=n;i+)/ 處理擴(kuò)展節(jié)點下一層所有子節(jié)點 BoardNode

8、N;N.low=new intm+1;/ 與 if 中的意思相同N.high=new intm+1;for(int j=1;j<=m;j+)N.lowj=E.lowj;/ 將 E.low 中的值賦給 N.lowN.highj=E.highj;if(BE.xij)if(curr<N.lowj)N.lowj=curr;/ 若當(dāng)前節(jié)點連接塊 j 的第一個電路板的位置 比現(xiàn)在正在排列的電路板的位置還小if(curr>N.highj)N.highj=curr;N.cd=N.len();/如果，當(dāng)前節(jié)點的最大長度小于了最優(yōu)長度則：if(N.cd<bestd)N.x=new intn

9、+1;N.s=E.s+1;for(int j=1;j<=n;j+)N.xj=E.xj;N.xN.s=E.xi;/ 交換位置N.xi=E.xN.s;/ 交換位置q.push(N);/ 將節(jié)點 N 加入隊列中elsedelete N.low;delete N.high;/printf("%d",bestd);delete E.x;/ 當(dāng)前擴(kuò)展節(jié)點所有子節(jié)點均考慮，變成死結(jié)點/try if(!q.empty()E=q.front(); /取隊列首節(jié)點作為擴(kuò)展節(jié)點 q.pop();else return bestd;/catch(OutOfBounds)/return bes

10、td;/printf("finish");while(!q.empty(); return bestd;return 1;/測試 void main() /scanf("%d%d",&n,&m); cin>>n>>m;int *B=new int*n+1; for (int t=0; t<=n; t+)Bt = new intm+1; for(int i=1;i<=n;i+) for(int j=1;j<=m;j+) cin>>Bij;/scanf("%d",&am

11、p;Bij);H.int *bestx=new intn+1; int bestd=0; bestd=FIFIOBoards(B,n,m,bestx); printf("%dn",bestd); for(i=1;i<=n;i+) cout<<bestxi<<" cout<<endl;/6-6 經(jīng)典 n 皇后問題/Description: 經(jīng)典 n 皇后問題 廣度優(yōu)先 建議 n<=14 解空間為子集樹 /參考答案說排列樹是不正確的，本例打印n*n 棋盤的所有解，即放置方法#include <iostream>

12、;#include <fstream> #include <algorithm>#include <functional>#include <queue> using namespace std;/本例子直接輸入棋盤大小，不用文件/ifstream in("input.txt"); / 請在項目文件夾下新建一個 input.txt /ofstream out("output.txt");class Nodepublic:Node(int n)t = 0; this->n = n;loc = new i

13、ntn + 1;for (int i = 0; i<= n; +i)loci = 0;Node(const Node &other) this->t = other.t;this->n = other.n; this->loc = new int n + 1; for (int i = 0; i <= n; +i) this->loci = other.loci;int t;/ 已放置 t 個皇后 int *loc;/loc1:t int n;/ 共放置 n 個皇后 bool checkNext(int next); void printQ();bo

14、ol Node:checkNext(int next)int i;for (i = 1; i <= t; +i)if (loci = next)/ 檢測同列 return false;if (loci - next = t + 1 - i)/ 檢測反斜線 行差 = 列差 return false;if (loci - next = i - t - 1)/ 檢測正斜線 return false; return true;void Node:printQ()for (int i = 1; i <= n; +i) cout<<loci<<" "

15、 cout<<endl;class Queen public:int n;/n 皇后int ansNum;/ 對于 n 皇后解的個數(shù)Queen(int n) this->n = n; ansNum = 0;void ArrangQueen();void Queen:ArrangQueen() queue<Node> Q; Node ini(n); / 初始化Q.push(ini); while(!Q.empty()Node father = Q.front(); /取隊列下一個節(jié)點Q.pop();if (father.t = n)father.printQ();+

16、ansNum;for (int i = 1; i <= n; +i)/一次性將當(dāng)前擴(kuò)展節(jié)點所有子節(jié)點考慮完，符合條件的插入隊列if (father.checkNext(i)Node Child(father); +Child.t;Child.locChild.t = i; Q.push(Child);int main()/#define in cin/#define out cout cout<<" 請輸入棋盤大小 n:" int n; cin>>n; / 從文件中讀入一個整數(shù) /for(int Case = 1; Case <= cas

17、es; +Case) /int n; /in>>n; Queen Q(n); Q.ArrangQueen();/out<<"Case #"<<Case<<": "<<Q.ansNum<<endl;cout<<" 共 "<<Q.ansNum<<" 種放置皇后方法，如上所示。 "<<endl; / return 0;/6-15 排列空間樹問題 VC2005 測試通過/ stdafx.h 頭文件/ st

18、dafx.h : include file for standard system include files,/ or project specific include files that are used frequently, but/ are changed infrequently/#pragmaonce#define WIN32_LEAN_AND_MEANWindows headers#include <stdio.h>#include <tchar.h>/ Exclude rarely-used stuff from/ TODO: reference a

19、dditional headers your program requires here/頭文件 MinHeap2.h ；最小堆實現(xiàn)#include <iostream> template<class Type> class Graph;template<class T> class MinHeap template<class Type> friend class Graph; public:MinHeap(int maxheapsize = 10); MinHeap()delete heap; int Size() constreturn c

20、urrentsize; T Max()if(currentsize) return heap1;MinHeap<T>& Insert(const T& x);MinHeap<T>& DeleteMin(T &x);void Initialize(T x, int size, int ArraySize); void Deactivate();void output(T a,int n);private:int currentsize, maxsize;T *heap;template <class T>void MinHeap

21、<T>:output(T a,int n) for(int i = 1; i <= n; i+) cout << ai << " " cout << endl;template <class T>MinHeap<T>:MinHeap(int maxheapsize)maxsize = maxheapsize; heap = new Tmaxsize + 1; currentsize = 0;template<class T>MinHeap<T>& MinHeap&l

22、t;T>:Insert(const T& x) if(currentsize = maxsize)return *this;int i = +currentsize;while(i != 1 && x < heapi/2)heapi = heapi/2;i /= 2;heapi = x; return *this;template<class T>MinHeap<T>& MinHeap<T>:DeleteMin(T& x) if(currentsize = 0)cout<<"Empty

23、 heap!"<<endl;return *this;x = heap1;T y = heapcurrentsize-; int i = 1, ci = 2; while(ci <= currentsize) if(ci < currentsize && heapci > heapci + 1) ci+;if(y <= heapci) break;heapi = heapci;i = ci;ci *= 2;heapi = y; return *this;template<class T>void MinHeap<T

24、>:Initialize(T x, int size, int ArraySize) delete heap; heap = x; currentsize = size; maxsize = ArraySize;for(int i = currentsize / 2; i >= 1; i-) T y = heapi;int c = 2 * i;while(c <= currentsize)if(c < currentsize && heapc > heapc + 1) c+;if(y <= heapc)break;heapc / 2 = he

25、apc;c *= 2;heapc / 2 = y; template<class T>void MinHeap<T>:Deactivate()heap = 0;/批作業(yè)調(diào)度問題 優(yōu)先隊列分支限界法求解/算法編碼與教材一致#include "stdafx.h"#include "MinHeap2.h"#include <iostream>using namespacestd;classFlowshop; classMinHeapNode friend Flowshop; public:operatorint() cons

26、t return bb;private:void Init(int);void NewNode(MinHeapNode,int,int,int,int);int s,/已安排作業(yè)數(shù)f1,/ 機(jī)器 1上最后完成時間f2,/機(jī)器 2上最后完成時間sf2,/當(dāng)前機(jī)器 2上完成時間和bb,/當(dāng)前完成時間和下界*x;/當(dāng)前作業(yè)調(diào)度;classFlowshopfriend int main(void); public:int BBFlow( void);private:int Bound(MinHeapNode E,int &f1,int &f2,bool *y);void Sort(vo

27、id);int n,/作業(yè)數(shù)* M,/各作業(yè)所需的處理時間數(shù)組*b,/各作業(yè)所需的處理時間排序數(shù)組*a,數(shù)組M和b的對應(yīng)關(guān)系數(shù)組*bestx,/最優(yōu)解bestc;/最小完成時間和bool *y;/工作數(shù)組;template <classType>inline void Swap(Type &a, Type &b);int main()int n=3,bf;int M132=2,1,3,1,2,3;int *M = new int*n; int *b = new int*n; int *a = new int *n; bool *y = new bool*n; int

28、 *bestx = new intn;for(int i=0;i<=n;i+)Mi = new int2; bi = new int 2; ai = new int 2; yi = new bool2;coutvv"各作業(yè)所需要的時間處理數(shù)組 M(i,j)值如下："<<endl;for(int i=0;i<n;i+)for(int j=0;j<2;j+)Mij=M1ij;for(int i=0;i<n;i+)cout<<"(" ;for(int j=0;j<2;j+) cout<<Mij&

29、lt;< " " cout<<")" ;cout<<endl;Flowshop flow; flow.n = n; flow.M = M; flow.b = b; flow.a = a; flow.y = y; flow.bestx = bestx; flow.bestc = 1000;/給初值 flow.BBFlow();coutvv"最優(yōu)值是："vvfiow.bestcvve ndl; coutvv"最優(yōu)調(diào)度是："for(int i=0;i<n;i+)cout<<

30、(flow.bestxi+1)<< " " cout<<endl;for(int i=0;i<n;i+)delete Mi; delete bi; delete ai; delete yi;return 0;/最小堆節(jié)點初始化void MinHeapNode:Init( int n) x = new int n; for(int i=0; i<n; i+) xi = i;s = 0; f1 = 0; f2 = 0;sf2 = 0; bb = 0;/最小堆新節(jié)點void MinHeapNode:NewNode(MinHeapNode E,i

31、nt Ef1,int Ef2,int Ebb,int n) x = new int n; for(int i=0; i<n; i+) xi = E.xi;f1 = Ef1;f2 = Ef2;sf2 = E.sf2 + f2; bb = Ebb;s = E.s + 1;/ 對各作業(yè)在機(jī)器 1和 2上所需時間排序 void Flowshop:Sort(void )int *c = new int n;for(int j=0; j<2; j+)for(int i=0; i<n; i+)bij = Mij; ci = i;for(int i=0; i<n-1; i+)for(int k=n-1; k>i; k-)if (bkj<bk-1j)Swap(bkj,bk-1j);Swap(ck,ck-1);for(int i=0; i<n; i+) acij = i;deletec;/計算完成時間和下界int FlowShop:Bound(MinHeapNode E,int &f1 , int &f2, bool *y) for(int k=0; k<n; k+)for(int j=0; j<2; j+) y